Finding and evaluating community structure in networks
M. Newman, and M. Girvan. Physical Review E, 69 (2):
026113(February 2004)PT: J; PN: Part 2; PG: 15.
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.
%0 Journal Article
%1 RefWorks:342
%A Newman, M. E. J.
%A Girvan, M.
%D 2004
%J Physical Review E
%K clustering communities graph master
%N 2
%P 026113
%T Finding and evaluating community structure in networks
%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 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.
%@ 1063-651X
@article{RefWorks:342,
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.},
added-at = {2011-03-22T23:55:54.000+0100},
author = {Newman, M. E. J. and Girvan, M.},
biburl = {https://www.bibsonomy.org/bibtex/274c838b04bb594ca8c141615d2f1b240/ans},
interhash = {b9145040e35ccb4d2a0ce18105e64ff4},
intrahash = {74c838b04bb594ca8c141615d2f1b240},
isbn = {1063-651X},
journal = {Physical Review E},
keywords = {clustering communities graph master},
month = feb,
note = {PT: J; PN: Part 2; PG: 15},
number = 2,
pages = 026113,
timestamp = {2011-03-22T23:55:54.000+0100},
title = {Finding and evaluating community structure in networks},
volume = 69,
year = 2004
}