Community detection in complex networks using a new agglomerative approach

Complex networks are used for the representation of complex systems such as social networks. Graph analysiscomprises various tools such as community detection algorithms to uncover hidden data. Community detection aims todetect similar subgroups of networks that have tight interconnections with each other while, there is a sparse connectionamong different subgroups. In this paper, a greedy and agglomerative approach is proposed to detect communities. Theproposed method is fast and often detects high-quality communities. The suggested method has several steps. In thefirst step, each node is assigned to a separated community. In the second step, a vertex is selected randomly and then itsneighbors are determined. Then the selected node and its best neighbor will be merged if their merging brings positivegain. The merging of the selected vertex and its best neighbor has more gain than other neighbors. Whenever the mergingoccurs, the graph will be updated and this process will be continued until all the vertexes are assessed. Furthermore,the computational complexity of the proposed method is O(nm), where n and m refer to the total number of vertexesand edges, respectively. In addition, our proposed method is compared with the Girvan–Newman algorithm and thefast divisive method for community detection. Results show that the proposed method is much faster than them andcan detect high-quality communities. Finally, the accuracy of the proposed method is evaluated by using four differentmeasures of purity, F-measure, NMI, and ARI.

PDF

___

[1] Mochón MC. Social network analysis and big data tools applied to the systemic risk supervision. International Journal of Interactive Multimedia and Artificial Intelligence 2016; 3 (6): 34-37. doi: 10.9781/ijimai.2016.365
[2] Lee H, Shao B, Kang U. Fast graph mining with HBase. Information Sciences 2015; 315: 56-66. doi:10.1016/j.ins.2015.04.016
[3] Tasgin M, Bingol H. Community detection in complex networks using genetic algorithm. In: Proceedings of the European Conference on Complex Systems; 2006
[4] Newman ME. Fast algorithm for detecting community structure in networks. Physical Review 2004; 69 (6): 066133. doi: 10.1103/PhysRevE.69.066133
[5] Gosak M, Markovič R, Dolenšek J, Rupnik MS, Marhl M et al. Network science of biological systems at different scales: a review. Physics of Life Reviews 2018; 24: 118-135. doi: 10.1016/j.plrev.2017.11.003
[6] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the USA 2004; 101(9): 2658-2663. doi: 10.1073/pnas.0400054101
[7] Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008; 2008 (10): 10008. doi:1742-5468/2008/10/P10008
[8] Clauset A, Newman M E, Moore C. Finding community structure in very large networks. Physical Review E 2004; 70 (6): 066111. doi:10.1103/PhysRevE.70.066111
[9] Tan F, Xia Y, Zhu B. Link prediction in complex networks: a mutual information perspective. A mutual information perspective. PLoS One 2014; 9 (9): 107056. doi: 10.1371/journal.pone.0107056
[10] Moghaddam A. Detection of malicious user communities in data networks. MSc, University of Victoria, Victoria, Canada, 2011.
[11] Jalili M, Perc M. Information ascades in complex networks. Journal of Complex Networks 2017; 5 (5): 665-693. doi: 10.1093/comnet/cnx019
[12] Fortunato S. Community detection in graphs. Physics Reports 2010; 486 (3-5): 75-174. doi: 10.1016/j.physrep.2009.11.002
[13] Zeng J, Hongfeng Y. A study of graph partitioning schemes for parallel graph community detection. Parallel Computing 2016; 58: 131-139. doi: 10.1016/j.parco.2016.05.008
[14] Harenberg S, Bello G, Gjeltema L, Ranshous S, Harlalka J et al. Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics 2014; 6 (6): 426-439. doi: 10.1002/wics.1319
[15] Arasteh M, Alizadeh S. A fast divisive community detection algorithm based on edge degree betweenness centrality. Applied Intelligence 2019; 49 (2): 689-702. doi: 10.1007/s10489-018-1297-9
[16] Pan Y, Li DH, Liu JG, Liang JZ. Detecting community structure in complex networks via node similarity. Physica A 2010; 389 (14): 2849-2857. doi: 10.1016/j.physa.2010.03.006
[17] Schaeffer SE. Graph clustering. Computer Science Review 2007; 1 (1): 27-64. doi: 10.1016/j.cosrev.2007.05.001
[18] Kernighan BW. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal 1970; 49 (2): 291-307. doi: 10.1002/j.1538-7305.1970.tb01770.x
[19] Suaris PR, Kedem G. An algorithm for quadrisection and its application to standard cell placement. IEEE Transactions on Circuits and Systems 1988; 35 (3): 294-303. doi: 10.1109/31.1742
[20] Girvan M, Newman ME. Community structure in social and biological networks. Proceedings of the National Academy of Sciences USA 2002; 99 (12): 7821-7826. doi: 10.1073/pnas.122653799
[21] Newman ME. Analysis of weighted networks. Physical Review E 2004; 70 (5): 056131. doi: 10.1103/PhysRevE.70.056131
[22] Newman M, Girvan M. Finding and evaluating community structure in networks. Physical Review E 2004; 69 (2): 026113. doi: 10.1103/PhysRevE.69.026113
[23] Estrada E. Virtual identification of essential proteins within the protein interaction network of yeast. Proteomics 2006; 6 (1): 35-40. doi: 10.1002/pmic.200500209
[24] Hurajová JC, Madaras T. Revising the Newman-Girvan algorithm. In: CEUR Workshop Proceedings of the 16th ITAT Conference Information Technologies - Applications and Theory; Tatranské Matliare, Slovakia; 2016. pp. 200–205.
[25] Newman M. Fast algorithm for detecting community structure in networks. Physical Review E 2004; 69 (6): 066133. doi: 10.1103/PhysRevE.69.066133
[26] Fiedler M. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 1973; 23 (2): 298-305. doi: dml.cz/dmlcz/101168
[27] Guimera R, Sales-Pardo M, Amaral LAN. Modularity from fluctuations in random graphs and complex networks. Physical Review E 2004; 70 (2): 025101. doi: 10.1103/PhysRevE.70.025101
[28] Massen CP, Doye JP. Identifying communities within energy landscapes. Physical Review E 2005; 71 (4): 046101. doi: 10.1103/PhysRevE.71.046101
[29] Duch J, Arenas A. Community detection in complex networks using extremal optimization. Physical Review E 2005; 72 (2): 027104. doi: 10.1103/PhysRevE.72.027104
[30] Derényi I, Palla G, Vicsek T. Clique percolation in random networks. Physical Review Letters 2005; 94 (16): 160202. doi: 10.1103/PhysRevLett.94.160202
[31] Shang R, Bai J, Jiao L, Jin C. Community detection based on modularity and an improved genetic algorithm. Physica A 2013; 392 (5): 1215-1231. doi: 10.1016/j.physa.2012.11.003
[32] Gong M, Cai Q, Chen X, Ma L. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Transactions on Evolutionary Computation 2014; 18 (1): 82-97. doi: 10.1109/TEVC.2013.2260862
[33] Pizzuti C. GA-Net: A genetic algorithm for community detection in social networks. In: Parallel Problem Solving from Nature (PPSN), Lecture Notes in Computer Science; 2008. pp. 1081-1090. doi:10.1007/978-3-540-87700-4_107
[34] Gong M, Fu B, Jiao L, Du H. Memetic algorithm for community detection in networks. Physical Review E 2011; 84 (5): 056101. doi: 10.1103/PhysRevE.84.056101
[35] Pizzuti C. A multiobjective genetic algorithm to find communities in complex networks. IEEE Transactions on Evolutionary Computation 2012; 16 (3): 418-430. doi: 10.1109/TEVC.2011.2161090
[36] Shi C, Yan Z, Cai Y, Wu B. Multi-objective community detection in complex networks. Applied Soft Computing 2012; 12 (2): 850-859. doi: 10.1016/j.asoc.2011.10.005
[37] Gong M, Ma L, Zhang Q, Jiao L. Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Physica A 2012; 391 (15): 4050-4060. doi: 10.1016/j.physa.2012.03.021
[38] Chakraborty T, Dalmia A. Metrics for community analysis: a survey. ACM Computing Surveys 2017; 50 (4): 54. doi: 10.1145/3091106
[39] Wagner S, Wagner D. Comparing Clusterings: An Overview. Karlsuhe, Germany: Universität Karlsruhe, 2007. doi: 10.5445/IR/1000011477