Modularity and community structure in networks¶
Why this mattered¶
Newman’s paper mattered because it helped turn community detection from a largely heuristic graph-partitioning problem into a mathematically organized part of network science. Earlier work had shown that many real networks contain groups of vertices more densely connected internally than externally, but this paper made modularity optimization more tractable and interpretable by introducing the modularity matrix and showing that community structure could be studied through its eigenvectors. That reframed modules not merely as visual clusters or outputs of agglomerative algorithms, but as structures detectable through a spectral property of the network relative to a null model.
The immediate shift was practical as well as conceptual. By deriving a spectral algorithm for modularity maximization, Newman made it possible to analyze larger empirical networks more quickly while obtaining partitions with higher modularity than several competing methods available at the time. This helped modularity become one of the standard objective functions for community detection across sociology, biology, information science, and physics. After this paper, researchers could compare divisions of networks using a common quantitative criterion, adapt spectral methods to network-specific null models, and treat modular organization as a measurable feature rather than an informal description.
Its later importance also lies in the problems it exposed. The success of modularity optimization made it central enough that its limitations, especially the resolution limit and degeneracy of high-modularity partitions, became major research topics. Subsequent breakthroughs in multiscale community detection, stochastic block models, statistical inference for networks, and overlapping or hierarchical community methods often defined themselves in relation to modularity: extending it, correcting it, or replacing it with more explicit generative models. In that sense, the paper did not just provide a better algorithm; it gave the field a dominant benchmark and vocabulary for asking what “community structure” means in real networks.
Abstract¶
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.
Related¶
- cite → Emergence of Scaling in Random Networks — Newman's modularity work analyzes community structure in complex networks, a structural level distinct from the scale-free degree distributions shown by Barabasi and Albert.
- cite → Finding and evaluating community structure in networks — Newman's 2006 paper formalizes and optimizes the modularity measure introduced for evaluating community structure in networks.
- cite → Collective dynamics of ‘small-world’ networks — Newman links community detection to Watts and Strogatz's small-world network model as a foundational example of nontrivial structure in real networks.
- cite → The Structure and Function of Complex Networks — Newman builds on his 2003 review's concepts of network topology, clustering, and community structure to formalize modularity optimization.
- enables → DeepWalk — Newman's modularity objective framed random-walk locality as community structure, a graph property DeepWalk exploits by treating truncated random walks as node contexts.
- cite ← DeepWalk — DeepWalk cites network modularity as a classic measure of community structure that graph embeddings should help capture.
- enables ← Emergence of Scaling in Random Networks — Scale-free network theory framed heterogeneous degree distributions, a prerequisite background for detecting modular community structure in real-world networks.
- enables ← Collective dynamics of ‘small-world’ networks — Small-world network analysis established clustering and short path length as measurable network properties that modularity methods later formalized into communities.