Finding and evaluating community structure in networks
Top Cited Papers
- 26 February 2004
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 69 (2), 026113
- https://doi.org/10.1103/physreve.69.026113
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.Keywords
This publication has 36 references indexed in Scilit:
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Infection dynamics on scale-free networksPhysical Review E, 2001
- Epidemic Spreading in Scale-Free NetworksPhysical Review Letters, 2001
- Exploring complex networksNature, 2001
- Graph structure in the WebComputer Networks, 2000
- Epidemics and percolation in small-world networksPhysical Review E, 2000
- Mean-field-type equations for spread of epidemics: the ‘small world’ modelPhysica A: Statistical Mechanics and its Applications, 1999
- Diameter of the World-Wide WebNature, 1999
- On power-law relationships of the Internet topologyACM SIGCOMM Computer Communication Review, 1999