Modelling of Overlapping by Community Detection Algorithms in Social Networks: A Review

Document Type : Computer Article

Authors

1 Department of Computer Engineering and IT, Shahrood University of technology, Shahrood, Iran.

2 Department of Computer Engineering and IT, Shahrood University of Technology, Shahrood, Iran

Abstract

A social network consists of some people who are related to each other through some similarities. The emergence and evolution of these networks and increasing rate of using them is the major cause for social network analysis to be a hot research topic. Using various algorithms, each network can be divided into some communities. So, each community includes some members of the social network. Community detection is one of the most important and fundamental tasks in network analysis. It is a step towards understanding the patterns and characteristics of the complex systems they represent. In this paper, the state of the art algorithms for community detection are categorized into six categories (spectral clustering and centrality, quality function, Label propagation, Structure, Closeness, link clustering) based on their definition of the community and modelling the concept of overlapping (existence of the nodes with membership in multiple communities). Next, these methods are implemented on various datasets and compared to each other. It is obvious from the results of performance measures, even in this small collection of data sets, no algorithm can be considered as the best community detection method for all kinds of networks.

Keywords

Main Subjects


[1] F. Huang, X. Li, S. Zhang and J. Zhang, "Overlapping Community Detection for Multimedia Social Networks", IEEE Transactions on Multimedia, Vol. 92, 2017, pp. 1-3.
[2] A.L. Barabási and R. Albert, "Emergence of scaling in random networks", Science, Vol. 286, 1999, pp. 509-512.
[3] A.L. Barabási and E. Bonabeau, "Scale-free Networks", Scientific American, Vol. 288, 2003, pp. 50-59.
[4] M. Plantié and M. Crampes, "Survey on social community detection", Social media retrieval (Springer), 2013, pp. 65-85.
[5] S. Yang, X. Yang, C. Zhang and E. Spyrou, "Using social network theory for modeling human mobility", IEEE network, Vol. 24, 2010, pp. 6-13.
[6] S. Fortunato, "Community detection in graphs, Physics reports", Vol. 486, 2010, pp. 75-174.
[7] S. Harenberg, G. Bello, L. Gjeltema, S. Ranshous, J. Harlalka and R. Seay, "Community detection in large-scale networks: a survey and empirical evaluation", Wiley Interdisciplinary Reviews: Computational Statistics, Vol. 6, 2014, pp. 426-439.
[8] M. Coscia, F. Giannotti and D. Pedreschi, "A classification for community discovery methods in complex networks", Statistical Analysis and Data Mining, Vol. 4, 2011, pp. 512-546.
[9] I. Psorakis, S. Roberts, M. Ebden and B. Sheldon, "Overlapping community detection using Bayesian non-negative matrix factorization", Physical Review E, Vol. 83. No. 6, 2011, p. 066114.
[10] J.Yang and J. Leskovec, “Overlapping community detection at scale: a nonnegative matrix factorization approach”, in Proceedings of the sixth ACM international conference on Web search and data mining, 2013, pp. 587-596.
[11] M. Girvan and M.E. Newman, "Community structure in social and biological networks", Proceedings of the national academy of sciences, Vol. 99, 2002, pp. 7821-7826.
[12] S. Gregory, “An algorithm to find overlapping community structure in networks”, in Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery, 2007, pp. 91-102.
[13] D. Rhouma and L. Romdhane, "An efficient algorithm for community mining with overlap in social networks", Expert Systems with Applications, Vol. 41, 2014, pp. 4309-4321.
[14] W. Zhi-Xiao, L. Ze-chao, Xiao-fang and T. Jin-hui, "Overlapping community detection based on node location analysis", Knowledge-Based Systems, Vol. 105, 2016, pp. 225-235.
[15] A. Clauset, M.E. Newman and C. Moore, "Finding community structure in very large networks", Physical review E, Vol. 70, 2004, p. 066111.
[16] V.D. Blondel, J. Guillaume, R. Lambiotte and E. Lefebvre, "Fast unfolding of communities in large networks", Journal of statistical mechanics: theory and experiment, 2008, p. 10008.
[17] M. Chen, K. Kuzmin and B.K. Szymanski, “Extension of Modularity Density for overlapping community structure”, in Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2014, pp. 856-863.
[18] S. Kelley, "The existence and discovery of overlapping communities in large-scale networks", PhD Thesis, Rensselaer Polytechnic Institute, NY, 2009.
[19] A. Lancichinetti and S. Fortunato, "Community detection algorithms: a comparative analysis", Physical review E, Vol. 80, 2009, p. 056117.
[20] A. Lancichinetti, F. Radicchi, J.J. Ramasco and S. Fortunato, "Finding statistically significant communities in networks", PloS one, Vol. 6, 2011, p. e18961.
[21] S. Bandyopadhyay, G. Chowdhary and D. Sengupta, "FOCS: Fast Overlapped Community Search", IEEE Transactions on Knowledge and Data Engineering, Vol. 27, 2015, pp. 2974-2985.
[ 22 ] ح. شریف زاده و ن. امجدی، ( 1393)، " مروری بر انواع الگوریتم های فراکاوشی در بهینه سازی"، مجله مدلسازی در مهندسی، دوره 2 ، شماره 38 ، 1393 ، صفحۀ 03 - 27.
[23] C. Pizzuti, “GA-Net: A Genetic Algorithm for Community Detection in Social Networks”, Parallel Problem Solving from Nature, PPSN (Springer), 2008, pp. 1081-1090.
[24] C. Pizzuti, "A Multiobjective Genetic Algorithm to Find Communities in Complex Networks", IEEE Transactions on Evolutionary Computation, Vol. 16, 2012, pp. 418-430.
[25]  ع. نعیمی صدیق، س.ک. چهارسوقی و م. شیخمحمدی شیخ " طراحی مدل هماهنگی در زنجیره تأمین رقابتی با استفاده از رویکرد نظریه بازی با همکاری و بدون همکاری "، مجله مدلسازی در مهندسی، دوره 10، شماره 29 ، 1391 ، صفحۀ 31 - 19.
[26] W. Chen, Z. Liu, X. Sun and Y. Wang, "A game-theoretic framework to identify overlapping communities
in social networks", Data Mining and Knowledge Discovery, Vol. 21, 2010, pp. 224-240.
[27] ا. گلکار و م. کائدی، "ارائه مدلی برای تخمین میزان برونگرایی اعضای شبکه اجتماعی با استفاده از اطلاعات ساختار گراف "
مجله مدلسازی در مهندسی، دوره 13 ، شماره 43 ، 1394 ، صفحۀ 91-106.
[28]  ر. احمدی و س. شیخ احمدی، "پیش بینی افراد خبره در شبکههای اجتماعی آنلاین"، هشتمین کنفرانس بینالمللی فناوری اطلاعات و دانش، دانشگاه بوعلی سینا، همدان، 1395
[29]  ع.ا. طالعی زاده و ز. چراغی، " قیمت گذاری و بازاریابی در یک زنجیره تأمین دوسطحی تحت چهار رویکرد نظریه بازیها "،
مجله مدلسازی در مهندسی، دوره 13 ، شماره 42 ، 1394 ، صفحۀ 135 - 149 .
[30] U.N. Raghavan, R. Albert and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks", Physical review E, Vol. 76, 2007, p. 036106.
[31] S. Gregory, "Finding overlapping communities in networks by label propagation", New Journal of Physics, Vol. 12, 2010, p. 103018.
[32] J. Xie and B.K. Szymanski, “Towards linear time overlapping community detection in social networks”, in Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2012, pp. 25-36.
[33] M. Coscia, G. Rossetti, F. Giannotti and D. Pedreschi, “Demon: a local-first discovery method for overlapping communities”, in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 615-623.
[34] E. Airoldi, D. Blei, S. Fienberg and E. Xing, "Mixed membership stochastic blockmodels", Journal of Machine Learning Research, Vol. 9, 2008, pp. 1981-2014.
[35] A. McDaid and N. Hurley, “Detecting highly overlapping communities with model-based overlapping seed expansion”, in Proceedings of the IEEE/ACM International Conference on Social Networks Analysis and Mining (ASONAM), 2010, pp. 112-119.
[36] J. Whang, D. Gleich and I. Dhillon, "Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion", IEEE Transactions on Knowledge and Data Engineering, Vol. 28, 2016, pp. 1272-1284.
[37] G. Palla, I. Derényi, I. Farkas and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society", Nature, Vol. 435, 2005, pp. 814-818.
[38] H. Shen, X. Cheng, K. Cai and M. Hu, "Detect overlapping and hierarchical community structure in networks", Physica A: Statistical Mechanics and its Applications, Vol. 388, 2010, pp. 1706-1712.
[39] C. Lee, F. Reid, A. McDaid and N. Hurley, "Detecting highly overlapping community structure by greedy clique expansion", arXiv preprint:1002.1827, 2010.
[40] P. Pons and M. Latapy, “Computing communities in large networks using random walks”, International Symposium on Computer and Information Sciences, 2005, pp. 284-293.
[41] M. Rosvall and C. Bergstrom, "Maps of random walks on complex networks reveal community structure", Proceedings of the National Academy of Sciences, Vol. 105, 2008, pp. 1118-1123.
[42] D. Jin, B. Yang, C. Baquero, D. Liu, D. He and J. Liu, "A Markov random walk under constraint for discovering overlapping communities in complex networks", Journal of Statistical Mechanics: Theory and Experiment, 2011, p. P05031.
[43] T. Evans and R. Lambiotte, "Line graphs, link partitions, and overlapping communities", Physical Review E, Vol. 80, 2009, p. 016105.
[44] Y.Y. Ahn, J.P. Bagrow and S. Lehmann, "Link communities reveal multiscale complexity in networks", Nature, Vol. 466. 2010, pp. 761-764.
[45] G. Palla, I. Farkas, P. Pollner, I. Derenyi, and T Vicsek, "Directed network modules", New Journal of Physics, Vol. 9, 2007, p. 186.
[46] I. Farkas, D. Ábel, G. Palla and T. Vicsek, "Weighted network modules", New Journal of Physics, Vol. 9, 2007, p. 180.
[47] J. Kunegis, “Konect: the koblenz network collection”, 22nd International Conference on World Wide Web, 2013, pp. 1343-1350.
[48] J. Leskovec and R. Sosič, "SNAP: A general-purpose network analysis and graph-mining library", ACM Transactions on Intelligent Systems and Technology, Vol. 8, 2016, pp. 1-20.
[49] M. Bastian, S. Heymann and M. Jacomy, “Gephi: open source software for exploring and manipulating networks”, in Proceedings of the International Conference on Weblogs and Social Media, Vol. 8, 2009, pp. 361-362.
[50] J. Leskovec, K. Lang and M. Mahoney, “Empirical comparison of algorithms for network community detection”, in Proceedings of the 19th international conference on World Wide Web, 2010, pp. 631-640.