Graph clustering

被引：1226

作者：

Schaeffer, Satu Elisa ^{[1
]}

机构：

[1] Aalto Univ, Lab Theoret Comp Sci, FI-02015 Espoo, Finland

来源：

COMPUTER SCIENCE REVIEW | 2007年 / 1卷 / 01期

基金：

芬兰科学院;

关键词：

D O I：

10.1016/j.cosrev.2007.05.001

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this survey we overview the definitions and methods for graph clustering, that is, finding sets of "related" vertices in graphs. We review the many definitions for what is a cluster in a graph and measures of cluster quality. Then we present global algorithms for producing a clustering for the entire vertex set of an input graph, after which we discuss the task of identifying a cluster for a specific seed vertex by local computation. Some ideas on the application areas of graph clustering algorithms are given. We also address the problematics of evaluating clusterings and benchmarking cluster algorithms. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：27 / 64

页数：38

共 249 条

[21] Biernacki C, 1997, COMPUTING SCI STAT, V29, P451
[22] Biggs N., 1994, ALGEBRAIC GRAPH THEO
[23] Bomze I.M., 1999, HDB COMBINATORIAL OP, P1
[24] Booth J. G., 2007, J ROYAL STAT SOC SER
[25] Boutin F., 2004, P 8 INT C INF VIS IE
[26] Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data
Boyer, F
Morgat, A
Labarre, L
Pothier, J
Viari, A
[J]. BIOINFORMATICS, 2005, 21 (23) : 4209 - 4215
[27] Bradley P. S., 1998, P 4 INT C KNOWLEDGE
[28] Brandes U, 2003, LECT NOTES COMPUT SC, V2832, P568
[29] A faster algorithm for betweenness centrality
Brandes, U
[J]. JOURNAL OF MATHEMATICAL SOCIOLOGY, 2001, 25 (02) : 163 - 177
[30] The anatomy of a large-scale hypertextual Web search engine
Brin, S
Page, L
[J]. COMPUTER NETWORKS AND ISDN SYSTEMS, 1998, 30 (1-7): : 107 - 117

← 1 2 3 4 5 6 7 8 9 10 →