Finding community structure in networks using the eigenvectors of matrices

被引:2937
作者
Newman, M. E. J. [1 ]
机构
[1] Univ Michigan, Dept Phys, Ann Arbor, MI 48109 USA
[2] Univ Michigan, Dept Phys, Ann Arbor, MI 48109 USA
基金
美国国家科学基金会;
关键词
D O I
10.1103/PhysRevE.74.036104
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
We consider the problem of detecting communities or modules in networks, groups of vertices with a higher-than-average density of edges connecting them. Previous work indicates that a robust approach to this problem is the maximization of the benefit function known as "modularity" over possible divisions of a network. Here we show that this maximization process can be written in terms of the eigenspectrum of a matrix we call the modularity matrix, which plays a role in community detection similar to that played by the graph Laplacian in graph partitioning calculations. This result leads us to a number of possible algorithms for detecting community structure, as well as several other results, including a spectral measure of bipartite structure in networks and a centrality measure that identifies vertices that occupy central positions within the communities to which they belong. The algorithms and measures proposed are illustrated with applications to a variety of real-world complex networks.
引用
收藏
页数:19
相关论文
共 74 条
[21]   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
[22]  
DANON L, PHYSICS0601144
[23]   Detecting network communities:: a new systematic and efficient algorithm -: art. no. P10012 [J].
Donetti, L ;
Muñoz, MA .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2004,
[24]   Evolution of networks [J].
Dorogovtsev, SN ;
Mendes, JFF .
ADVANCES IN PHYSICS, 2002, 51 (04) :1079-1187
[25]   Community detection in complex networks using extremal optimization [J].
Duch, J ;
Arenas, A .
PHYSICAL REVIEW E, 2005, 72 (02)
[26]   Spectral measures of bipartivity in complex networks -: art. no. 046105 [J].
Estrada, E ;
Rodríguez-Velázquez, JA .
PHYSICAL REVIEW E, 2005, 72 (04)
[27]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[28]  
FJALLSTROM P, 1998, COMPUTER INFORM SCI, V3
[29]   Self-organization and identification of web communities [J].
Flake, GW ;
Lawrence, S ;
Giles, CL ;
Coetzee, FM .
COMPUTER, 2002, 35 (03) :66-+
[30]   Method to find community structures based on information centrality [J].
Fortunato, S ;
Latora, V ;
Marchiori, M .
PHYSICAL REVIEW E, 2004, 70 (05) :13