Community structure in social and biological networks
By Michelle Girvan, Mark Newman. Proceedings of the National Academy of Sciences of the United States of America, 2001
15,867 citations recorded by the source corpus.
A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particularly on a few properties that seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. In this article, we highlight another property that is found in many networks, the property of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. We propose a method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We test our method on computer-generated and real-world graphs whose community structure is already known and find that the method detects this known structure with high sensitivity and reliability. We also apply the method to two networks whose community structure is not well known—a collaboration network and a food web—and find that it detects significant and informative community divisions in both cases.
Subfields: Molecular Biology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/2a005868b79511cf8c924cd5990e2497527a0527
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Molecular Biology
- Santo Fortunato
- Jure Leskovec
- Olaf Sporns
- Mark Newman
- Tiago P. Peixoto
- Jaewon Yang
- Renaud Lambiotte
- E. Bullmore
In Statistical and Nonlinear Physics
- Santo Fortunato
- Jure Leskovec
- Mark Newman
- Olaf Sporns
- M. A. Porter
- Jaewon Yang
- Darko Hric
- Tiago P. Peixoto
Citations in the corpus
- E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations (2003, methodology): “We describe an experiment performed within our own organization, HP Labs, using nearly one million email messages collected over a period of roughly two months.”
- A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects (2013, methodology): “In [44], Newman proposed a modularity-based community detecting algorithm which uses the metric of quality function " modularity " .”
- The community-search problem and how to plan a successful cocktail party (2010, methodology): “A typical approach for finding communities is by means of optimizing the modularity measure [16, 26].”
- An event-based framework for characterizing the evolutionary behavior of interaction graphs (2007, background): “Early research in this area [13, 24, 4, 5] has primarily focused on the static properties of these networks, neglecting the fact that most real-world interaction networks are dynamic in nature.”
- Identification of Global Oil Trade Patterns: An Empirical Research Based on Complex Network Theory (2014, neutral): “Community structure The community structure of a network can be described as network nodes joining together in tightly-knit groups among which there are only looser connections [17].”
- GA-Net: A Genetic Algorithm for Community Detection in Social Networks (2008, methodology): “The American College Football network [8] comes from the United States college football.”
- Network analysis in conservation biogeography: challenges and opportunities (2010, methodology): “For example, a hierarchical clustering algorithm using the concept of betweenness centrality proposed by Girvan & Newman (2002) has been applied to decomposing a fragmented landscape into different compartments (Bodin & Norberg, 2007).”
- Community Structure in Graphs (2007, methodology): “The most famous computer generated benchmark is a class of graphs designed by Girvan and Newman [14].”
- Community discovery using nonnegative matrix factorization (2011, background): “2005), which are usually called clusters or communities (Girvan and Newman 2002).”
- Exploring the Locus of Invention: The Dynamics of Network Communities and Firms' Invention Productivity (2014, methodology): “In many sparsely connected social systems, these communities typically do not overlap (e.g., Girvan & Newman, 2002; Shipilov, Li, & Greve, 2011; Sytch et al., 2012).”
- Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, background): “Thus, while networks have been extensivelystudied, and the existence and properties of communities in small networks is by now well-understood [1, 2, 10, 25], it is still not clear how to identify realistic overlapping communities in very large networks that are increasingly common.”
- Evolutionary Large-Scale Multi-Objective Optimization: A Survey (2021, background): “Many real-world complex systems can be represented by networks, in which the nodes denote the objects (e.g. individuals in social networks [52] and genes in biological networks [103]) and the edges denote the connections between objects.”
- Coauthorship networks and patterns of scientific collaboration (2004, neutral): “scientific collaboration”
- Dynamical networks in tRNA:protein complexes (2009, methodology): “The community structure is identified by using the Girvan–Newman algorithm (13), which uses a topdown approach to iteratively remove the edge with the highest betweenness and recalculate the betweenness of all remaining edges until none of the edges remain.”
- The “New” Science of Networks (2004, background): “As a result, it is possible for a universal cascade (i.e., one affecting the entire population) to be triggered by a random shock that, a priori, is indistinguishable from Network Robustness attention concerns the origins and effects of node”