Format

Send to

Choose Destination
Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Feb;69(2 Pt 2):026113. Epub 2004 Feb 26.

Finding and evaluating community structure in networks.

Author information

1
Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109-1120, USA.

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.

PMID:
14995526
DOI:
10.1103/PhysRevE.69.026113

Supplemental Content

Loading ...
Support Center