Benchmark graphs for testing community detection algorithms
Lancichinetti, A, Fortunato, S, Radicchi, FPhys. Rev. E 78, 046110 (2008)
Times cited: 510
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.