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 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.
| Comments: | 16 pages, 13 figures |
| Subjects: | Statistical Mechanics (cond-mat.stat-mech) ; Disordered Systems and Neural Networks (cond-mat.dis-nn) |
| Cite as: | arXiv:cond-mat/0308217 [cond-mat.stat-mech] |
| (or arXiv:cond-mat/0308217v1 [cond-mat.stat-mech] for this version) | |
| https://doi.org/10.48550/arXiv.cond-mat/0308217 |