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.
Keywords
Modularity (biology)Computer scienceCommunity structureEigenvalues and eigenvectorsClique percolation methodComplex networkFunction (biology)Quality (philosophy)Theoretical computer scienceNetwork analysisData miningArtificial intelligenceData scienceMathematicsWorld Wide WebBiologyEngineering
Affiliated Institutions
Related Publications
Consensus and Cooperation in Networked Multi-Agent Systems
<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> This paper provides a theoretical framework for analysis of consensus algorithms...
Overlapping Communities Explain Core–Periphery Organization of Networks
Networks provide a powerful way to study complex systems of interacting objects. Detecting network communities-groups of objects that often correspond to functional modules-is c...
Network In Network
Abstract: We propose a novel deep network structure called In Network (NIN) to enhance model discriminability for local patches within the receptive field. The conventional con...
RolX
Given a network, intuitively two nodes belong to the same role if they have similar structural behavior. Roles should be automatically determined from the data, and could be, fo...
A Simple, Positive Semi-Definite, Heteroskedasticity and Autocorrelation Consistent Covariance Matrix
This paper describes a simple method of calculating a heteroskedasticity and autocorrelation consistent covariance matrix that is positive semi-definite by construction. It also...
Publication Info
- Year
- 2006
- Type
- article
- Volume
- 103
- Issue
- 23
- Pages
- 8577-8582
- Citations
- 11783
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
11783
OpenAlex
Cite This
M. E. J. Newman
(2006).
Modularity and community structure in networks.
Proceedings of the National Academy of Sciences
, 103
(23)
, 8577-8582.
https://doi.org/10.1073/pnas.0601602103
Identifiers
- DOI
- 10.1073/pnas.0601602103