Abstract
Community structure is one of the most best-known properties of complex networks. Finding communities help us analyze networks from a mesoscopic viewpoints instead of microscopic or macroscopic one. It helps to understand behavior grouping. Various community detection algorithms have been proposed with some shortcomings in time and space complexity, accuracy, or stability. Label Propagation Algorithm (LPA) is a popular method used for finding communities in an almost-linear time-consuming process. However, its performance is not satisfactory in some metrics such as accuracy and stability. In this paper, a new modified version of LPA is proposed to improve the stability and accuracy of the LPA by defining two concepts -nodes and link strength based on semi-local similarity-, while preserving its simplicity. In the proposed method a new initial node selection strategy, namely the tiebreak strategy, updating order and rule update are presented to solve the random behavior problem of original LPA. The proposed algorithm is evaluated on artificial and real networks. The experiments show that the proposed algorithm is close to linear time complexity with better accuracy than the original LPA and other compared methods. Furthermore, the proposed algorithm has the robustness and stability advantages while the original LPA does not have these features.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Newman Mark E J, The structure and function of complex networks, SIAM Review, 2003, 45(2): 167–256.
Scott J, Social Network Analysis, 4th Edition, SAGE Publications, London, UK, 2017.
Dorogovtsev S and Mendes J, Evolution of Networks: From Biological Networks to the Internet and WWW, Oxford University Press, Oxford, 2003.
Andrei B, Ravi K, Farzin M, et al., Graph structure in the web, Computer Networks, 2000, 33(1): 309–320.
Roger G and Nunes A L A, Modeling the world-wide airport network, The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2): 381–385.
Roger G and Nunes A L A, Functional cartography of complex metabolic networks, Nature, 2005, 433(7028): 895–900.
Romualdo P S and Alessandro V, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, Cambridge, 2007.
Bullmore E and Sporns O, Complex brain networks: Graph theoretical analysis of structural andfunctional systems, Nature Reviews Neuroscience, 2009, 10(4): 312–312.
Jackson M O, Social and Economic Networks, Princeton University Press, Princeton, 2010.
Réka A and Albert-László B, Statistical mechanics of complex networks, Reviews of Modern Physics, 2002, 74(1): 47.
Costa L da F, Francisco A R, Gonzalo T, et al., Characterization of complex networks: A survey of measurements, Advances in Physics, 2007, 56(1): 167–242.
Santo F, Community detection in graphs, Physics Reports, 2010, 486(3): 75–174.
Michele C, Fosca G, and Dino P, A classification for community discovery methods in complex networks, Statistical Analysis and Data Mining: The ASA Data Science Journal, 2011, 4(5): 512–546.
Shi G, Fabio P, Matthew C, et al., Controllability of structural brain networks, Nature Communications, 2015, 6: 8414, DOI: 10.1038/ncomms9414.
Michelle G and Newman Mark E J, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, 2002, 99(12): 7821–7826.
Nandini R U, Réka A, and Soundar K, Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 2007, 76(3): 036106.
Leung Ian X Y, Pan H, Pietro L, et al., Towards real-time community detection in large networks, Physical Review E, 2009, 79(6): 066107.
Liu X and Tsuyoshi M, Advanced modularity-specialized label propagation algorithm for detecting communities in networks, Physica A: Statistical Mechanics and Its Applications, 2010, 389(7): 1493–1500.
Šubelj L and Bajec M, Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction, Physical Review E, 2011, 83(3): 036103.
Filippo R, Claudio C, and Federico C, et al., Defining and identifying communities in networks, Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658–2663.
Santo F, Vito L, and Massimo M, Method to find community structures based on information centrality, Physical Review E, 2004, 70(5): 056104.
Newman M E, Fast algorithm for detecting community structure in networks, Physical Review E, 2004, 69(6): 066133.
Clauset A, Newman Mark E J, and Moore C, Finding community structure in very large networks, Physical Review E, 2004, 70(6): 066111.
Blondel V D, Guillaume J L, Lambiotte R, et al., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
Fortunato S and Barthélemy M, Resolution limit in community detection, Proceedings of the National Academy of Sciences, 2007, 104(1): 36–41.
Pons P and Latapy M, Computing communities in large networks using random walks, ISCIS, 2005, 3733: 284–293.
Shon H S, Kin S, Rhee C S, et al., Clustering DNA Microarray Data by MCL Algorithm, ISMB 2007
Rosvall M and Bergstrom C T, Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences, 2008, 105(4): 1118–1123.
Sun H L, Liu J, Huang J B, et al., CenLP: A centrality-based label propagation algorithm for community detection in networks, Physica A: Statistical Mechanics and Its Applications, 2015, 436: 767–780.
Barber M J and Clark J W, Detecting network communities by propagating labels under constraints, Physical Review E, 2009, 80(2): 026129.
Xie J R and Szymanski B K, Labelrank: A stabilized label propagation algorithm for community detection in networks, Network Science Workshop (NSW), 2013 IEEE 2nd, 2013, 138–143.
Lou H, Li S H, and Zhao Y X, Detecting community structure using label propagation with weighted coherent neighborhood propinquity, Physica A: Statistical Mechanics and Its Applications, 2013, 392(14): 3095–3105.
Liang Z W, Li J P, Yang F, et al., Detecting community structure using label propagation with consensus weight in complex network, Chinese Physics B, 2014, 23(9): 098902.
Lin Z, Zheng X L, Xin N, et al., CK-LPA: Efficient community detection algorithm based on label propagation with community kernel, Physica A: Statistical Mechanics and Its Applications, 2014, 416: 386–399.
Liu X, Xie Z, and Yi D Y, Community detection by neighborhood similarity, Chinese Physics Letters, 2012, 29(4): 048902.
Scripps J, Tan P N, and Esfahanian A H, Node roles and community structure in networks, Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 Workshop on Web Mining and Social Network Analysis, 2007, 26–35.
Žalik K R, Maximal neighbor similarity reveals real communities in networks, Scientific Reports, 2015, 5: 18374.
Lancichinetti A, Fortunato S, and Radicchi F, Benchmark graphs for testing community detection algorithms, Physical Review E, 2008, 78(4): 046110.
Zachary W W, An information flow model for conflict and fission in small groups, 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, Behavioral Ecology and Sociobiology, 2003, 54(4): 396–405.
Newman M E and Girvan M, Finding and evaluating community structure in networks, Physical Review E, 2004, 69(2): 026113.
Gleiser P M and Danon L, Community structure in jazz, Advances in Complex Systems, 2003, 6(4): 565–573.
Jordi D and Alex A, Community detection in complex networks using extremal optimization, Physical Review E, 2005, 72(2): 027104.
Roger G, Leon D N, and Albert D G, Self-similar community structure in a network of human interactions, Physical Review E, 2003, 68(6): 065103.
Newman M E J, Finding community structure in networks using the eigenvectors of matrices, Physical Review E, 2006, 74(3): 036104
Watts D J and Strogatz S H, Collective dynamics of “small-world” networks, Nature, 1998, 393(6684): 440–442.
Leon D N, Albert D G, Jordi D, et al., Comparing community structure identification, Journal of Statistical Mechanics: Theory and Experiment, 2005, 2055(9): P09008.
Network data, www-personal.umich.edu/mejn/netdata/.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was recommended for publication by Editor LÜ Jinhu.
Rights and permissions
About this article
Cite this article
Berahmand, K., Bouyer, A. A Link-Based Similarity for Improving Community Detection Based on Label Propagation Algorithm. J Syst Sci Complex 32, 737–758 (2019). https://doi.org/10.1007/s11424-018-7270-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-018-7270-1