Benchmark graphs for testing community detection algorithms
Top Cited Papers
- 24 October 2008
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 78 (4), 046110
- https://doi.org/10.1103/physreve.78.046110
Abstract
Community structure is one of the most important features of real networks and reveals the internal organization of the nodes. Many algorithms have been proposed but the crucial issue of testing, i.e., the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this benchmark to test two popular methods of community detection, modularity optimization, and Potts model clustering. The results show that the benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.Keywords
Other Versions
This publication has 17 references indexed in Scilit:
- 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
- Identifying the role that animals play in their social networksProceedings. Biological sciences, 2004
- Self-similar community structure in a network of human interactionsPhysical Review E, 2003
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- Epidemic Spreading in Scale-Free NetworksPhysical Review Letters, 2001
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- Error and attack tolerance of complex networksNature, 2000