Using Prior Knowledge for Community Detection by Label Propagation Algorithm

Abstract:

Community detection is an important approach to analyze and understand the organization or unit structure of the complex networks. By comparing the existing community detection algorithms, the label propagation algorithm (LPA) shows prominent operation speed and qualifies near linear time complexity. However, original LPA algorithm only uses the topological structure to guide the community detection process, failing to improve the quality of community detection when extra information offered. In this paper, we combine the prior information with topological structure to guide the community detection process. During the label propagation process, we proposed a new label update principle, making a node absorb its neighbor label information depending on the label distribution. The experimental results both on real networks and artificial networks show that the improved algorithm not only inherits the characteristic of rapid speed, but also improves the quality of community detection. Moreover, the improved algorithm still has the feature of near linear time complexity.

• Periodical: Advanced Materials Research (Volumes 1049-1050)
• Pages: 1566-1571
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.1049-1050.1566
• Online since: October 2014
• Authors: Yi Bo Wang, Wen Jun Wang*, Dong Liu, Xiao Liu, Peng Fei Jiao
• Keywords: Community Detection, Label Propagation, Prior Information

References

[1] Raghavan, Usha Nandini, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks., Physical Review E 76. 3 (2007): 036106.

DOI: 10.1103/physreve.76.036106

[2] Fortunato, Santo. Community detection in graphs., Physics Reports 486. 3 (2010): 75-174.

[3] Barber, Michael J., and John W. Clark. Detecting network communities by propagating labels under constraints., Physical Review E 80. 2 (2009): 026129.

DOI: 10.1103/physreve.80.026129

[4] Gregory, Steve. Finding overlapping communities in networks by label propagation., New Journal of Physics 12. 10 (2010): 103018.

DOI: 10.1088/1367-2630/12/10/103018

[5] Allahverdyan, Armen E., Greg Ver Steeg, and Aram Galstyan. Community detection with and without prior information., EPL (Europhysics Letters) 90. 1 (2010): 18002.

DOI: 10.1209/0295-5075/90/18002

[6] Danon, Leon, et al. Comparing community structure identification., Journal of Statistical Mechanics: Theory and Experiment 2005. 09 (2005): P09008.

DOI: 10.1088/1742-5468/2005/09/p09008

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

DOI: 10.1086/jar.33.4.3629752

[8] Girvan, Michelle, and Mark EJ Newman. Community structure in social and biological networks., Proceedings of the National Academy of Sciences99. 12 (2002): 7821-7826.

[9] Lancichinetti, Andrea, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms., Physical Review E 78. 4 (2008): 046110.

DOI: 10.1103/physreve.78.046110