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 Journal Article
%1 citeulike:154
%A Newman, M. E. J.
%A Girvan, M.
%D 2004
%J Physical Review E
%K aaa community
%R 10.1103/PhysRevE.69.026113
%T Finding and evaluating community structure in networks
%U http://arxiv.org/abs/cond-mat/0308217
%V 69
%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.
@article{citeulike:154,
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 = {2006-06-16T10:34:37.000+0200},
author = {Newman, M. E. J. and Girvan, M.},
biburl = {https://www.bibsonomy.org/bibtex/2c565fe3c95b04c01e286ebbde3366bdd/ldietz},
citeulike-article-id = {154},
comment = {Girvan Newman Algorithm
Girvan-Newman Algorithm
GN Algorithm},
doi = {10.1103/PhysRevE.69.026113},
eprint = {cond-mat/0308217},
interhash = {b9145040e35ccb4d2a0ce18105e64ff4},
intrahash = {c565fe3c95b04c01e286ebbde3366bdd},
journal = {Physical Review E},
keywords = {aaa community},
month = {February},
priority = {2},
timestamp = {2006-06-16T10:34:37.000+0200},
title = {Finding and evaluating community structure in networks},
url = {http://arxiv.org/abs/cond-mat/0308217},
volume = 69,
year = 2004
}