SCIENTIA SINICA Mathematica, Volume 47, Issue 2: 241-256(2017) https://doi.org/10.1360/N012015-00284

A linear community detection algorithm based on dynamical\\ system in networks

More info
  • ReceivedSep 6, 2015
  • AcceptedFeb 17, 2016
  • PublishedAug 8, 2016


Detection of communities or clustering is particularly valuable for understanding, analyzing and optimizing many natural and engineering complex networks, such as gene regulatory networks, smart grid and transportation networks. Present techniques relies heavily on the optimization or heuristic methods, which cannot balance the computational efficiency and accuracy. In this paper, we propose an iterative algorithm to realize the exact detection of network communities, by using a novel method based on dynamical system. We first introduce a discrete-time dynamical system that characterizes the evolutionary iteration of community membership from a random configure to the optimal one, and then specify the conditions that can direct the trajectory of this dynamical system to the convergence, which reveals the community label of each node. The computational complexity analysis shows the high-performance of our algorithm: The required computational time is linearly dependent on the total number of nodes in a sparse network. Analyzing the eigenvalue gap of the Markovian transition matrix, a rigorous theory is provided to find the optimal number of communities divided from a network. We also show that the new algorithm can be generalized to unify the conventional algorithms that are widely used. Finally, we perform extensive simulations using both synthetic and real-world benchmark networks to illustrate the nice performance of our method.

Funded by







[1] Folino F, Pizzuti C. An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Trans Knowl Data Eng, 2013, 26: 1838-1852. Google Scholar

[2] Gong M G, Cai Q, Chen X W, et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Trans Evol Comput, 2014, 18: 82-97 CrossRef Google Scholar

[3] Tang L, Liu H, Zhang J P. Identifying evolving groups in dynamic multimode networks. IEEE Trans Knowl Data Eng, 2012, 24: 72-85. Google Scholar

[4] Liu Y, Moser J, Aviyente S. Network community structure detection for directional neural networks inferred from multichannel multi-subject EEG data. IEEE Trans Biomed Eng, 2014, 61: 1919-1930 CrossRef Google Scholar

[5] Wang C D, Lai J H, Yu P S. Neiwalk: Community discovery in dynamic content-based networks. IEEE Trans Knowl Data Eng, 2014, 26: 1734-1748 CrossRef Google Scholar

[6] Tremblay N, Borgnat P. Graph wavelets for multiscale community mining. IEEE Trans Signal Process, 2014, 62: 5227-5239 CrossRef Google Scholar

[7] Rolland T, Tasan M, Charloteaux B, et al. A proteome-scale map of the human interactome network. Cell, 2014, 159: 1212-1226 CrossRef Google Scholar

[8] Newman M E J. Fast algorithm for detecting community structure in networks. Phys Rev E (3), 2004, 69: 066133-1226 CrossRef Google Scholar

[9] Newman M E J, Girvan M. Finding and evaluating community structure in networks. Phys Rev E (3), 2004, 69: 026113-1226 CrossRef Google Scholar

[10] Zhang X S, Wang R S, Wang Y, et al. Modularity optimization in community detection of complex networks. Europhys Lett EPL, 2009, 87: 38002. Google Scholar

[11] Li H J, Wang Y, Wu L Y, et al. Potts model based on a Markov process computation solves the community structure problem effectively. Phys Rev E (3), 2012, 86: 016109-1226 CrossRef Google Scholar

[12] Li H J, Zhang X S. Analysis of stability of community structure across multiple hierarchical levels. Europhys Lett EPL, 2013, 103: 58002-1226 CrossRef Google Scholar

[13] Blondel V D, Guillaume J, Lambiotte R, et al. Fast unfolding of communities in large networks. J Stat Mech Theory Exp, 2008, 2008: 10008-1226 CrossRef Google Scholar

[14] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks. Phys Rev E (3), 2004, 70: 066111-1226 CrossRef Google Scholar

[15] Girvan M, Newman M E J. Community structure in social and biological networks. Proc Nat Acad Sci India Sect A, 2002, 99: 7821-7826 CrossRef Google Scholar

[16] Guimera R, Nunes Amaral L A. Functional cartography of complex metabolic networks. Nature, 2005, 433: 895-900. Google Scholar

[17] Hastings M B. Community detection as an inference problem. Phys Rev E (3), 2006, 74: 035102. Google Scholar

[18] Reichardt J, Bornholdt S. Statistical mechanics of community detection. Phys Rev E (3), 2006, 74: 016110-900 CrossRef Google Scholar

[19] Fortunato S, Barth$\acute{\rm e}$lemy M. Resolution limit in community detection. Proc Nat Acad Sci India Sect A, 2007, 104: 36-41 CrossRef Google Scholar

[20] Hofman J M, Wiggins C H. Bayesian approach to network modularity. Phys Rev Lett, 2008, 100: 258701-41 CrossRef Google Scholar

[21] Raghavan U N, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E (3), 2007, 76: 036106-41 CrossRef Google Scholar

[22] Ronhovde P, Nussinov Z. Local resolution-limit-free Potts model for community detection. Phys Rev E (3), 2010, 81: 046114-41 CrossRef Google Scholar

[23] Danon L, Diaz-Guilera A, Duch J, et al. Comparing community structure identification. J Stat Mech Theory Exp, 2005, 2005: 09008-41 CrossRef Google Scholar

[24] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms. Phys Rev E (3), 2008, 78: 046110-41 CrossRef Google Scholar

[25] Duch J, Arenas A. Community detection in complex networks using extremal optimization. Phys Rev E (3), 2005, 72: 027104-41 CrossRef Google Scholar

[26] Boccaletti S, Ivanchenko M, Latora V, et al. Detecting complex network modularity by dynamical clustering. Phys Rev E (3), 2007, 75: 045102. Google Scholar

[27] Shi J, Malik J. Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell, 2001, 22: 888-905. Google Scholar

[28] Knuth D E. The Stanford GraphBase: A Platform for Combinatorial Computing. Reading: Addison-Wesley, 1993. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有