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 条

[1] Achlioptas D., 2005, P 37 ANN ACM S THEOR
[2] ALGORITHMS FOR SEARCHING MASSIVE GRAPHS
AGRAWAL, R
JAGADISH, HV
[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (02) : 225 - 238
[3] Aldous D. J., 2001, REVERSIBE MARKOV CHA
[4] Development and implementation of an algorithm for detection of protein complexes in large interaction networks
Altaf-Ul-Amin, Md
Shinbo, Yoko
Mihara, Kenji
Kurokawa, Ken
Kanaya, Shigehiko
[J]. BMC BIOINFORMATICS, 2006, 7 (1)
[5] Andersen R., 2006, P 74 ANN S FDN COMP
[6] Arora S., 2004, P 36 ANN S THEOR COM
[7] Complexity of finding dense subgraphs
Asahiro, Y
Hassin, R
Iwama, K
[J]. DISCRETE APPLIED MATHEMATICS, 2002, 121 (1-3) : 15 - 26
[8] Auber D., 2004, P 8 INT C INF VIS IE
[9] AURENHAMMER F, 1991, COMPUT SURV, V23, P345, DOI 10.1145/116873.116880
[10] Ausiello G., 1999, COMPLEXITY APPROXIMA

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