Misc,
Community detection in graphs
(2009)cite arxiv:0906.0612Comment: Review article. 103 pages, 42 figures, 2 tables. Two sections expanded + minor modifications. Three figures + one table + references added. Final version published in Physics Reports.
DOI: 10.1016/j.physrep.2009.11.002
Abstract
The modern science of networks has brought significant advances to our
understanding of complex systems. One of the most relevant features of graphs
representing real systems is community structure, or clustering, i. e. the
organization of vertices in clusters, with many edges joining vertices of the
same cluster and comparatively few edges joining vertices of different
clusters. Such clusters, or communities, can be considered as fairly
independent compartments of a graph, playing a similar role like, e. g., the
tissues or the organs in the human body. Detecting communities is of great
importance in sociology, biology and computer science, disciplines where
systems are often represented as graphs. This problem is very hard and not yet
satisfactorily solved, despite the huge effort of a large interdisciplinary
community of scientists working on it over the past few years. We will attempt
a thorough exposition of the topic, from the definition of the main elements of
the problem, to the presentation of most methods developed, with a special
focus on techniques designed by statistical physicists, from the discussion of
crucial issues like the significance of clustering and how methods should be
tested and compared against each other, to the description of applications to
real networks.
