Girvan et al PNAS 2002
Citation
Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002).
Online Version
Summary
This paper shows a method for detecting community structure in a network which addresses the topic of Community Detection. The method is designed with the setting that network nodes are joined together in tightly-nit groups between which there are only looser connections.
The key idea is to construct the communities by removing edges from the original graph, contrasting to the traditional way which constructs the communities by add edges to the vertex set. The edges to be removed is chosen based on the edge betweenness - the number of shortest paths between pairs of vertices that run along the edge.
Brief description of the method
- Calculate the betweenness for all edges in the network.
- Remove the edge with the highest betweenness.
- Recalculate betweennesses for all edges affected by the removal.
- Repeat from step 2 until no edges remain.
Step one uses the fast algorithm from Newman's paper.
Background
Some common properties of many networks
- Small-word property - average distance between vertices in a network is short
- power-law degree distributions - many vertices in a network with low degree and a small number with high degree
- network transitivity - two vertices having a same neighbor would have higher probability of being neighbors of each other.
A traditional method of constructing the communities
- Calculate the weight for each pair of vertices.
- Beginning from an vertex only set, add edges between pairs one by one in the desc order of the weights.
- The resulting graph shows a nested set of increasingly large components, which are taken to be the communities.
