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.

Time complexity O(V·E), gograph function partition.RandomizedKCut.

gograph picks the edges to contract at random, so the cut can change each time the server restarts.

How it works

The randomized k-cut starts with each vertex in its own group. It picks an edge at random, merges the groups at its two ends, and drops the edges that now run inside one group. It repeats until k groups are left. The edges still running between groups are the cut.

This is Karger's contraction method for the minimum cut, applied to k groups. A dense cluster has many edges, so a random edge is more likely to fall inside one, and clusters tend to merge before the few edges between them are picked. One run can still miss the smallest cut, so repeat it and keep the cut with the fewest edges.

One run costs O(V·E). k must be at least 2 and no more than the number of vertices. If the graph has more than k connected components, the edges run out first and each component is its own group. Use it to split a network into parts with few links between them, such as friend groups or shards of a service map.

Maze

A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.

An undirected graph with 30 vertices and 31 edges.

Split the maze into 4 regions and try to close as few passages as possible.

On this run, the cut splits the vertices into 4 groups, of 26, 2, 1 and 1 vertices, and cuts 3 edges: C5 and D5; D6 and E6; E5 and E6.

Step by step

  1. Randomized k-cut starts with each of the 30 vertices as a supernode of its own. gograph shuffles the edges and takes them in that order. An edge between two supernodes is contracted: the two merge into one, and the edges between them now lie inside it and are dropped. It stops when k = 4 supernodes are left, and the edges between them form the cut. These steps contract only edges inside the supernodes gograph ended with, in the graph's edge order, so they end in the same cut.
  2. Contract the edge between A1 and A2. A1 and A2 form a supernode of 2 vertices. 29 supernodes are left.
  3. Contract the edge between A2 and A3. A3 joins the supernode of A1 and A2, which now has 3 vertices. 28 supernodes are left.
  4. Contract the edge between A3 and B3. B3 joins the supernode of A1, A2 and A3, which now has 4 vertices. 27 supernodes are left.
  5. Contract the edge between A4 and A5. A4 and A5 form a supernode of 2 vertices. 26 supernodes are left.
  6. Contract the edge between A4 and B4. B4 joins the supernode of A4 and A5, which now has 3 vertices. 25 supernodes are left.

21 more steps lead to the last one:

  1. Done. After 26 contractions, k = 4 supernodes are left, so the contraction stops. The 3 edges between different supernodes form the cut. Every vertex now shows its supernode.

Use it in Go

cut, err := partition.RandomizedKCut(g, 4)
if err != nil {
	return err
}
for _, group := range cut.Supernodes {
	var members []string
	for _, v := range group {
		members = append(members, v.Label())
	}
	fmt.Println(members)
}
for _, e := range cut.CutEdges {
	fmt.Println(e.Source().Label(), e.Destination().Label())
}

Example graphs

More in Partitioning

  • Maximal cliques: Finds every group of vertices that are all adjacent to each other and can't take one more vertex.
  • Girvan-Newman: Splits a graph into k communities by removing, one at a time, the edge that the most shortest paths cross.

All algorithms