Abstract
Dividing a network into communities has great benefits in understanding the characteristics of the network. The label propagation algorithm (LPA) is a fast and convenient community detection algorithm. However, the community initialization of LPA does not take advantage of topological information of networks, and its robustness is poor. In this paper, we propose a stable community detection algorithm based on density peak clustering and label propagation (DS-LPA). First, the local density calculation method in density peak clustering algorithm is improved in finding the community center of the network, so as to build a suitable initial community, which can improve the quality of community partition. Then, the label update order is determined reasonably by computing the information transmission power of nodes, and the solutions for multiple candidate labels are provided, which greatly improved the robustness of the algorithm. DS-LPA is compared with other seven algorithms on the synthetic network and real-world networks. NMI, ARI, and modularity are used to evaluate these algorithms. It can be concluded that DS-LPA has a higher performance than most comparison algorithms on synthetic network with ten different mixed parameters by statistical testing. And DS-LPA can quickly calculate the best community partition on different sizes of real-world networks.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Guerrero M, Montoya FG, Baños R, Alcayde A, Gil C (2018) Community detection in national-scale high voltage transmission networks using genetic algorithms. Adv Eng Inform 38:232– 241
Lu F, Liu K, Duan Y, Cheng S, Du F (2018) Modeling the heterogeneous traffic correlations in urban road systems using traffic-enhanced community detection approach. Physica A: Stat Mech Appl 501:227–237
Mallek S, Boukhris I, Elouedi Z (2015) Community detection for graph-based similarity: application to protein binding pockets classification. Pattern Recogn Lett 62:49–54
Pattanayak HS, Sangal AL, Verma HK (2019) Community detection in social networks based on fire propagation. Swarm Evol Comput 44:31–48
M’barek MB, Borgi A, Bedhiafi W, Hmida SB (2018) Genetic algorithm for community detection in biological networks. Procedia Comput Sci 126:195–204
Sun PG, Gao L, Yang Y (2013) Maximizing modularity intensity for community partition and evolution. Inf Sci 236:83– 92
Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113
Feng Y, Chen H, Li T, Luo C (2020) A novel community detection method based on whale optimization algorithm with evolutionary population. Appl Intell:1–20
Guo K, He L, Chen Y, Guo W, Zheng J (2020) A local community detection algorithm based on internal force between nodes. Appl Intell 50(2):328–340
Huang X, Cheng H, Yu JX (2015) Dense community detection in multi-valued attributed networks. Inf Sci 314:77–99
Li H J, Bu Z, Li A, Liu Z, Shi Y (2016) Fast and accurate mining the community structure: Integrating center locating and membership optimization. IEEE Trans Knowl Data Eng 28(9):2349–2362
Plantié M, Crampes M (2013) Survey on social community detection. In: Social media retrieval. Springer, pp 65–85
Yang Z, Algesheimer R, Tessone CJ (2016) A comparative analysis of community detection algorithms on artificial networks. Sci Rep 6:30750
Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821– 7826
Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exper 2008(10):P10008
Derényi I, Palla G, Vicsek T (2005) Clique percolation in random networks. Phys Rev Lett 94(16):160202
Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111
Bagrow JP, Bollt EM (2005) Local method for detecting communities. Phys Rev E 72 (4):046108
Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106
Lou H, Li S, Zhao Y (2013) Detecting community structure using label propagation with weighted coherent neighborhood propinquity. Physica A: Stat Mech Appl 392(14):3095– 3105
Zarandi FD, Rafsanjani MK (2018) Community detection in complex networks using structural similarity. Physica A: Stat Mech Appl 503:882–891
Nan DY, Yu W, Liu X, Zhang YP, Dai WD (2018) A framework of community detection based on individual labels in attribute networks. Physica A: Stat Mech Appl 512:523–536
Xing Y, Meng F, Zhou Y, Zhu M, Shi M, Sun G (2014) A node influence based label propagation algorithm for community detection in networks. Sci World J 2014:1–13
Zhang XK, Ren J, Song C, Jia J, Zhang Q (2017) Label propagation algorithm for community detection based on node importance and label influence. Phys Lett A 381(33):2691– 2698
Leung IX, Hui P, Lio P, Crowcroft J (2009) Towards real-time community detection in large networks. Phys Rev E 79(6): 066107
Qiang H, Yan G (2012) A method of personalized recommendation based on multi-label propagation for overlapping community detection. In: 2012 3Rd international conference on system science, engineering design and manufacturing informatization. IEEE, vol 1, pp 360–364
Liu T, Yan X, Shenzhi C (2018) Site-effect-based semi-synchronous label propagation algorithm for community detection. In: 2018 IEEE Intl conf on parallel & distributed processing with applications, ubiquitous computing & communications, big data & cloud computing, social computing & networking, sustainable computing & communications, ISPA/IUCC/ BDCloud/SocialCom/SustainCom. IEEE, pp 215–222
Barber MJ, Clark JW (2009) Detecting network communities by propagating labels under constraints. Phys Rev E 80(2):026129
Liu X, Murata T (2010) Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Stat Mech Appl 389(7):1493–1500
Le BD, Shen H, Nguyen H, Falkner N (2019) Improved network community detection using meta-heuristic based label propagation. Appl Intell 49(4):1451–1466
Zhang W, Zhang R, Shang R, Jiao L (2018) Weighted compactness function based label propagation algorithm for community detection. Physica A: Stat Mech Appl 492:767–780
Lin Z, Zheng X, Xin N, Chen D (2014) Ck-lpa: Efficient community detection algorithm based on label propagation with community kernel. Physica A: Stat Mech Appl 416:386–399
Joghan HS, Bagheri A (2017) Local edge betweenness based label propagation for community detection in complex networks. In: 2017 International Conference on Computational Science and Computational Intelligence (CSCI). IEEE, pp 864–869
Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344 (6191):1492–1496
Bai X, Yang P, Shi X (2017) An overlapping community detection algorithm based on density peaks. Neurocomputing 226:7–15
JIN Z, XU P (2018) An adaptive community detection algorithm of density peak clustering. J Harbin Inst Technol 50(5): 44–51
Xu M, Li Y, Li R, Zou F, Gu X (2019) Eadp: an extended adaptive density peaks clustering for overlapping community detection in social networks. Neurocomputing 337:287–302
Deng ZH, Qiao HH, Gao MY, Song Q, Gao L (2019) Complex network community detection method by improved density peaks model. Physica A: Stat Mech Appl 526:121070
Chen Y, Zhao P, Li P, Zhang K, Zhang J (2016) Finding communities by their centers. Sci Rep 6:24017
Ding J, He X, Yuan J, Chen Y, Jiang B (2018) Community detection by propagating the label of center. Physica A: Stat Mech Appl 503:675–686
Cheng Q, Liu Z, Huang J, Cheng G (2016) Community detection in hypernetwork via density-ordered tree partition. Appl Math Comput 276:384–393
Šubelj L, Bajec M (2011) Robust network community detection using balanced propagation. Eur Phys J B 81(3):353–362
Lü L, Zhang YC, Yeung C H, Zhou T (2011) Leaders in social networks, the delicious case. PloS one 6(6)
You X, Ma Y, Liu Z (2020) A three-stage algorithm on community detection in social networks. Knowl-Based Syst 104822:187
Jiang H, Liu Z, Liu C, Su Y, Zhang X (2020) Community detection in complex networks with an ambiguous structure using central node based link prediction. Knowl-Based Syst:105626
Frey BJ, Dueck D (2007) Clustering by passing messages between data points. Ence 315 (5814):972–976
Hubert L, Arabie P (1985) Comparing partitions. J Class 2(1):193–218
Danon L, Diaz-Guilera A, Duch J, Arenas A (2005) Comparing community structure identification. J Stat Mech Theory Exper 2005(09):P09008
Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110
Derrac J, Garcia S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3–18
Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473
Lusseau D (2003) The emergent properties of a dolphin social network. Proc R Soc Lond Ser B Biol Sci 270(suppl_2):S186–S188
Adamic LA, Glance N (2005) The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd international workshop on Link discovery, pp 36–43
Knuth D E (1993) The stanford graphbase: a platform for combinatorial algorithms. In: SODA, vol 93, pp 41–43
Watts DJ, Strogatz SH (1998) Collective dynamics of ’small-world’networks. Nature 393 (6684):440–442
Jure L, Jon K, Christos F (2007) Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data
Guo C, Wang J, Zhang Z (2014) Evolutionary community structure discovery in dynamic weighted networks. Physica A Stat Mech Appl 413:565–576
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by the National Natural Science Foundation of China (Nos. 61976182, 61572406, 62076171, 61876157), Key program for International S&T Cooperation of Sichuan Province (2019YFH0097), Sichuan Key R&D project (2020YFG0035).
Rights and permissions
About this article
Cite this article
Li, C., Chen, H., Li, T. et al. A stable community detection approach for complex network based on density peak clustering and label propagation. Appl Intell 52, 1188–1208 (2022). https://doi.org/10.1007/s10489-021-02287-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-021-02287-5