Abstract:Existing label propagation based overlapping community detection algorithms are limited, in terms of lacking accuracy, exhibiting high randomness, etc., when applied to complex networks. To overcome these limitations, this paper proposes a novel algorithm for overlapping community detection based on label propagation(NOCDLP). In the algorithm, we first search for a number of complete subgraphs centered on nodes with higher degrees in a network and initiate the label propagation starting from these subgraphs. Then, a function to specify the bonds between nodes and communities is generated, by analyzing the strength of connections between nodes and communities, and the internal closeness of a particular community after a certain node is adopted. By introducing this function, the accuracy of community detection is increased significantly. Subsequently, in the process of label propagation, NOCDLP sets control marks to alleviate the high randomness in community detection. Finally, the algorithm cleans up overlapping nodes to improve the accuracy of the overlapping community structures generated. This algorithm is tested in both artificial and real-world networks. The experimental results show that the proposed algorithm is practical and more efficient in comparison with multiple classical algorithms.