Robustness of community structure in networks

被引:218
作者
Karrer, Brian [1 ]
Levina, Elizaveta [2 ]
Newman, M. E. J. [1 ,3 ]
机构
[1] Univ Michigan, Dept Phys, Ann Arbor, MI 48109 USA
[2] Univ Michigan, Dept Stat, Ann Arbor, MI 48109 USA
[3] Univ Michigan, Ctr Study Complex Syst, Ann Arbor, MI 48109 USA
基金
美国国家科学基金会;
关键词
D O I
10.1103/PhysRevE.77.046119
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.
引用
收藏
页数:9
相关论文
共 48 条
[11]  
CLAUSET A, 2006, P 23 INT C MACH LEAR
[12]  
Cover T.M., 2006, ELEMENTS INFORM THEO, V2nd, DOI [DOI 10.1002/0471200611, 10.1002/0471200611]
[13]   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
[14]   Clique percolation in random networks -: art. no. 160202 [J].
Derényi, I ;
Palla, G ;
Vicsek, T .
PHYSICAL REVIEW LETTERS, 2005, 94 (16)
[15]  
Dongen S., 2000, Performance criteria for graph clustering and markov cluster experiments
[16]   Community detection in complex networks using extremal optimization [J].
Duch, J ;
Arenas, A .
PHYSICAL REVIEW E, 2005, 72 (02)
[17]   Parallel tempering: Theory, applications, and new perspectives [J].
Earl, DJ ;
Deem, MW .
PHYSICAL CHEMISTRY CHEMICAL PHYSICS, 2005, 7 (23) :3910-3916
[18]   Weighted network modules [J].
Farkas, Illes J. ;
Abel, Daniel ;
Palla, Gergely ;
Vicsek, Tamas .
NEW JOURNAL OF PHYSICS, 2007, 9
[19]  
FORTUNATO S, ARXIV07122716
[20]   Resolution limit in community detection [J].
Fortunato, Santo ;
Barthelemy, Marc .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (01) :36-41