How to count all cliques (not just maximal ones) in graphs?

How can I count the numbers of $r$-cliques in a graph? In other words, the number of triangles, the number of $K_4$, the number of $K_5$ etc. I have tried for example FindClique[G,{4},All], which finds all "isolated" $K_4$s but does not find $K_4$s in a larger clique. So for example if $G = K_5$ then FindClique[G,{4},All] does not find the 4-cliques within G but FindClique[G,{5},All] does find the 5-clique. Is there a simple way of doing this with a Mathematica command or is it necessary to compute the number of smaller cliques from the number of larger cliques?

• You can consider accepting Ralph's answer. It performs very well. In fact if the aim is to return all cliques (not just count them), I don't think it is at all technically possible to match it when using an external library, due to the performance limitations of Mathematica's C API. (I'm quite disappointed about that.) Commented Oct 25, 2015 at 16:42

Mathematica only finds maximal cliques, i.e. cliques (complete subgraphs) that are not part of a larger clique.

Computing the number of all cliques given the maximal ones is not trivial because some of the maximal cliques may be overlapping.

The simplest way to find all cliques is to use one of several packages that can do this.

g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];


IGraph/M

<<IGraphM


cliques = IGCliques[g, Infinity]

{{2}, {1}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, \
{14}, {17}, {18}, {20}, {22}, {26}, {24}, {25}, {28}, {29}, {30}, \
{27}, {31}, {32}, {33}, {15}, {16}, {19}, {21}, {23}, {34}, {2,
1}, {2, 3}, {2, 4}, {2, 8}, {2, 14}, {2, 18}, {2, 20}, {2, 22}, {2,
31}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1,
11}, {1, 12}, {1, 13}, {1, 14}, {1, 18}, {1, 20}, {1, 22}, {1,
32}, {3, 4}, {3, 8}, {3, 9}, {3, 10}, {3, 14}, {3, 28}, {3, 29}, {3,
33}, {4, 8}, {4, 13}, {4, 14}, {5, 7}, {5, 11}, {6, 7}, {6,
11}, {6, 17}, {7, 17}, {9, 31}, {9, 33}, {9, 34}, {10, 34}, {14,
34}, {20, 34}, {26, 24}, {26, 25}, {26, 32}, {24, 28}, {24,
30}, {24, 33}, {24, 34}, {25, 28}, {25, 32}, {28, 34}, {29,
32}, {29, 34}, {30, 27}, {30, 33}, {30, 34}, {27, 34}, {31,
33}, {31, 34}, {32, 33}, {32, 34}, {33, 15}, {33, 16}, {33,
19}, {33, 21}, {33, 23}, {33, 34}, {15, 34}, {16, 34}, {19,
34}, {21, 34}, {23, 34}, {2, 1, 3}, {2, 1, 4}, {2, 1, 8}, {2, 1,
14}, {2, 1, 18}, {2, 1, 20}, {2, 1, 22}, {2, 3, 4}, {2, 3, 8}, {2,
3, 14}, {2, 4, 8}, {2, 4, 14}, {1, 3, 4}, {1, 3, 8}, {1, 3, 9}, {1,
3, 14}, {1, 4, 8}, {1, 4, 13}, {1, 4, 14}, {1, 5, 7}, {1, 5,
11}, {1, 6, 7}, {1, 6, 11}, {3, 4, 8}, {3, 4, 14}, {3, 9, 33}, {6,
7, 17}, {9, 31, 33}, {9, 31, 34}, {9, 33, 34}, {26, 25, 32}, {24,
28, 34}, {24, 30, 33}, {24, 30, 34}, {24, 33, 34}, {29, 32,
34}, {30, 27, 34}, {30, 33, 34}, {31, 33, 34}, {32, 33, 34}, {33,
15, 34}, {33, 16, 34}, {33, 19, 34}, {33, 21, 34}, {33, 23, 34}, {2,
1, 3, 4}, {2, 1, 3, 8}, {2, 1, 3, 14}, {2, 1, 4, 8}, {2, 1, 4,
14}, {2, 3, 4, 8}, {2, 3, 4, 14}, {1, 3, 4, 8}, {1, 3, 4, 14}, {9,
31, 33, 34}, {24, 30, 33, 34}, {2, 1, 3, 4, 8}, {2, 1, 3, 4, 14}}

CountsBy[cliques, Length]
(* <|1 -> 34, 2 -> 78, 3 -> 45, 4 -> 11, 5 -> 2|> *)


Update: In IGraph/M 0.1.4 or later, we can directly count cliques, without listing them:

