A Fast Method for Community Detection Based on Compressing Networks

Jialin He; Duanbing Chen; Chongjing Sun

doi:doi:10.11648/j.se.20160402.12

| Peer-Reviewed

A Fast Method for Community Detection Based on Compressing Networks

Jialin He, Duanbing Chen, Chongjing Sun

Published in Software Engineering (Volume 4, Issue 2)

Received: 15 April 2016 Published: 16 April 2016

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	Software Engineering (Volume 4, Issue 2)
DOI	10.11648/j.se.20160402.12
Page(s)	13-18
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2016. Published by Science Publishing Group

Keywords

Complex Networks, Community Structure, Modularity Optimization, Connection Strength, Small Network

References

[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.

Cite This Article

Plain Text BibTeX RIS

APA Style

Jialin He, Duanbing Chen, Chongjing Sun. (2016). A Fast Method for Community Detection Based on Compressing Networks. Software Engineering, 4(2), 13-18. https://doi.org/10.11648/j.se.20160402.12

Copy | Download

ACS Style

Jialin He; Duanbing Chen; Chongjing Sun. A Fast Method for Community Detection Based on Compressing Networks. Softw. Eng. 2016, 4(2), 13-18. doi: 10.11648/j.se.20160402.12

Copy | Download

AMA Style

Jialin He, Duanbing Chen, Chongjing Sun. A Fast Method for Community Detection Based on Compressing Networks. Softw Eng. 2016;4(2):13-18. doi: 10.11648/j.se.20160402.12

Copy | Download

@article{10.11648/j.se.20160402.12,
  author = {Jialin He and Duanbing Chen and Chongjing Sun},
  title = {A Fast Method for Community Detection Based on Compressing Networks},
  journal = {Software Engineering},
  volume = {4},
  number = {2},
  pages = {13-18},
  doi = {10.11648/j.se.20160402.12},
  url = {https://doi.org/10.11648/j.se.20160402.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.se.20160402.12},
  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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - A Fast Method for Community Detection Based on Compressing Networks
AU  - Jialin He
AU  - Duanbing Chen
AU  - Chongjing Sun
Y1  - 2016/04/16
PY  - 2016
N1  - https://doi.org/10.11648/j.se.20160402.12
DO  - 10.11648/j.se.20160402.12
T2  - Software Engineering
JF  - Software Engineering
JO  - Software Engineering
SP  - 13
EP  - 18
PB  - Science Publishing Group
SN  - 2376-8037
UR  - https://doi.org/10.11648/j.se.20160402.12
AB  - 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.
VL  - 4
IS  - 2
ER  -

Copy | Download

Author Information

Jialin He

Web Sciences 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
Chongjing Sun

Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, China

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Jialin He, Duanbing Chen, Chongjing Sun. (2016). A Fast Method for Community Detection Based on Compressing Networks. Software Engineering, 4(2), 13-18. https://doi.org/10.11648/j.se.20160402.12

Copy | Download

ACS Style

Jialin He; Duanbing Chen; Chongjing Sun. A Fast Method for Community Detection Based on Compressing Networks. Softw. Eng. 2016, 4(2), 13-18. doi: 10.11648/j.se.20160402.12

Copy | Download

AMA Style

Jialin He, Duanbing Chen, Chongjing Sun. A Fast Method for Community Detection Based on Compressing Networks. Softw Eng. 2016;4(2):13-18. doi: 10.11648/j.se.20160402.12

Copy | Download

@article{10.11648/j.se.20160402.12,
  author = {Jialin He and Duanbing Chen and Chongjing Sun},
  title = {A Fast Method for Community Detection Based on Compressing Networks},
  journal = {Software Engineering},
  volume = {4},
  number = {2},
  pages = {13-18},
  doi = {10.11648/j.se.20160402.12},
  url = {https://doi.org/10.11648/j.se.20160402.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.se.20160402.12},
  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.},
 year = {2016}
}

Copy | Download

TY  - JOUR
T1  - A Fast Method for Community Detection Based on Compressing Networks
AU  - Jialin He
AU  - Duanbing Chen
AU  - Chongjing Sun
Y1  - 2016/04/16
PY  - 2016
N1  - https://doi.org/10.11648/j.se.20160402.12
DO  - 10.11648/j.se.20160402.12
T2  - Software Engineering
JF  - Software Engineering
JO  - Software Engineering
SP  - 13
EP  - 18
PB  - Science Publishing Group
SN  - 2376-8037
UR  - https://doi.org/10.11648/j.se.20160402.12
AB  - 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.
VL  - 4
IS  - 2
ER  -

Copy | Download