Abstract
Graph vertices are often organized into groups that seem to live fairly
independently 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 communities,
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 community 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 hierarchies,
i.e. communities which are nested inside larger communities, and by the
existence of overlaps between communities, due to the presence of nodes
belonging 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.
Description
[0712.2716] Community Structure in Graphs
Links and resources
Tags
community