On modularity clustering

被引：766

作者：

Brandes, Ulrik ^{[1
]}

Delling, Daniel ^{[2
]}

Gaertler, Marco ^{[2
]}

Goerke, Robert ^{[2
]}

Hoefer, Martin ^{[3
]}

Nikoloski, Zoran ^{[4
]}

Wagner, Dorothea ^{[2
]}

机构：

[1] Univ Konstanz, Dept Comp & Informat Sci, D-78457 Constance, Germany

[2] Univ Karlsruhe, Fac Informat, TH, ITI Wagner, D-76128 Karlsruhe, Germany

[3] Rhein Westfal TH Aachen, Dept Comp Sci, Lehrstuhl Informat 1, D-52074 Aachen, Germany

[4] Max Planck Inst Mol Plant Physiol, Bioinformat Grp, D-14476 Potsdam, Germany

来源：

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING | 2008年 / 20卷 / 02期

关键词：

graph clustering; graph partitioning; modularity; community structure; greedy algorithm;

D O I：

10.1109/TKDE.2007.190689

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

引用

页码：172 / 188

页数：17

共 28 条

[11] Gaertler M, 2005, LECT NOTES COMPUT SC, V3418, P178
[12] Gaertler M, 2007, LECT NOTES COMPUT SC, V4508, P11
[13] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[14] Correlation Clustering with a Fixed Number of Clusters
Giotis, Ioannis
Guruswami, Venkatesan
[J]. PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 1167 - 1176
[15] Guimerà R, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.025101
[16] A clustering algorithm based on graph connectivity
Hartuv, E
Shamir, R
[J]. INFORMATION PROCESSING LETTERS, 2000, 76 (4-6) : 175 - 181
[17] Data clustering: A review
Jain, AK
Murty, MN
Flynn, PJ
[J]. ACM COMPUTING SURVEYS, 1999, 31 (03) : 264 - 323
[18] On clusterings - Good, bad and spectral
Kannan, R
Vempala, S
Vetta, A
[J]. 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, : 367 - 377
[19] The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations - Can geographic isolation explain this unique trait?
Lusseau, D
Schneider, K
Boisseau, OJ
Haase, P
Slooten, E
Dawson, SM
[J]. BEHAVIORAL ECOLOGY AND SOCIOBIOLOGY, 2003, 54 (04) : 396 - 405
[20] Local modularity measure for network clusterizations
Muff, S
Rao, F
Caflisch, A
[J]. PHYSICAL REVIEW E, 2005, 72 (05)

← 1 2 3 →