A Community Detection Algorithm Based on Balanced Label Propagation

Huijuan Jia; Ting Liu; Xiaohong Zhang

doi:10.4108/eetel.5881

Authors

Huijuan Jia Henan Polytechnic University
Ting Liu Henan Polytechnic University
Xiaohong Zhang Henan Polytechnic University

DOI:

https://doi.org/10.4108/eetel.5881

Keywords:

Community Detection, Node Importance, Community Merging, Balanced Label Propagation

Abstract

OBJECTIVES: In conventional label propagation algorithms, the randomness inherent in the selection order of nodes and subsequent label propagation frequently leads to instability and reduces the accuracy of community detection outcomes.

METHODS: First, select the initial node according to the node importance and assign different labels to each initial node, aiming to reduce the number of iterations of the algorithm and improve the efficiency and stability of the algorithm; second, identify the neighbor node with the largest connection to each initial node for the pre-propagation of the labels; then, the algorithm traverses the nodes in descending order of the node importance for the propagation of labels to reduce the randomness of the label propagation process; finally, the final community is formed through the rapid merging of small communities.

RESULTS: The experimental results on multiple real datasets and artificially generated networks show that the stability and accuracy are all improved.

CONCLUSION: The proposed community detection algorithm based on balanced label propagation is better than the other four advanced algorithms on Q and NMI values of community division results.

References

Shang R, Zhang W, Zhang J, et al. Local community detection based on higher-order structure and edge information[J]. Physica A: Statistical Mechanics and its Applications, 2022, 587: 126513.

Teng X, Liu J, Li M. Overlapping community detection in directed and undirected attributed networks using a multiobjective evolutionary algorithm[J]. IEEE transactions on cybernetics, 2019, 51(1): 138-150.

N. Papadopoulos A, Tzortzidis G. Distributed time-based local community detection[C]//Proceedings of the 24th Pan-Hellenic Conference on Informatics. 2020: 390-393.

Midoun M A, Wang X, Talhaoui M Z. A jungle community detection algorithm based on new weighted similarity[J]. Arabian Journal for Science and Engineering, 2021, 46: 8493-8507.

Zhang, Wei Tong. Complex network community detection and its application based on graph representation and label propagation [D]. Xi'an University of Electronic Science and Technology, 2021.

Liu Wanjun. Research on the Application of Artificial Intelligence in Digital Archive Service [D]. Heilongjiang University, 2020.

Zhang Y, Liu Y, Li Q, et al. LILPA: A label importance based label propagation algorithm for community detection with application to core drug discovery[J]. Neurocomputing, 2020, 413: 107-133.

Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical review E, 2007, 76(3): 036106.

Zhang X, Ren J, Song C, et al. Label propagation algorithm for community detection based on node importance and label influence[J]. Physics Letters A, 2017, 381(33):2691-2698.

Saeid A, Taghavi S A, Asgarali B, et al. A three-stage algorithm for local community detection based on the high node importance ranking in social networks[J]. Physica A: Statistical Mechanics and its Applications, 2021, 563125420-.

Kong H, Kang Q, Liu C, et al. An improved label propagation algorithm based on node intimacy for community detection in networks[J]. International Journal of Modern Physics B, 2018, 32(25): 1850279.

Yue Y, Wang G, Hu J, et al. An improved label propagation algorithm based on community core node and label importance for community detection in sparse network[J]. Applied Intelligence, 2023: 1-17.

Deng Kaixuan, Chen Hongchang, Huang Ruiyang. Improved LPA algorithm based on label propagation capability[J]. Computer Engineering, 2018, 44(3): 60-64.

Zarezade M, Nourani E, Bouyer A. Community detection using a new node scoring and synchronous label updating of boundary nodes in social networks[J]. Journal of AI and Data Mining, 2020, 8(2): 201-212.

Thakare S B, Kiwelekar A W. Skiplpa: An efficient label propagation algorithm for community detection in sparse network[C]//Proceedings of the 9th Annual ACM India Conference. 2016: 97-106.

YUAN Huilin, HAN Zhen, FENG Chong et al. A community discovery method based on core node influence[J]. Computer Science,2022,49(S2):240-246.

Li H, Zhang R, Zhao Z, et al. LPA-MNI: an improved label propagation algorithm based on modularity and node importance for community detection[J]. Entropy, 2021, 23(5): 497.

Lin Z, Zheng X, Xin N, et al. CK-LPA: Efficient community detection algorithm based on label propagation with community kernel[J]. Physica A: Statistical Mechanics and its Applications, 2014, 416: 386-399.

Zhao X, Liang J, Wang J. A community detection algorithm based on graph compression for large-scale social networks[J]. Information Sciences, 2021, 551: 358-372.

Roghani H, Bouyer A. A fast local balanced label diffusion algorithm for community detection in social networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2022.

Bouyer A, Roghani H. LSMD: A fast and robust local community detection starting from low degree nodes in social networks[J]. Future Generation Computer Systems, 2020, 113: 41-57.

Zhang W, Shang R, Jiao L. Large-scale community detection based on core node and layer-by-layer label propagation[J]. Information Sciences, 2023, 632: 1-18.

Zhai Zhenxin, Yu Yecheng, Gu Yu et al. A label propagation community discovery method based on layer-by-layer expansion of core nodes[J]. Computer and Digital Engineering, 2022, 50(06): 1327-1333+1346.

Bouyer A, Azad K, Rouhi A. A fast community detection algorithm using a local and multi-level label diffusion method in social networks[J]. International Journal of General Systems, 2022, 51(4): 352-385.

Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of anthropological research, 1977, 33(4): 452-473.

Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: can geographic isolation explain this unique trait[J]. Behavioral Ecology and Sociobiology, 2003, 54: 396-405.

Newman M E J. Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, 2006, 103(23): 8577-8582.

Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the national academy of sciences, 2002, 99(12): 7821-7826.

Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical review E, 2006, 74(3): 036104.

Boguná M, Pastor-Satorras R, Díaz-Guilera A, et al. Models of social networks based on social distance attachment[J]. Physical review E, 2004, 70(5): 056122.

Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133.

Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth[C]//Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. 2012: 1-8.

Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical review E, 2008, 78(4): 046110.