Volume 4, Issue 2, March 2016, Page: 13-18
A Fast Method for Community Detection Based on Compressing Networks
Jialin He, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China; Big Data Research Center, University of Electronic Science and Technology of China, Chengdu, China
Duanbing Chen, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China; Big Data Research Center, University of Electronic Science and Technology of China, Chengdu, China
Chongjing Sun, Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China; Big Data Research Center, University of Electronic Science and Technology of China, Chengdu, China
Received: Apr. 15, 2016;       Published: Apr. 16, 2016
DOI: 10.11648/j.se.20160402.12      View  2864      Downloads  61
Abstract
Community structure is one of important characteristics in complex networks and contributes to the understanding of function in corresponding complex systems. Many methods based on modularity optimization have been proposed in the past few years. To obtain a good community partition, they must maximize the modularity from scratch, which have low efficiency. In this paper, we suggest a novel method which first constructs a small network according to connection strength index and then uses Blondel method to detect communities. Experimental results on real and synthetic networks show that compared with the traditional method our method can not only maintain the quality of communities but also improve the efficiency greatly.
Keywords
Complex Networks, Community Structure, Modularity Optimization, Connection Strength, Small Network
To cite this article
Jialin He, Duanbing Chen, Chongjing Sun, A Fast Method for Community Detection Based on Compressing Networks, Software Engineering. Vol. 4, No. 2, 2016, pp. 13-18. doi: 10.11648/j.se.20160402.12
Reference
[1]
Albert R, Barabási A L. Statistical mechanics of complex networks [J]. Reviews of Modern Physics, 2002, 74(1): 47.
[2]
Dorogovtsev S N, Mendes J F F. Evolution of networks [J]. Advances in Physics, 2002, 51(4): 1079-1187.
[3]
Boccaletti S, Latora V, Moreno Y, et al. Complex networks: Structure and dynamics [J]. Physics Reports, 2006, 424(4): 175-308.
[4]
Newman M E J. The structure and function of complex networks [J]. SIAM Review, 2003, 45(2): 167-256.
[5]
Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology [C]// ACM SIGCOMM Computer Communication Review. ACM, 1999, 29(4): 251-262.
[6]
Newman M E J. The structure of scientific collaboration networks [J]. Proceedings of the National Academy of Sciences, 2001, 98(2): 404-409.
[7]
Zachary W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropological Research, 1977: 452-473.
[8]
Girvan M, Newman M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[9]
Fortunato S. Community detection in graphs [J]. Physics Reports, 2010, 486(3): 75-174.
[10]
Malliaros F D, Vazirgiannis M. Clustering and community detection in directed networks: A survey [J]. Physics Reports, 2013, 533(4): 95-142.
[11]
Porter M A, Onnela J P, Mucha P J. Communities in networks [J]. Notices of the AMS, 2009, 56(9): 1082-1097.
[12]
Newman M E J. Communities, modules and large-scale structure in networks [J]. Nature Physics, 2012, 8(1): 25-31.
[13]
Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks [J]. Physical Review E, 2004, 70(2): 025101.
[14]
Duch J, Arenas A. Community detection in complex networks using extremal optimization [J]. Physical Review E, 2005, 72(2): 027104.
[15]
Newman M E J. Fast algorithm for detecting community structure in networks [J]. Physical review E, 2004, 69(6): 066133.
[16]
Clauset A, Newman M E J, Moore C. Finding community structure in very large networks [J]. Physical review E, 2004, 70(6): 066111.
[17]
Medus A, Acuna G, Dorso C O. Detection of community structures in networks via global optimization [J]. Physica A: Statistical Mechanics and its Applications, 2005, 358(2): 593-604.
[18]
Chen D, Shang M, Lv Z, et al. Detecting overlapping communities of weighted networks via a local algorithm [J]. Physica A: Statistical Mechanics and its Applications, 2010, 389(19): 4177-4187.
[19]
Guo W F, Zhang S W. A general method of community detection by identifying community centers with affinity propagation [J]. Physica A: Statistical Mechanics and its Applications, 2016, 447: 508-519.
[20]
Dinh T N, Nguyen N P, Alim M A, et al. A near-optimal adaptive algorithm for maximizing modularity in dynamic scale-free networks [J]. Journal of Combinatorial Optimization, 2015, 30(3): 747-767.
[21]
Chen D, Fu Y, Shang M. A fast and efficient heuristic algorithm for detecting community structures in complex networks [J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(13): 2741-2749.
[22]
Agarwal G, Kempe D. Modularity-maximizing graph communities via mathematical programming [J]. The European Physical Journal B, 2008, 66(3): 409-418.
[23]
Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks [J]. Journal of statistical mechanics: theory and experiment, 2008, 2008(10): P10008.
[24]
Cormen T H. Introduction to algorithms [M]. MIT press, 2009.
[25]
Cho E, Myers S A, Leskovec J. Friendship and mobility: user movement in location-based social networks[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2011: 1082-1090.
[26]
Ley M. The DBLP computer science bibliography: Evolution, research issues, perspectives[C]//String Processing and Information Retrieval. Springer Berlin Heidelberg, 2002: 1-10.
[27]
Yang J, Leskovec J. Defining and evaluating network communities based on ground-truth [J]. Knowledge and Information Systems, 2015, 42(1): 181-213.
[28]
Leskovec J, Lang K J, Dasgupta A, et al. Statistical properties of community structure in large social and information networks[C] //Proceedings of the 17th International Conference on World Wide Web. ACM, 2008: 695-704.
[29]
Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical review E, 2008, 78(4): 046110.
[30]
Molloy M, Reed B. The size of the giant component of a random graph with a given degree sequence [J]. Combinatorics, Probability and Computing, 1998, 7(03): 295-305.
[31]
He J, Chen D. A fast algorithm for community detection in temporal network [J]. Physica A: Statistical Mechanics and its Applications, 2015, 429: 87-94.
Browse journals by subject