Girvan-Newman
Splits a graph into k communities by removing, one at a time, the edge that the most shortest paths cross.
Time complexity O(E·V·(V+E)), gograph function partition.GirvanNewman.
How it works
Girvan-Newman finds communities by taking a graph apart. The few edges between two tight groups carry many shortest paths, because every route from one group to the other has to cross them. The algorithm counts how many shortest paths between pairs of vertices use each edge, the edge's betweenness. It removes the edge with the highest count, then counts again.
It stops once the graph has fallen into k connected components, and those are the communities. gograph counts with Brandes' method, a breadth-first search from every vertex, so the length of a path is its number of edges and weights aren't used. That costs O(V·(V+E)) for each edge it removes, and O(E·V·(V+E)) in the worst case. When edges tie, it removes the first one in the graph's edge order, so every run gives the same result. Scores within one part in a billion of the highest count as tied, since the same paths added up in another order can round differently.
It is slow on large graphs, but each split has a clear reason: it removes the link that the most routes cross. A directed graph splits as if it were undirected, and each community keeps the direction of its edges. It works on a copy, so the input stays as it was. Each community it returns keeps all of its edges, including the ones removed along the way.
Campus network
A hundred switches, servers and computers in ten buildings of a university campus, A to J. Each id is a building letter and a number, so D7 is number 7 in building D. A is the data center, where the core switches A1 and A2 link to the main switch of every other building, always number 1. The larger buildings have more switches between the main switch and the computers, and two pairs of neighboring buildings also have a direct link.
An undirected graph with 100 vertices and 114 edges.
Split the campus network into 8 parts along the links that the most routes between devices cross.
The 8 communities have 43, 13, 8, 11, 6, 6, 8 and 5 vertices: A1, A2, A3, A4, A5, A6, A7, A8, A9, A10 and 33 more; B2, B3, B4, B5, B6, B7, B8, B9, B10, B11 and 3 more; C1, C2, C3, C4, C5, C6, C7 and C8; D2, D3, D4, D5, D6, D7, D8, D9, D10, D11 and 1 more; E2, E6, E7, E8, E9 and E10; F2, F6, F7, F8, F9 and F10; G1, G2, G3, G4, G5, G6, G7 and G8; H2, H6, H7, H8 and H9.
Step by step
- Girvan-Newman removes edges one at a time until the graph falls apart into k = 8 communities. Before each removal it scores every edge by its betweenness: the number of shortest paths between pairs of vertices that cross it, with tied shortest paths sharing the credit. Then it removes the edge with the highest score. The graph starts as one community.
- Remove the edge between B1 and B3. Its betweenness, 609, is the highest. The graph is still in one piece.
- Remove the edge between B1 and B2. Its betweenness, 1131, is the highest. That splits the graph into parts of 87 and 13 vertices, so there are now 2 communities.
- Remove the edge between E1 and E2. Its betweenness, 486, ties for the highest with the edge between F1 and F2, and it comes first in gograph's AllEdges order. That splits a community of 87 into parts of 81 and 6 vertices, so there are now 3 communities.
- Remove the edge between F1 and F2. Its betweenness, 450, is the highest. That splits a community of 81 into parts of 75 and 6 vertices, so there are now 4 communities.
- Remove the edge between D1 and D3. Its betweenness, 384, is the highest. There are still 4 communities.
7 more steps lead to the last one:
- Done. Removing 12 edges left 8 communities.
Use it in Go
communities, err := partition.GirvanNewman(g, 8)
if err != nil {
return err
}
for _, c := range communities {
var members []string
for _, v := range c.GetAllVertices() {
members = append(members, v.Label())
}
fmt.Println(members)
}
Example graphs
- Friend groups, 12 vertices and 21 edges
- Office network, 13 vertices and 16 edges
- Karate club, 34 vertices and 78 edges
- Campus network, 100 vertices and 114 edges
More in Partitioning
- Maximal cliques: Finds every group of vertices that are all adjacent to each other and can't take one more vertex.
- Randomized k-cut: Splits an undirected graph into k groups by merging the ends of random edges until k groups are left, and cuts the edges between them.