Finding and evaluating community structure in networks¶
Why this mattered¶
Newman and Girvan’s paper helped turn “community structure” from an intuitive description of networks into a measurable, algorithmic object. Before this work, researchers could observe that social, biological, technological, and information networks seemed to contain densely connected groups, but there was no broadly adopted way to extract those groups and decide how many were meaningful. The paper’s key move was to identify communities by progressively removing high-betweenness edges, especially recalculating betweenness after each removal, so that boundaries between groups could emerge dynamically rather than being fixed by a single global ranking.
Its second major contribution was modularity: an objective score for how strongly a proposed division separates a network into internally dense, externally sparse groups relative to a null model. This made community detection comparable, optimizable, and portable across domains. After the paper, network scientists could analyze large empirical systems not only by nodes, hubs, and paths, but by mesoscopic organization: factions in social networks, functional modules in biological networks, topical clusters on the web, and subfields in citation graphs.
The paper also set the agenda for a large subsequent literature. Its divisive algorithm was computationally expensive, but the modularity framework inspired faster greedy methods, spectral approaches, multilevel algorithms such as Louvain, statistical block-model comparisons, and later debates about resolution limits and detectability thresholds. In that sense, its lasting importance was not a single best algorithm, but a new paradigm: networks could be decomposed into meaningful intermediate-scale structure, evaluated quantitatively, and used to explain how complex systems organize and function.
Abstract¶
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.
Related¶
- cite → A Set of Measures of Centrality Based on Betweenness — Newman and Girvan's community-detection method uses edge betweenness, derived from Freeman's betweenness centrality, to identify network divisions.
- cite → Collective dynamics of ‘small-world’ networks — The community-structure paper builds on small-world network theory as evidence that real networks have nonrandom structural organization.
- cite → The Structure and Function of Complex Networks — The community-structure paper cites Newman's complex-networks review for the broader framework of network topology and function.
- cite ← Modularity and community structure in networks — Newman's 2006 paper formalizes and optimizes the modularity measure introduced for evaluating community structure in networks.
- enables ← A Set of Measures of Centrality Based on Betweenness — Freeman's betweenness centrality quantified bridge nodes in networks, a concept used by Girvan and Newman to remove high-betweenness edges when detecting communities.
- enables ← Collective dynamics of ‘small-world’ networks — Watts and Strogatz's small-world graph model helped frame network topology as a measurable structure, enabling Newman and Girvan's modularity-based detection of communities in complex networks.