Modularity and community structure in networks.
By Mark Newman. 2006
12,290 citations recorded by the source corpus.
Many networks of interest in the sciences, including social networks, computer networks, and metabolic and regulatory networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure is one of the outstanding issues in the study of networked systems. One highly effective approach is the optimization of the quality function known as "modularity" over the possible divisions of a network. Here I show that the modularity can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which I call the modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times. I illustrate the method with applications to several published network data sets.
Subfields: Molecular Biology, Statistical and Nonlinear Physics, Graph Learning
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
- Olaf Sporns
- Jure Leskovec
- Ludo Waltman
- Nees Jan van Eck
- E. Bullmore
- D. Bassett
- M. A. Porter
In Statistical and Nonlinear Physics
- Santo Fortunato
- Jure Leskovec
- Olaf Sporns
- Mark Newman
- M. A. Porter
- Darko Hric
- Alex Arenas
- Richard F. Betzel
In Graph Learning
- Jure Leskovec
- Bryan Perozzi
- Chengqi Zhang
- William L. Hamilton
- Stephan Günnemann
- Peng Cui
- Wenwu Zhu
- Huan Liu
Citations in the corpus
- DeepWalk: online learning of social representations (2014, background): “The eigenvectors of B encode information about modular graph partitions of G [34].”
- ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software (2014, methodology): “His LinLog energy model arguably provides the most readable placements, since it results in a placement that corresponds to Newman’s modularity [14], a widely used measure of community structure.”
- Prioritizing network communities (2018, methodology): “…the understanding of complex systems across sciences 2,3 . detection 4 Methods for community , also called node clustering or graph partitioning, allow for computational detection of modular structure by identifying a division of network ’ s nodes into groups, also called communities 5 – 10 .”
- Community detection in graphs (2009, methodology): “…methods, which are computationally demanding (Guimerà et al., 2004; Massen and Doye, 2005; Medus et al., 2005); algorithms giving a good tradeoff between high accuracy and low complexity (Duch and Arenas, 2005; Lehmann and Hansen, 2007; Newman, 2006b; Ruan and Zhang, 2007; White and Smyth, 2005).”
- SOCPROG programs: analysing animal social structures (2009, positive): “The groups formed using these two cutoffs are indicated in the dendrogram above Perhaps the most efficient is the eigenvector modularity method of Newman (2006).”
- Analysis of the structure of complex networks at different resolution levels (2007, methodology): “Heuristics for the optimization of modularity [17, 18, 19, 20, 21, 22] have become the only feasible (in computational time), and accurate method to detect modular structure up to now.”
- Like like alike — Joint Friendship and Interest Propagation in Social Networks Shuang (2011, methodology): “Some of them employ random walk methods [14] [22] or spectral graph algorithms [19] [20].”
- Structural complexity of minerals: information storage and processing in the mineral world (2013, background): “The hierarchical organization of crystal structures of minerals links structural mineralogy to the theory of complex hierarchical networks with the properties of clustering and modularity (Newman, 2006).”
- Soil Bacterial and Fungal Response to Wildfires in the Canadian Boreal Forest Across a Burn Severity Gradient (2019, background): “4 428 suggested to define modular structure [69].”
- Spatio-Temporal Data Mining (2017, methodology): “For example, [Yu et al. 2015b] found groups of ST rasters by first constructing networks from ST rasters and then grouping the resultant networks using a network module-finding approach from [Newman 2006].”
- Overlapping community detection at scale: a nonnegative matrix factorization approach (2013, neutral): “Graph partitioning [28, 30], modularity optimization [24]”
- 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.”
- A Multiobjective Genetic Algorithm to Find Communities in Complex Networks (2012, background): “The idea underlying the edge betweenness comes from the observation that if two communities are joined by a few intercommunity edges, then all the paths from vertices in one community to vertices in the another must pass through these edges.”