A Distributed Approach to Community Detection in Large Social Networks Based on Label Propagation

Document Type : Original Article

Authors

1 shahed university

2 Computer Engineering Department, Shahed University, Tehran, Iran. Acoustic Research Center , Shahed University, Tehran, Iran.

Abstract

Detection of overlapping communities in large complex social networks with intelligent agents, is an NP problem with great time complexity and large memory usage and no simultaneous online solution.           Proposing a novel distributed label propagation approach can help to decrease the searching time and reduce the memory space usage. This paper presents a scalable distributed overlapping community         detection approach based on the label propagation method by proposing a novel algorithm and three new metrics to expand scalability and improve modularity through agent-based implementation and good memory allocation in a multi-core architecture. The experimental results of large real datasets over the state-of-the-art SLPA approach show that the execution time speeds up by 900% and the modularity improves by 3% to 100% thus producing fast and accurate detection of overlapped communities.
 

Keywords

References

[1]     T. Aynaud and J. L. Guillaume, “Multi-step community detection and hierarchical time segmentation in evolving networks,” Proceedings of the 5th SNA-KDD workshop, 2011.##
[2]     W. M. Campbell, C. K. Dagli, and C. J. Weinstein, “Social Network Analysis with Content and Graphs,” Lincoln Laboratory Journal, vol. 20, no. 1, 2013.##
[3]     Y.-Y. Ahn, J. P. Bagrow, and S. J. n. Lehmann, “Link communities reveal multiscale complexity in networks,” vol. 466, no. 7307, p. 761, 2010.##
[4]     L. Tang and H. Liu, “Community detection and mining in social media,” Synthesis Lectures on Data Mining and Knowledge Discovery, vol. 2, no. 1, pp. 130-137, 2010.##
[5]     [5] Y. Cohen, D. Hendler, and A. Rubin, “Node-centric detection of overlapping communities in social networks,” International Conference and School on Network Science, pp. 1-10, 2017.##
[6]     [6] M. Brutz and F. G. Meyer, “A Modular Multiscale Approach to Overlapping Community Detection,” arXiv preprint arXiv: 1501.05623, 2015.##
[7]     [7] U. N. Raghavan, R. Albert, and S. J. P. E. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Phys. Rev. E., vol. 76, no. 3, p. 036106, Sep 2007.##
[8]     [8] M. J. Barber and J. W. J. P. R. E. Clark, “Detecting network communities by propagating labels under constraints,” Phys. Rev. E., vol. 80, no. 2, p. 026129, Aug. 2009.##
[9]     [9] X. Liu, T. J. P. A. S. M. Murata, and I. Applications, “Advanced modularity-specialized label propagation algorithm for detecting communities in networks,” Physica A: Statistical Mechanics and its Applications, vol. 389, no. 7, pp. 1493-1500, 2010.##
[10]  C. L. Staudt and H. Meyerhenke, “Engineering parallel algorithms for community detection in massive networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 1, pp. 171-184, 2016.##
[11]  S. Moon, J.-G. Lee, M. Kang, M. Choy, and J. w. Lee, “Parallel community detection on large graphs with MapReduce and GraphChi,” Data & Knowledge Engineering, vol. 104, pp. 17-34, 2016.##
[12]  C. Li, Y. Tang, H. Lin, C. Yuan, and H. Mai, “Parallel overlapping community detection algorithm in complex networks based on label propagation,” SCIENTIA SINICA Informationis, vol. 46, no. 2, pp. 212-227, 2016.##
[13]  K. Kuzmin, S. Y. Shah, and B. K. Szymanski, “Parallel overlapping community detection with SLPA,” International Conference on Social Computing. IEEE, pp. 204-212, 2013.##
[14]  Q. Yuchen, W. Haixia, and W. Dongsheng, “Parallelizing and optimizing overlapping community detection with speaker-listener Label Propagation Algorithm on multi-core architecture,” IEEE 2nd International Conference on Cloud Computing and Big Data Analysis (ICCCBDA), pp. 439-443, 2017.##
[15]  A. Kukanov and M. J. J. I. T. J. Voss, “The Foundations for Scalable Multi-Core Software in Intel Threading Building Blocks,” Intel Technology Journal, vol. 11, no. 4, 2007.##
[16]  S. Kim, “Community Detection in Directed Networks and its Application to Analysis of Social Networks,” Dissertation, The Ohio State University, 2014.##
[17]  S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3-5, pp. 75-174, 2010.##
[18]  J. Su and T. C. Havens, “Fuzzy community detection in social networks using a genetic algortihm,” International Conference on Fuzzy Systems IEEE, pp. 2039-2046, 2014.##
[19]  B. Adamcsek, G. Palla, I. J. Farkas, I. Derenyi, and T. Vicsek, “CFinder: locating cliques and overlapping modules in biological networks,” Bioinformatics, vol. 22, no. 8, pp. 1021-1023, 2006.##
[20]  S. Gregory,“ Finding overlapping communities in networks by label propagation,” New Journal of Physics, vol. 12, no. 10, p. 103018, 2010.##
[21]  S. Gregory, “An algorithm to find overlapping community structure in networks,” European Conference on Principles of Data Mining and Knowledge Discovery, pp. 91-102, Springer 2007.##
[22]  H. Shen, X. Cheng, K. Cai, and M. B. Hu,“ Detect overlapping and hierarchical community structure in networks,” Physica A: Statistical Mechanics and its Applications, vol. 388, no. 8, pp. 1706-1712, 2009.##
[23]  J. Yang and J. Leskovec, “Defining and evaluating network communities based on ground-truth,” Knowledge and Information Systems, vol. 42, no. 1, pp. 181-213, 2013.##
[24]  W. Liu, X. Jiang, M. Pellegrini, and X. J. S. r. Wang, “Discovering communities in complex networks by edge label propagation,” Scientific Reports 6.1, vol. 6, no. 1, pp. 1-10, 2016.##
[25]  J. J. Whang, D. F. Gleich, and I. S. Dhillon, “Overlapping community detection using neighborhood-inflated seed expansion,” IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 5, pp. 1272-1284, 2016.##
[26]  V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008.##

Files

History

  • Receive Date: 25 April 2021
  • Accept Date: 25 April 2021
  • Publish Date: 25 April 2021

Share

How to cite

Statistics