Finding and evaluating community structure in networks
Mark E. J. Newman, Michelle Girvan · Physical Review E · 2004
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.
Cited by 13,903 works. doi:10.1103/physreve.69.026113 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Collective dynamics of ‘small-world’ networks
- Statistical mechanics of complex networks
- Introduction to Algorithms
- An Efficient Heuristic Procedure for Partitioning Graphs
- The Structure and Function of Complex Networks
- Diameter of the World-Wide Web
- Community structure in social and biological networks
- Network Flows: Theory, Algorithms, and Applications.
- Exploring complex networks