Finding and Evaluating Community Structure in Networks. Newman, M. E J & Girvan, M.
doi  abstract   bibtex   
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{newmanFindingEvaluatingCommunity2004,
  title = {Finding and Evaluating Community Structure in Networks},
  volume = {69},
  issn = {1063651X},
  doi = {10.1103/PhysRevE.69.026113},
  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.},
  issue = {2 2},
  journaltitle = {Physical Review E - Statistical, Nonlinear, and Soft Matter Physics},
  date = {2004},
  author = {Newman, M. E J and Girvan, M.},
  file = {/home/dimitri/Nextcloud/Zotero/storage/78QE3H3I/Newman, Girvan - 2004 - Finding and evaluating community structure in networks.pdf},
  eprinttype = {pmid},
  eprint = {14995526}
}
Downloads: 0