Username   Password       Forgot your password?  Forgot your username? 


A Label Propagation Algorithm based on Circular Spread

Volume 14, Number 10, October 2018, pp. 2261-2270
DOI: 10.23940/ijpe.18.10.p2.22612270

Yong Wang, Xinzhen Fang, Jiahao Shi, and Jing Yang

College of Computer Science and Technology, Harbin Engineering University, Harbin, 150001, China

(Submitted on July 10, 2018; Revised on August 14, 2018; Accepted on September 16, 2018)


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.


References: 20

                1. 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
                2. 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
                3. 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
                4. 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
                5. 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
                6. 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
                7. 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
                8. 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
                9. 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
                10. 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
                11. 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
                12. 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
                13. 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
                14. 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
                15. 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
                16. S. Xu and P. Wang, “Identifying Important Nodes by Adaptive LeaderRank,” Physica A: Statistical Mechanics & Its Applications, pp. 469:654-664, 2017
                17. Q. Su, K. Yang, and N. Zhang, “Comparative Research on LeaderRank and PageRank Algorithms,” Information Technology, No. 4, pp. 8-11, 2015
                18. 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
                19. 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
                20. 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


                              Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

                              Download this file (IJPE-2018-10-02.pdf)IJPE-2018-10-02.pdf[A Label Propagation Algorithm based on Circular Spread]465 Kb
                              This site uses encryption for transmitting your passwords.