Abstract
Community detection is an enduring research hotspot in the field of complex networks. The label propagation algorithm is a semi-supervised learning method, which has the advantages of close to linear time complexity, simplicity and ease of implementation. However, LPA has two significant shortcomings in dividing communities: poor accuracy and strong randomness, which seriously affect the performance of the algorithm. This paper proposes a new label propagation algorithm to solve these two problems. In the initialization stage, a new node importance metric is proposed, which simultaneously considers the importance both of the node itself and its neighbor nodes to rank the importance of the nodes. In the label propagation stage, We also propose a new node similarity metric and the label is updated according to the similarity between the current node and neighbor nodes. Our experiments on real networks and artificial synthetic networks show that this algorithm can effectively find community structure and has better stability and accuracy than some existing LPA improved algorithms, and this advantage is more obvious on large networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Liu, Y., Shen, D., Kou, Y., Nie, T.: Link prediction based on node embedding and personalized time interval in temporal multi-relational network. In: Ni, W., Wang, X., Song, W., Li, Y. (eds.) WISA 2019. LNCS, vol. 11817, pp. 404–417. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30952-7_40
Berahmand, K., Bouyer, A.: A link-based similarity for improving community detection based on label propagation algorithm. J. Syst. Sci. Complexity 32(3), 737–758 (2019). E69, 066133 (2004)
Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76(3), 036106 (2007)
Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10), 103018 (2010)
Barber, M.J., Clark, J.W.: Detecting network communities by propagating labels under constraints. Phys. Rev. E 80(2), 026129 (2011)
Leung, I.X., Hui, P., Lio, P., Crowcroft, J.: Towards real-time community detection in large networks. Phys. Rev. E 79(6), 066107 (2009)
Zhuoxiang, Z., Yitong, W., Jiatang, T., Zexu, Z.: A novel algorithm for community discovery in social networks based on label propagation. J. Comput. Res. Dev. 3, 8–15 (2011)
Zhang, Y., Liu, Y., Zhu, J., Yang, C., Yang, W., Zhai, S.: NALPA: a node ability based label propagation algorithm for community detection. IEEE Access 8, 46642–46664 (2020)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Zhu, X., Xia, Z.: Label Propagation Algorithm Based on Adaptive H Index. Springer, Cham (2018)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Danon, L., Diaz-Guilera, A., Duch, J., et al.: Comparing community structure identification. J. Stat. Mech. Theory Exp. 2005(09), P09008 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, J., Xia, Z. (2021). A New Novel Label Propagation Algorithm. In: Xing, C., Fu, X., Zhang, Y., Zhang, G., Borjigin, C. (eds) Web Information Systems and Applications. WISA 2021. Lecture Notes in Computer Science(), vol 12999. Springer, Cham. https://doi.org/10.1007/978-3-030-87571-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-87571-8_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-87570-1
Online ISBN: 978-3-030-87571-8
eBook Packages: Computer ScienceComputer Science (R0)