Overlapping Community Discovery Based on Node Hierarchy and Label Propagation Gain
CHEN Yu-Zhong, SHI Song, CHEN Guo-Long, YU Zhi-Yong
1.College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108 2.Fujian Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350108
Abstract The time complexity of multi-label propagation algorithm (MLPA) is nearly linear. However, when it is applied to overlapping community discovery, the accuracy and the stability of MLPA are poor. Inspired by the idea that overlapping nodes are more probable to appear in the boundary regions of different communities, an overlapping community discovery algorithm based on node hierarchy and label propagation gain is proposed in this paper. Firstly, the improved single label propagation with node centrality and community distribution constraints is utilized to unfold preliminary non-overlapping communities and centrality values of nodes are calculated by local information in the propagation process simultaneously. Furthermore, node hierarchy partition function is defined according to centrality values of nodes and employed to mark the hierarchy of each node in its respective community. Finally, based on the label propagation gain among nodes, a new multi-label updating rule is designed to obtain the final overlapping communities. Extensive experimental results on synthetic and real-world networks validate that the proposed algorithm effectively improves the accuracy and stability.
[1] Xie J R, Kelley S, Szymanski B K. Overlapping Community Detection in Networks: The State-of-the-Art and Comparative Study. ACM Computing Surveys, 2013, 45(4): 1-35 [2] Palla G, Derényi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 2005, 435: 814-818
[3] Zhu M, Meng F R, Zhou Y. Density-Based Link Clustering Algorithm for Overlapping Community Detection. Journal of Computer Research and Development, 2013, 50(12): 2520-2530 (in Chinese) (朱 牧,孟凡荣,周 勇.基于链接密度聚类的重叠社区发现算法.计算机研究与发展, 2013, 50(12): 2520-2530) [4] Zhang Z H, Miao D Q, Qian J. Detecting Overlapping Communities with Heuristic Expansion Method Based on Rough Neighborhood. Chinese Journal of Computers, 2013, 36(10): 2078-2086 (in Chinese) (张泽华,苗夺谦,钱 进.邻域粗糙化的启发式重叠社区扩张方法.计算机学报, 2013, 36(10): 2078-2086) [5] Wang W J, Liu D, Liu X, et al. Fuzzy Overlapping Community Detection Based on Local Random Walk and Multidimensional Scaling. Physica A: Statistical Mechanics and Its Applications, 2013, 392(24): 6578-6586 [6] Gregory S. Finding Overlapping Communities in Networks by Label Propagation. New Journal of Physics, 2010. DOI: 10.1088/1367-2630/12/10/103018 [7] Raghavan U N, Albert R, Kumara S. Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0709.2938.pdf [8] Xie J R, Szymanski B K, Liu X M. SLPA: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process // Proc of the 11thInternational Conference on Data Mining. Vancouver, Canada, 2011: 344-349 [9] Dai Q G, Guo M Z, Liu Y, et al. MLPA: Detecting Overlapping Communities by Multi-label Propagation Approach // Proc of theCongress on Evolutionary Computation. Cancun, Mexico, 2013: 681-688 [10] Page L, Brin S, Motwani R, et al. The PageRank Citation Ranking: Bringing Order to the Web[EB/OL]. [2014-04-20]. http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf [11] Barber M J, Clark J W. Detecting Network Communities by Propagating Labels under Constraints. Physcial Review E[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0903.3138.pdf [12] Liu X, Murata T. Advanced Modularity-Specialized Label Propagation Algorithm for Detecting Communities in Networks[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0910.1154.pdf [13] ubelj L, Bajec M. Unfolding Network Communities by Combining Defensive and Offensive Label Propagation // Proc of the ECML PKDD Workshop on the Analysis of Complex Networks. Barcelona, Spain, 2010: 87-104 [14] Lancichinetti A, Fortunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0805.4770v4.pdf [15] Danon L, Diaz-Guilera A, Duch J, et al. Comparing Community Structure Identification[EB/OL]. [2014-04-20]. http://deim.urv.cat/~alexandre.arenas/publicacions/pdf/jstat05.pdf [16] Nicosia V, Mangioni G, Carchiolo V, et al. Extending the Definition of Modularity to Directed Graphs with Overlapping Communities[EB/OL]. [2014-04-20]. http://arxiv.org/pdf/0801.1647.pdf
2015, Vol. 28 
