- Access by Xinjiang University
Benchmark graphs for testing community detection algorithms
Phys. Rev. E 78, 046110 – Published 24 October, 2008
DOI: 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.
Article Text
References (25)
- M. E. J. Newman, SIAM Rev. 45, 167 (2003).
- S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, Phys. Rep. 424, 175 (2006).
- M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002).
- S. Fortunato and C. Castellano, in Encyclopedia of Complexity and System Science, edited by B. Meyers (Springer, Heidelberg, 2009).
- D. Lusseau and M. E. J. Newman, Proc. R. Soc. London, Ser. B 271, S477 (2004).
- G. W. Flake, S. Lawrence, C. Lee Giles, and F. M. Coetzee, Comput. Sci. Eng. 35, 66 (2002).
- R. Guimerà and L. A. N Amaral, Nature (London) 433, 895 (2005).
- G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Nature (London) 435, 814 (2005).
- R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 406, 378 (2000).
- R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 (2000).
- R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001).
- R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas, Phys. Rev. E 68, 065103 (R) (2003).
- L. Danon, J. Duch, A. Arenas, and A. Díaz-Guilera, in Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science, edsited by. G. Caldarelli and A. Vespignani (World Scientific, Singapore, 2007), pp. 93–114.
- A. Clauset, M. E. J. Newman, and C. Moore, Phys. Rev. E 70, 066111 (2004).
- L. Danon, A. Díaz-Guilera, and A. Arenas, J. Stat. Mech.: Theory Exp. 2006 P11010.
- V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, e-print arXiv:0803.0476.
- A. Lancichinetti, S. Fortunato, and J. Kertész, e-print arXiv:0802.1218.
- M. Molloy and B. Reed, Combinatorics, Probab. Comput. 6, 161 (1995).
- M. E. J. Newman, Phys. Rev. E 69, 066133 (2004).
- J. Duch and A. Arenas, Phys. Rev. E 72, 027104 (2005).
- J. Reichardt and S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004).
- L. Danon, A. Díaz-Guilera, J. Duch, and A. Arenas, J. Stat. Mech.: Theory Exp. 2005 P09008.
- F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Proc. Natl. Acad. Sci. U.S.A. 101, 2658 (2004).
- S. Fortunato and M. Barthélemy, Proc. Natl. Acad. Sci. U.S.A. 104, 36 (2007).
- A software package to generate the benchmark graphs can be downloaded from http://santo.fortunato.googlepages.com/benchmark.tgz