Graph vertices are often organized into groups that seem to live fairly in-
dependently of the rest of the graph, with which they share but a few edges,
whereas the relationships between group members are stronger, as shown by
the large number of mutual connections. Such groups of vertices, or commu-
nities, can be considered as independent compartments of a graph. Detecting
communities is of great importance in sociology, biology and computer science,
disciplines where systems are often represented as graphs. The task is very
hard, though, both conceptually, due to the ambiguity in the definition of com-
munity and in the discrimination of different partitions and practically, because
algorithms must find “good” partitions among an exponentially large number of
them. Other complications are represented by the possible occurrence of hierar-
chies, i.e. communities which are nested inside larger communities, and by the
existence of overlaps between communities, due to the presence of nodes belong-
ing to more groups. All these aspects are dealt with in some detail and many
methods are described, from traditional approaches used in computer science
and sociology to recent techniques developed mostly within statistical physics.
%0 Book Section
%1 fortunato2012community
%A Fortunato, Santo
%A Castellano, Claudio
%B Computational Complexity
%D 2012
%E Meyers, Robert A.
%I Springer New York
%K community complex graphs network structure
%P 490-512
%R 10.1007/978-1-4614-1800-9_33
%T Community Structure in Graphs
%U http://dx.doi.org/10.1007/978-1-4614-1800-9_33
%X Graph vertices are often organized into groups that seem to live fairly in-
dependently of the rest of the graph, with which they share but a few edges,
whereas the relationships between group members are stronger, as shown by
the large number of mutual connections. Such groups of vertices, or commu-
nities, can be considered as independent compartments of a graph. Detecting
communities is of great importance in sociology, biology and computer science,
disciplines where systems are often represented as graphs. The task is very
hard, though, both conceptually, due to the ambiguity in the definition of com-
munity and in the discrimination of different partitions and practically, because
algorithms must find “good” partitions among an exponentially large number of
them. Other complications are represented by the possible occurrence of hierar-
chies, i.e. communities which are nested inside larger communities, and by the
existence of overlaps between communities, due to the presence of nodes belong-
ing to more groups. All these aspects are dealt with in some detail and many
methods are described, from traditional approaches used in computer science
and sociology to recent techniques developed mostly within statistical physics.
%@ 978-1-4614-1799-6
@incollection{fortunato2012community,
abstract = {Graph vertices are often organized into groups that seem to live fairly in-
dependently of the rest of the graph, with which they share but a few edges,
whereas the relationships between group members are stronger, as shown by
the large number of mutual connections. Such groups of vertices, or commu-
nities, can be considered as independent compartments of a graph. Detecting
communities is of great importance in sociology, biology and computer science,
disciplines where systems are often represented as graphs. The task is very
hard, though, both conceptually, due to the ambiguity in the definition of com-
munity and in the discrimination of different partitions and practically, because
algorithms must find “good” partitions among an exponentially large number of
them. Other complications are represented by the possible occurrence of hierar-
chies, i.e. communities which are nested inside larger communities, and by the
existence of overlaps between communities, due to the presence of nodes belong-
ing to more groups. All these aspects are dealt with in some detail and many
methods are described, from traditional approaches used in computer science
and sociology to recent techniques developed mostly within statistical physics.
},
added-at = {2013-11-20T13:27:10.000+0100},
author = {Fortunato, Santo and Castellano, Claudio},
biburl = {https://www.bibsonomy.org/bibtex/2eb01f72fa816d2c06494d3fade515de6/giacomo.fiumara},
booktitle = {Computational Complexity},
doi = {10.1007/978-1-4614-1800-9_33},
editor = {Meyers, Robert A.},
interhash = {9cbb7ac721f177c150ab887f5de694b7},
intrahash = {eb01f72fa816d2c06494d3fade515de6},
isbn = {978-1-4614-1799-6},
keywords = {community complex graphs network structure},
pages = {490-512},
publisher = {Springer New York},
timestamp = {2013-11-20T13:27:10.000+0100},
title = {Community Structure in Graphs},
url = {http://dx.doi.org/10.1007/978-1-4614-1800-9_33},
year = 2012
}