Finding and evaluating community structure in networks
M. Newman, und M. Girvan. Phys Rev E Stat Nonlin Soft Matter Phys, 69 (2):
026113.1-15(Februar 2004)
Zusammenfassung
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.
Beschreibung
Finding and evaluating community structure in netw...[Phys Rev E Stat Nonlin Soft Matter Phys. 2004] - PubMed Result
%0 Journal Article
%1 Newman04communityStructure
%A Newman, M E
%A Girvan, M
%D 2004
%J Phys Rev E Stat Nonlin Soft Matter Phys
%K detection modularity score
%N 2
%P 026113.1-15
%T Finding and evaluating community structure in networks
%U http://www.ncbi.nlm.nih.gov/pubmed/14995526
%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{Newman04communityStructure,
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 = {2009-01-07T08:18:49.000+0100},
author = {Newman, M E and Girvan, M},
biburl = {https://www.bibsonomy.org/bibtex/20c522f0a01f72638e70916f1144746e6/folke},
description = {Finding and evaluating community structure in netw...[Phys Rev E Stat Nonlin Soft Matter Phys. 2004] - PubMed Result},
interhash = {b9145040e35ccb4d2a0ce18105e64ff4},
intrahash = {0c522f0a01f72638e70916f1144746e6},
journal = {Phys Rev E Stat Nonlin Soft Matter Phys},
keywords = {detection modularity score},
month = Feb,
number = 2,
pages = {026113.1-15},
pmid = {14995526},
timestamp = {2009-01-07T08:18:49.000+0100},
title = {Finding and evaluating community structure in networks},
url = {http://www.ncbi.nlm.nih.gov/pubmed/14995526},
volume = 69,
year = 2004
}