  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 new class of benchmark
graphs, that account for the heterogeneity in the distributions of node degrees
and of community sizes. We use this new benchmark to test two popular methods
of community detection, modularity optimization and Potts model clustering. The
results show that the new benchmark poses a much more severe test to algorithms
than standard benchmarks, revealing limits that may not be apparent at a first
analysis.
