Community Structure in Graphs

By Santo Fortunato, Claudio Castellano. Encyclopedia of Complexity and Systems Science, 2007

374 citations recorded by the source corpus.

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.

Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d29edc96be8e8ae47e3b9379f801adda2b3b1c7d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

A classification for community discovery methods in complex networks (2011, background): “Fortunato and Castellano [179], hugely extended by Fortunato in [6], have published the most recent and probably the most comprehensive review on the community discovery problem.”
A Multiobjective Genetic Algorithm to Find Communities in Complex Networks (2012, methodology): “A reference approach to multiobjective clustering algorithms for numerical and categorical data is that proposed by Handl and Knowles [28], and named multiobjective clustering with automatic K-determination (MOCK).”
Extending the definition of modularity to directed graphs with overlapping communities (2008, background): “For this reason, a signiﬁcant number of new algorithms for community detection have been proposed in the last few years (refer to [5] [8] for extensive overviews).”
Community detection in graphs (2009, background): “(Danon et al., 2007; Fortunato and Castellano, 2009; Newman, 2004a; Porter et al., 2009; Schaeffer, 2007)).”
Assessing the relevance of node features for network structure (2008, background): “Examples go from inference of gene function from proteininteraction networks [10] to the detection of communities in social networks [11, 12].”
Community detection in Social Media (2012, methodology): “For instance, the survey articles by Fortunato and Castellano (2007) and Fortunato (2009, 2010) contain an extensive discussion of numerous community detection methods; however, they are mostly concerned with the methodological foundations of community detection .”
Comparing Community Structure to Characteristics in Online Collegiate Social Networks (2008, methodology): “Although structural communities, constructed using only link topologies and weights, have been shown to correspond closely to functional communities in some situations [21, 28 ], such correspondence is in general only approximate.”
Communities in Networks (2009, background): “daptation of a ﬁgure from Ref. [20]. the demographic identiﬁcation of network components and the function of dynamical processes that operate on networks (such as the spread of opinions and diseases) [33]. A community in a social network might indicate a circle of friends, a community in the World W”