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 [J].
AGRAWAL, R ;
JAGADISH, HV .
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 [J].
Altaf-Ul-Amin, Md ;
Shinbo, Yoko ;
Mihara, Kenji ;
Kurokawa, Ken ;
Kanaya, Shigehiko .
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 [J].
Asahiro, Y ;
Hassin, R ;
Iwama, K .
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
12345678910