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.
%0 Journal Article
%1 Schaeffer200727
%A Schaeffer, Satu Elisa
%D 2007
%J Computer Science Review
%K clustering community detection graph survey
%N 1
%P 27 - 64
%R 10.1016/j.cosrev.2007.05.001
%T Graph clustering
%U http://www.sciencedirect.com/science/article/B8JDG-4PBG1S7-1/2/6537f3d1ffbf391086c60dbeba874b13
%V 1
%X 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.
@article{Schaeffer200727,
abstract = {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.},
added-at = {2010-07-26T19:01:50.000+0200},
author = {Schaeffer, Satu Elisa},
biburl = {https://www.bibsonomy.org/bibtex/258ff3e69759d9ec6101b5ee5d91c471c/folke},
description = {ScienceDirect - Computer Science Review : Graph clustering},
doi = {10.1016/j.cosrev.2007.05.001},
interhash = {24c764dba3c31f76ced3aa58f1983ed4},
intrahash = {58ff3e69759d9ec6101b5ee5d91c471c},
issn = {1574-0137},
journal = {Computer Science Review},
keywords = {clustering community detection graph survey},
number = 1,
pages = {27 - 64},
timestamp = {2010-07-26T19:01:50.000+0200},
title = {Graph clustering},
url = {http://www.sciencedirect.com/science/article/B8JDG-4PBG1S7-1/2/6537f3d1ffbf391086c60dbeba874b13},
volume = 1,
year = 2007
}