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 Newman2004Finding
%A Newman, M. E. J.
%A Girvan, M.
%D 2004
%I American Physical Society
%J Physical Review E
%K modularity, networks social-networks communities betweenness
%N 2
%P 026113+
%R 10.1103/physreve.69.026113
%T Finding and evaluating community structure in networks
%U http://dx.doi.org/10.1103/physreve.69.026113
%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.
@article{Newman2004Finding,
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 = {2019-06-10T14:53:09.000+0200},
author = {Newman, M. E. J. and Girvan, M.},
biburl = {https://www.bibsonomy.org/bibtex/274c838b04bb594ca8c141615d2f1b240/nonancourt},
citeulike-article-id = {1043460},
citeulike-linkout-0 = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=PLEEE8000069000002026113000001\&idtype=cvips\&gifs=yes},
citeulike-linkout-1 = {http://link.aps.org/abstract/PRE/v69/e026113},
citeulike-linkout-2 = {http://dx.doi.org/10.1103/physreve.69.026113},
citeulike-linkout-3 = {http://link.aps.org/abstract/PRE/v69/i2/e026113},
citeulike-linkout-4 = {http://link.aps.org/pdf/PRE/v69/i2/e026113},
doi = {10.1103/physreve.69.026113},
interhash = {b9145040e35ccb4d2a0ce18105e64ff4},
intrahash = {74c838b04bb594ca8c141615d2f1b240},
journal = {Physical Review E},
keywords = {modularity, networks social-networks communities betweenness},
month = feb,
number = 2,
pages = {026113+},
posted-at = {2008-10-06 17:06:28},
priority = {4},
publisher = {American Physical Society},
timestamp = {2019-08-26T11:18:50.000+0200},
title = {{Finding and evaluating community structure in networks}},
url = {http://dx.doi.org/10.1103/physreve.69.026113},
volume = 69,
year = 2004
}