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

Link to pnas

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.

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

1. Calculate the weight for each pair of vertices.
2. Beginning from an vertex only set, add edges between pairs one by one in the desc order of the weights.
3. The resulting graph shows a nested set of increasingly large components, which are taken to be the communities.