Maximal cliques

Finds every group of vertices that are all adjacent to each other and can't take one more vertex.

Time complexity O(3^(V/3)), gograph function partition.MaximalCliques.

How it works

A clique is a set of vertices where every two are joined by an edge. It is maximal when no other vertex is joined to all of them, so it can't grow. partition.MaximalCliques lists every maximal clique with the Bron-Kerbosch algorithm. It grows a clique one vertex at a time from a set of candidates, and keeps the vertices it has already tried so that no clique is listed twice.

gograph adds three things that make it faster. It starts from the vertices in degeneracy order, which keeps the candidate sets small in sparse graphs. At each step it picks a pivot and only branches on candidates that aren't the pivot's neighbors, since every maximal clique holds the pivot or one of those. And it stores the sets as bitsets, so comparing them is quick.

A graph can have up to 3^(V/3) maximal cliques, so no method is fast on every graph, but real networks are usually sparse enough. Edge directions are ignored, and so are self-loops. Use it to find tight groups of friends or devices that are all linked, where one vertex can belong to several groups.

Karate club

The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.

An undirected graph with 34 vertices and 78 edges.

Which groups of members all spent time with each other outside the club, where no other member spent time with all of them?

The graph has 36 maximal cliques. The 2 largest have 5 vertices each: 1, 2, 3, 4 and 8; 1, 2, 3, 4 and 14.

Step by step

  1. Bron-Kerbosch grows a clique R. P holds the vertices that can still join R, and X holds the ones that could join but whose cliques were listed already. The search starts once from each vertex, in degeneracy order: repeatedly remove the vertex with the fewest neighbors left. That keeps P small. Each call picks a pivot in P or X with the most neighbors in P and tries only the vertices of P that are not its neighbors.
  2. Start from 12, the first vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add 1 to R. P and X are both empty, so no other vertex is adjacent to both 12 and 1. Record them as maximal clique 1.
  3. Start from 16, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add 33 and 34 to R. P and X are both empty, so no other vertex is adjacent to all of 16, 33 and 34. Record them as maximal clique 2.
  4. Start from 17, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add 6 and 7 to R. P and X are both empty, so no other vertex is adjacent to all of 17, 6 and 7. Record them as maximal clique 3.
  5. Start from 18, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add 1 and 2 to R. P and X are both empty, so no other vertex is adjacent to all of 18, 1 and 2. Record them as maximal clique 4.
  6. Start from 19, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add 33 and 34 to R. P and X are both empty, so no other vertex is adjacent to all of 19, 33 and 34. Record them as maximal clique 5.

36 more steps lead to the last one:

  1. Done. Every vertex has been a start, and the search found 36 maximal cliques. The biggest has 5 vertices.

Use it in Go

for _, clique := range partition.MaximalCliques(g) {
	var names []string
	for _, v := range clique {
		names = append(names, v.Label())
	}
	fmt.Println(strings.Join(names, ", "))
}

Example graphs

More in Partitioning

  • Girvan-Newman: Splits a graph into k communities by removing, one at a time, the edge that the most shortest paths cross.
  • 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.

All algorithms