Benchmark graphs for testing community detection algorithms

被引:2085
作者
Lancichinetti, Andrea [1 ]
Fortunato, Santo [1 ]
Radicchi, Filippo [1 ]
机构
[1] ISI, CNLL, I-10133 Turin, Italy
关键词
D O I
10.1103/PhysRevE.78.046110
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
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.
引用
收藏
页数:5
相关论文
共 24 条
[1]   Error and attack tolerance of complex networks [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 2000, 406 (6794) :378-382
[2]  
BLONDEL VD, ARXIV08030476
[3]   Complex networks: Structure and dynamics [J].
Boccaletti, S. ;
Latora, V. ;
Moreno, Y. ;
Chavez, M. ;
Hwang, D. -U. .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2006, 424 (4-5) :175-308
[4]  
Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111
[5]   Resilience of the Internet to random breakdowns [J].
Cohen, R ;
Erez, K ;
ben-Avraham, D ;
Havlin, S .
PHYSICAL REVIEW LETTERS, 2000, 85 (21) :4626-4628
[6]   Comparing community structure identification -: art. no. P09008 [J].
Danon, L ;
Díaz-Guilera, A ;
Duch, J ;
Arenas, A .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :219-228
[7]  
Danon L., 2007, Large Scale Struct. Dyn. Compl. Netw., P93
[8]   The effect of size heterogeneity on community identification in complex networks [J].
Danon, Leon ;
Diaz-Guilera, Albert ;
Arenas, Alex .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2006,
[9]   Community detection in complex networks using extremal optimization [J].
Duch, J ;
Arenas, A .
PHYSICAL REVIEW E, 2005, 72 (02)
[10]   Self-organization and identification of web communities [J].
Flake, GW ;
Lawrence, S ;
Giles, CL ;
Coetzee, FM .
COMPUTER, 2002, 35 (03) :66-+