Finding and evaluating community structure in networks.
By Mark Newman, Michelle Girvan. Physical review. E, Statistical, nonlinear, and soft matter physics, 2003
14,008 citations recorded by the source corpus.
We propose and study a set of algorithms for discovering community structure in networks-natural divisions of network nodes into densely connected subgroups. Our algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using any one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. We also propose a measure for the strength of the community structure found by our algorithms, which gives us an objective metric for choosing the number of communities into which a network should be divided. We demonstrate that our algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/08b39cbabc2c5b764a85a0193296f83e23a62934
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Santo Fortunato
- Jure Leskovec
- Michael W. Mahoney
- Ludo Waltman
- Nees Jan van Eck
- Anirban Dasgupta
- Kevin J. Lang
- Darko Hric
In Computer Networks and Communications
- Santo Fortunato
- Olaf Sporns
- Jure Leskovec
- Mark Newman
- M. A. Porter
- Alex Arenas
- Binghui Wang
- E. Bullmore
In Statistical and Nonlinear Physics
- Santo Fortunato
- Jure Leskovec
- Mark Newman
- Olaf Sporns
- M. A. Porter
- Darko Hric
- Jaewon Yang
- Alex Arenas
Citations in the corpus
- Overlapping Communities Explain Core–Periphery Organization of Networks (2014, methodology): “This work was supported by the National Science Foundation (NSF) under Career Award IIS-1149837, by Defense Advanced Research Projects Agency (DARPA) XDATA, by GRAPHS, by the Alfred P. Sloan Fellowship, and by the Microsoft Faculty Fellowship.”
- Task-Based Core-Periphery Organization of Human Brain Dynamics (2012, methodology): “We determined the community structure of this mean-coherence matrix by optimizing the single-layer modularity quality function [1, 2, 3, 4, 5]:”
- A smart local moving algorithm for large-scale modularity-based community detection (2013, background): “Modularity functions were introduced by Newman and Girvan (2004), and the idea of detecting communities by optimizing a modularity function was proposed by Newman (2004a).”
- Creating an academic landscape of sustainability science: an analysis of the citation network (2007, methodology): “The clustering algorithm is based on modularity Q, which is defined as follows (Newman 2004; Newman and Girvan 2004): Q ¼ XNm s¼1 ls l ds 2l 2" # ð1Þ where Nm is the number of clusters, ls is the number of links between nodes in cluster s, and ds is the sum of the degrees of the nodes in cluster s.”
- Species traits as drivers of food web structure (2018, background): “Standard network properties (Williams and Martinez 2000, Newman and Girvan 2004, Vermaat et al.”
- Which Type of Citation Analysis Generates the Most Accurate Taxonomy of Scientific and Technical Knowledge? (2015, background): “The first modularity-based algorithms capable of clustering hundreds of thousands of documents became available in the mid-2000s (Newman, 2006; Newman & Girvan, 2004).”
- WEB-based GEne SeT AnaLysis Toolkit (WebGestalt): update 2013 (2013, methodology): “First, using the random walk-based walktrap algorithm (20), we identify the best partition of the network by maximizing the modularity score (21); Secondly, we use the edge switching algorithm (22) to generate 1000 random networks with the same attributes as the protein–protein interaction network…”
- Community-based greedy algorithm for mining top-K influential nodes in mobile social networks (2010, background): “They usually optimize a quality measure of network clustering, such as popular modularity measure [17], and need to solve an NP-complete problem.”
- Structure–stability relationships in networks combining mutualistic and antagonistic interactions (2014, background): “On the other hand, modularity, that characterizes the organization of networks into sub-groups of species that interact more with each other than with other species (Newman and Girvan 2004), promotes food web stability (Stouffer and Bascompte 2011).”
- Identifying compartments in presence–absence matrices and bipartite networks: insights into modularity measures (2013, methodology): “The most common measure used to assess modularity (Newman & Girvan, 2004), herein Q1, is expressed as follows: Q1 ¼ XN m¼1 Lm L Km 2L 2" # ; (1) where N is the number of modules in the network, L is the total number of links, Lm is the number of links between all the nodes within module m and Km is…”
- Sociology in the Era of Big Data: The Ascent of Forensic Social Science (2015, positive): “Perhaps the most promising line of work attempts to take the mass of links and render it into identifiable clusters of linked nodes (Leskovec et al. 2010; Newman 2001; Newman and Girvan 2004).”
- A bibliometric review of the innovation adoption literature (2018, methodology): “[07-08] [11][24] [38][44] [01][18] [22-23] [33] [14][17] [30][49] [41]”