Benchmark graphs for testing community detection algorithms

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.

Figure 1

(Color online) A realization of the new benchmark, with 500 nodes.

Figure 2

(Color online) Study of the complexity of our algorithm. The plots show the scaling of the computer time (in s) with the average degree of the graph. The curves correspond to different choices for the exponents $\gamma$ and $\beta$ and the value of $\mu$. The two panels reproduce graphs with 1000 (a) and 10000 nodes (b). The calculations were performed on Opteron processors.

Figure 3

(Color online) Distribution of the $\mu$ values for benchmark graphs obtained with our algorithm for different choices of the exponents and system size.

Figure 4

(Color online) Test of modularity optimization on the benchmark of Girvan and Newman.

Figure 5

(Color online) Test of modularity optimization on the new benchmark. The number of nodes $N=1000$. The results clearly depend on all parameters of the benchmark, from the exponents $\gamma$ and $\beta$ to the average degree $⟨k⟩$. The threshold ${\mu }_c=0.5$ (dashed vertical line in the plots) marks the border beyond which communities are no longer defined in the strong sense, i.e., such that each node has more neighbors in its own community than in the others [23]. Each point corresponds to an average over 100 graph realizations.

Figure 6

(Color online) Test of modularity optimization on the new benchmark. The number of nodes is now $N=5000$, the other parameters are the same as in Fig. 5. Each point corresponds to an average over 25 graph realizations.

Figure 7

(Color online) Test of Potts model clustering on the new benchmark. The number of nodes $N=1000$. The results clearly depend on all parameters of the benchmark, from the exponents $\gamma$ and $\beta$ to the average degree $⟨k⟩$. Each point corresponds to an average over 100 graph realizations.

Figure 8

(Color online) Test of Potts model clustering on the new benchmark. The number of nodes $N=5000$, the other parameters are the same as in Fig. 7. Each point corresponds to an average over ten graph realizations.