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.
%0 Generic
%1 NewmanGirvan2003
%A Newman, M. E. J.
%A Girvan, M.
%D 2003
%K social-networks
%T Finding and evaluating community structure in networks
%U http://arxiv.org/abs/cond-mat/0308217
%X 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.
@misc{NewmanGirvan2003,
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.},
added-at = {2007-07-06T10:33:42.000+0200},
author = {Newman, M. E. J. and Girvan, M.},
biburl = {https://www.bibsonomy.org/bibtex/21bd36e98dd5877a404b1742e56d446ed/schaal},
citeulike-article-id = {154},
eprint = {cond-mat/0308217},
interhash = {7892b08fd9c96782d075e92787ce3323},
intrahash = {1bd36e98dd5877a404b1742e56d446ed},
keywords = {social-networks},
month = {August},
priority = {2},
timestamp = {2007-07-06T10:33:48.000+0200},
title = {Finding and evaluating community structure in networks},
url = {http://arxiv.org/abs/cond-mat/0308217},
year = 2003
}