A framework for overlapping and non-overlapping communities detection based on seed extension and label propagation

Current social networks driven by Internet technology are characterized by complexity, overlap and large-scale. However, the label propagation algorithm, despite its near-linear time complexity that has drawn significant attention, remains a challenge in meeting the demands for high accuracy and stability. We introduce LPANIS (Label Propagation Algorithm with Node Importance and Similarity), a novel community detection algorithm that utilizes a combination of seed extension and label propagation. This approach enables the detection of both overlapping and non-overlapping communities concurrently, providing a solution to the challenges mentioned above. Initially, the seed node is identified and similarity is employed to preprocess the labels of nodes adjacent to the seed node. Subsequently, a predetermined sequence determined by node importance is utilized for the execution of label propagation. Finally, the community structure is detected using label propagation ability and label update strategy. We evaluate the effectiveness of our method by comparing experiments on five real networks and five synthetic networks, using seven comparison algorithms. Multiple sets of experiments show that LPANIS obtains the best results in both modularity and normalized mutual information. In seventy-five percent of synthetic networks, the accuracy of detecting overlapping nodes is not less than 0.83 according to the F−score.