Abstract
Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50,000 physicists.
Keywords
Computer scienceCommunity structureAlgorithmMathematicsStatistics
Affiliated Institutions
Related Publications
Finding community structure in very large networks
The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsui...
Community structure in social and biological networks
A number of recent studies have focused on the statistical properties of networked systems such as social networks and the Worldwide Web. Researchers have concentrated particula...
Modularity and community structure in networks
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...
The structure of scientific collaboration networks
The structure of scientific collaboration networks is investigated. Two scientists are considered connected if they have authored a paper together and explicit networks of such ...
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...
Publication Info
- Year
- 2004
- Type
- article
- Volume
- 69
- Issue
- 6
- Pages
- 066133-066133
- Citations
- 5403
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
5403
OpenAlex
Cite This
M. E. J. Newman
(2004).
Fast algorithm for detecting community structure in networks.
Physical Review E
, 69
(6)
, 066133-066133.
https://doi.org/10.1103/physreve.69.066133
Identifiers
- DOI
- 10.1103/physreve.69.066133