Community detection algorithms: A comparative analysis
Authors:
Top Cited Papers
- 30 November 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 80 (5) , 056117
Abstract
Uncovering the community structure exhibited by real networks is a crucial step toward an understanding of complex systems that goes beyond the local organization of their constituents. Many algorithms have been proposed so far, but none of them has been subjected to strict tests to evaluate their performance. Most of the sporadic tests performed so far involved small networks with known community structure and/or artificial graphs with a simplified structure, which is very uncommon in real systems. Here we test several methods against a recently introduced class of benchmark graphs, with heterogeneous distributions of degree and community size. The methods are also tested against the benchmark by Girvan and Newman [Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)] and on random graphs. As a result of our analysis, three recent algorithms introduced by Rosvall and Bergstrom [Proc. Natl. Acad. Sci. U.S.A. 104, 7327 (2007); Proc. Natl. Acad. Sci. U.S.A. 105, 1118 (2008)], Blondel et al. [J. Stat. Mech.: Theory Exp. (2008), P10008], and Ronhovde and Nussinov [Phys. Rev. E 80, 016109 (2009)] have an excellent performance, with the additional advantage of low computational complexity, which enables one to analyze large systems.Keywords
All Related Versions
This publication has 49 references indexed in Scilit:
- Assessing the relevance of node features for network structureProceedings of the National Academy of Sciences, 2009
- Maps of random walks on complex networks reveal community structureProceedings of the National Academy of Sciences of the United States of America, 2008
- Mixture models and exploratory analysis in networksProceedings of the National Academy of Sciences, 2007
- An information-theoretic framework for resolving community structure in complex networksProceedings of the National Academy of Sciences, 2007
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Complex networks: Structure and dynamicsPhysics Reports, 2006
- Uncovering the overlapping community structure of complex networks in nature and societyNature, 2005
- Functional cartography of complex metabolic networksNature, 2005
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973