A Label Propagation Algorithm based on Circular Spread

doi:10.23940/ijpe.18.10.p2.22612270

Abstract

Abstract:

A label propagation algorithm has attracted widespread attention in community detection due to its linear time complexity. However, the traditional label propagation algorithm has a strong problem of randomness and may bring in backtracking during the process of label propagation; the result of finding the community is unstable and of low quality. This essay proposes a circular spread label propagation algorithm (CS-LPA), which takes full account of the structural characteristics of the community, introduces node influence measures, and discovers the potential community through the proliferation of labels that integrate the cyclic structure of social network. Finally, experimental results of real datasets show that CS-LPA not only enhances the stability of community detection results, but also effectively improves the quality of community detection.

Submitted on July 10, 2018; Revised on August 14, 2018; Accepted on September 16, 2018
References: 20

Yong Wang, Xinzhen Fang, Jiahao Shi, and Jing Yang. A Label Propagation Algorithm based on Circular Spread [J]. Int J Performability Eng, 2018, 14(10): 2261-2270.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References 0

	J. J. Ma, D. Zeng, and R. A. Huff, “Complex Network Analysis,” Journal of International Technology and Information Management, Vol. 22, No. 4, pp. 99-112, 2013
	P. Bedi and C. Sharma, “Community Detection in Social Networks,” Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, Vol. 6, No. 3, pp. 115-135, 2016
	Z. Dou, B. Zhang, and X. Yu, “A New Alternating Minimization Algorithm for Image Segmentation,” in Proceedings of IET International Conference on Wireless, Mobile and Multi-Media, pp. 248-272, 2016
	L. Bohlin, D. Edler, A Lancichinetti, and M Rosvall, “Community Detection and Visualization of Networks with the Map Equation Framework,” Springer, pp. 3-34, 2014
	M. S. Houston, M. D. Silverstein, and V. J. Suman, “Community-Acquired Lower Respiratory Tract Infection in the Elderly: A Community-based Study of Incidence and Outcome,” Journal of the American Board of Family Practice, Vol. 8, No. 5, pp. 347-356, 2016
	M. Girvan and M. E. J. Newman, “Community Structure in Social and Biological Networks,” in Proceedings of National Academy of Science of the United States of America, Vol. 9, No. 12, pp. 7921-7826, 2002
	M. Gong, B. Fu, L. Jiao, and H. Du, “Memetic Algorithm for Community Detection in Networks,” Physical Review E, Vol. 84, No. 5, pp. 056101, 2011
	A. Clauset, M. E. J. Newman, and C Moore, “Finding Community Structure in Very Large Networks,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 70, No. 6, pp. 066111, 2005
	R. Forster, “Louvain Community Detection with Parallel Heuristics on GPUs,” in Proceedings of IEEE Jubilee International Conference on Intelligent Engineering Systems, pp. 227-232, 2016
	U. N. Raghavan, R. Albert, and S. Kumara, “Near Linear Time Algorithm to Detect Community Structures in Large-Cale Networks,” Physical Review E, Vol. 76, No. 3, pp. 036106, 2007
	A. A. Alkadhmawee and S. Lu, “Prolonging the Network Lifetime based on LPA-Star Algorithm and Fuzzy Logic in Wireless Sensor Network,” in Proceedings of World Congress on Intelligent Control and Automation, pp. 1448-1453, 2016
	Y. Lu, X. Huo, O. Arslan, and P. Tsiotras, “Multi-Scale LPA* with Low Worst-Case Complexity Guarantees,” in Proceedings of IEEE International Conference on Intelligent Robots and Systems, Vol. 10, No. 1, pp. 3507-3512, 2011
	M. Sattari and K. Zamanifar, “A Cascade Information Diffusion based Label Propagation Algorithm for Community Detection in Dynamic Social Networks,” Journal of Computational Science, Vol. 25, No. 3, pp. 122-133, 2018
	Y. X. Zhao, S. H. Li, and X. Z. Chen, “Community Detection using Label Propagation in Entropic Order,” in Proceedings of IEEE International Conference on Computer and Information Technology, pp. 18-24, 2012
	M. J. Barber and J. W. Clark, “Detecting Network Communities by Propagating Labels under Constraints,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 80, No. 2, pp. 026129, 2009
	S. Xu and P. Wang, “Identifying Important Nodes by Adaptive LeaderRank,” Physica A: Statistical Mechanics & Its Applications, pp. 469:654-664, 2017
	Q. Su, K. Yang, and N. Zhang, “Comparative Research on LeaderRank and PageRank Algorithms,” Information Technology, No. 4, pp. 8-11, 2015
	M. E. Newman, “Fast Algorithm for Detecting Community Structure in Networks,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 69, No. 6, pp. 066133, 2004
	P. A. Estévez, M. Tesmer, C. A. Perez, and J. M. Zurada, “Normalized Mutual Information Feature Selection,” IEEE Transactions on Neural Networks, Vol. 20, No. 2, pp. 189-201, 2009
	A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark Graphs for Testing Community Detection Algorithms,” Physical Review E Statistical Nonlinear & Soft Matter Physics, Vol. 78, No. 4, pp. 046110, 2008