Finding and evaluating community structure in networks

@article{citeulike:1043460, abstract = {We propose and study a set of algorithms for discovering community structure in networks\&\#151;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.}, author = {Newman, M. E. J. and Girvan, M. }, citeulike-article-id = {1043460}, doi = {10.1103/PhysRevE.69.026113}, journal = {Physical Review E (Statistical, Nonlinear, and Soft Matter Physics)}, keywords = {2004, betweenness, community, complex, network}, number = {2}, posted-at = {2008-07-17 18:34:00}, priority = {0}, publisher = {APS}, title = {Finding and evaluating community structure in networks}, url = {http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=PLEEE8000069000002026113000001\&idtype=cvips\&gifs=yes}, volume = {69}, year = {2004} }

TY - JOUR ID - citeulike:1043460 L3 - citeulike-article-id:1043460 TI - Finding and evaluating community structure in networks JF - Physical Review E (Statistical, Nonlinear, and Soft Matter Physics) VL - 69 IS - 2 PB - APS N2 - 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. KW - 2004 KW - betweenness KW - community KW - complex KW - network AU - Newman, MEJ AU - Girvan, M PY - 2004/// UR - http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PLEEE8000069000002026113000001&idtype=cvips&gifs=yes ER -