IGCliqueSizeCounts[g]
(* {34, 78, 45, 11, 2} *)


This release also significantly speeds up clique finding.

Since there is significant overhead in storing and transferring all the cliques back to Mathematica after computing them, IGCliqueSizeCounts can be many times faster than IGCliques. If you only need counts, use IGCliqueSizeCounts.

IGraphR

This needs a bit more work as the output of R/igraph's cliques command doesn't easily transfer to Mathematica.

<<IGraphR
REvaluate["cliqCounter <- function (g) { as.vector(table(sapply(cliques(g), length))) };"]

IGraph["cliqCounter"][g]
(* {34, 78, 45, 11, 2} *)


This gives you the number of cliques with sizes 1, 2, 3, 4 and 5.

MmaCliquer

This is a partial interface to Cliquer that I made for my own use. Currently it can only count cliques of different sizes, but not return the vertices they contain. This library is very fast for counting all cliques (but not so much for counting maximal ones).

Due to GPL issues you need to compile it yourself ...

<<Cliquer

CliquerDistribution[g]
(* {34, 78, 45, 11, 2} *)


Finally, just for some fun with IGraph/M's isomorphism functions:

Table[IGVF2SubisomorphismCount[CompleteGraph[i], g]/IGBlissAutomorphismCount@CompleteGraph[i], {i, 5}]

(* {34, 78, 45, 11, 2} *)


Of course this is extremely inefficient :)

• thank you - very helpful. Clive Commented Sep 29, 2015 at 21:24
• @cliveelphick If you find any problems with these packages, please let me know! Commented Sep 29, 2015 at 21:36
• I have posted a third, much simpler answer to this question, and would be grateful for a comment. Thank you. Commented Oct 23, 2015 at 14:31
• @Szabolcs How does one compile/install Cliquer? Running <<Cliquer in Linux returns Get::noopen: Cannot open Cliquer.
– Leo
Commented Apr 19, 2021 at 18:13
• @Leo Just use IGraph/M instead. It also uses cliquer. Commented Apr 19, 2021 at 20:06
1. Mathematica can return the set of all maximal cliques of a graph.
2. Any subset of clique vertices is also a clique.

So, this gives all cliques:

findAllCliques[g_] :=
DeleteDuplicates[Flatten[Map[Subsets, FindClique[g, Infinity, All]], 1]]


Try it:

n = RandomInteger[25];
m = RandomInteger[Binomial[n, 2]];
rgr = Graph[RandomGraph[{n, m}], VertexLabels -> "Name"];
allCliques = findAllCliques[rgr];
Print["n = ", n, "   m = ", m]
Print[Length@allCliques, " Cliques found"]
rgr
allCliques
Histogram@Map[Length, allCliques]

• Hi Ralph! Yes, this implementation is correct (but I would feel more comfortable if you used DeleteDuplicates[Sort /@ ...] just to be sure ...). One potential problem is that if the cliques overlap in a certain way, there may be an extreme number of duplicates to be removed, which will slow it down and will have high memory requirements. This is an example made to be difficult on purpose: n = 12; g = CompleteGraph[2 n]; g = EdgeDelete[g, Table[i <-> i + n, {i, n}]];. Commented Oct 23, 2015 at 15:53
• In practice though it seems to work much better than I expected. And the igraph function I recommended works much worse (much slower than your implementation). There's something wrong with it, I'll take a look later. Cliquer is still the winner by far. Commented Oct 23, 2015 at 15:56
• If I understand correctly, you present the graph built by your line of code for testing findAllCliques. That took about 20 seconds on my MacBook Air. Do you have timing for that using some other method?Question: in constructing your example, why did you generate CompleteGraph[24] and then delete some of its edges? Commented Oct 23, 2015 at 16:14
• With the Cliquer library (last section in my answer) it takes 0.01 seconds. Commented Oct 23, 2015 at 16:15
• My application requires the actual cliques rather than just how many there are. Commented Oct 23, 2015 at 16:19

A naive approach is to enumerate all $${n \choose r}$$ subsets, and for each check whether the subset induces an $$r$$-clique. Obviously, this does not scale nicely when $$r$$ gets larger, nor when $$n$$ starts to get larger.

For special cases, i.e., small values of $$r$$ you can do better. A neat algebraic graph-theoretic way of computing the number of triangles is given by $$\text{tr}(A^3)/6$$, where $$A$$ is the adjacency matrix of a graph $$G$$. For counting 3-cliques, we can simply do

TriangleCount[g_] := Tr[MatrixPower[AdjacencyMatrix[g], 3]]/6;