Abstract
As a scientific research method to reveal the intrinsic functional properties of complex network systems, Community Detection has already become one of the most popular research topics in complex networks. The typical label propagation algorithms are very suitable for large-scale networks due to their approximate linear time complexity. But too many random strategies in the algorithms make it not stable enough. For that reason, this paper proposes a Community Detection Algorithm Fusing Node Similarity and Label Propagation (FNSLP). First, the algorithm preprocesses the neighboring nodes of the seed nodes by node similarity to reduce the kinds of the initial label. Combined with nodes’ influence, the label propagation ability is calculated. Then, the label selection of nodes is assisted by an improved label update strategy, which reduces the phenomenon of label oscillation and improves the accuracy and stability of label selection. Experimental results show that in four real networks, the algorithm achieves the maximum Modularity value on 75% of the datasets. In multiple artificial benchmark networks with different mixing parameters, the algorithm's Normalized Mutual Information value reaches the maximum value.
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
Barabási, A.L.: Network science. Philos. Trans. R. Soc. A Math. Phys. Eng. Sci. 371(1987), 20120375 (2013)
Khan, B.S., Niazi, M.A.: Network community detection: a review and visual survey. arXiv preprint arXiv:1708.00977 (2017)
Ma, L., Li, N., Guo, Y., et al.: Learning to optimize: reference vector reinforcement learning adaption to constrained many-objective optimization of industrial copper burdening system. IEEE Trans. Cybern. (2021)
Ma, L., Wang, X., Wang, X., et al.: TCDA: truthful combinatorial double auctions for mobile edge computing in industrial Internet of Things. IEEE Trans. Mob. Comput. PP(99) (2021)
Shirazi, S., Albadvi, A., Akhondzadeh, E., et al.: A new application of community detection for identifying the real specialty of physicians. Int. J. Med. Informatics 140, 104161 (2020)
Javed, M.A., Younis, M.S., Latif, S., et al.: Community detection in networks: a multidisciplinary review. J. Netw. Comput. Appl. 108, 87–111 (2018)
Huang, X., Chen, D., Ren, T., et al.: A survey of community detection methods in multilayer networks. Data Min. Knowl. Disc. 35(1), 1–45 (2021)
Jin, D., Yu, Z., Jiao, P., et al.: A survey of community detection approaches: from statistical modeling to deep learning. IEEE Trans. Knowl. Data Eng. (2021)
Yulin, T.: A community detection algorithm based on label propagation. J. Lanzhou Univ. Arts Sci. (Natural Science Edition) (2021)
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)
Lin, T.-S., Sun, F.-X.: Label propagation algorithm based on node importance and similarity. Comput. Syst. Appl. 30(10), 218–223 (2021)
Li, W., Xie, Z., Yu, Z.: A new algorithm based on node similarities for community detection. Softw. Guide 17(2), 63–67 (2018)
Zhao, Y., Li, S., Chen, X.: Community detection using label propagation in entropic order. In: 2012 IEEE 12th International Conference on Computer and Information Technology. IEEE, pp. 18–24 (2012)
Sun, S., Fan, J., Qu, J., et al.: Improved label propagation algorithm based on network preprocessing. Comput. Syst. Appl. 27(4), 173–177 (2018)
Zhang, M., Li, L.: Research on stable label propagation community division algorithm. Comput. Technol. Dev. 30(1), 129–134 (2020)
Deng, K., Chen, H., Huang, R.: Improved LPA algorithm based on label propagation ability. Comput. Eng. 44(3), 60–64 (2018)
Qi, J., Xun, L., Yi, W.: Overlapping community detection algorithm based on the selection of seed nodes. Appl. Res. Comput. 34(12), 3534–3537 (2017)
Laassem, B., Idarrou, A., Boujlaleb, L.: Label propagation algorithm for community detection based on Coulomb’s law. Phys. A 593, 126881 (2022)
Yang, H., Cheng, J., Yang, Z., et al.: A node similarity and community link strength-based community discovery algorithm. Complexity 2021(22), 1–17 (2021)
Gao, Y., Yu, X., Zhang, H.: Overlapping community detection by constrained personalized PageRank. Expert Syst. Appl. 173, 114682 (2021)
Zhang, Y., Xia, X., Xu, X., et al.: Robust hierarchical overlapping community detection with personalized PageRank. IEEE Access 8, 102867–102882 (2020)
Brahim, L., Loubna, B., Ali, I.: A literature survey on label propagation for community detection. In: 2021 Fifth International Conference on Intelligent Computing in Data Sciences (ICDS), pp. 1–7. IEEE (2021)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3–5), 75–174 (2010)
Qui, X., Cheng, Y.: An improved particle-swarm-optimization algorithm for community discovery in social networks. J. Chin. Comput. Syst. 35(6), 1422–1426 (2014)
Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Wu, Q., Chen, R., Yu, W., et al.: Overlapping community detection algorithm fusing label preprocessing and node influence. J. Comput. Appl. 40(12), 3578 (2020)
Wu, Q., Chen, R., Yu, W., Liu, G.: Overlapping community detection algorithm fusing label preprocessing and node influence. J. Comput. Appl. 40(12), 3578 (2020)
Acknowledgment
This work was supported by R&D projects in key areas of Guangdong Province under Grant 2021B0101200003, and the Scientific Research Project of Hunan Education Department under Grant 19C0766.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Liu, Y., Yu, J., Liu, Z., Han, X. (2022). A Community Detection Algorithm Fusing Node Similarity and Label Propagation. In: Ma, H., Wang, X., Cheng, L., Cui, L., Liu, L., Zeng, A. (eds) Wireless Sensor Networks. CWSN 2022. Communications in Computer and Information Science, vol 1715. Springer, Singapore. https://doi.org/10.1007/978-981-19-8350-4_8
Download citation
DOI: https://doi.org/10.1007/978-981-19-8350-4_8
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-8349-8
Online ISBN: 978-981-19-8350-4
eBook Packages: Computer ScienceComputer Science (R0)