brain of mat kelcey...

social graphs, like twitter or facebook, often follow the pattern of having clusters of highly connected components with an occasional edge joining these clusters.

these connecting edges define the boundaries of communities in the social network and can be identified by algorithms that measure betweenness.

the girvan-newman algorithm can be used to decompose a graph hierarchically based on successive removal of the edges with the highest betweenness.

the algorithm is basically

1. calculate the betweenness of each edge (using an all shortest paths algorithm)
2. remove the edge(s) with the highest betweenness
3. check for connected components (using tarjan's algorithm)
4. repeat for graph or subgraphs if graph was split