8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Szabolcs Oct 25 '15 at 16:42
11
$\begingroup$

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`

Mathematica graphics

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 :)

$\endgroup$
  • $\begingroup$ thank you - very helpful. Clive $\endgroup$ – clive elphick Sep 29 '15 at 21:24
  • $\begingroup$ @cliveelphick If you find any problems with these packages, please let me know! $\endgroup$ – Szabolcs Sep 29 '15 at 21:36
  • $\begingroup$ I have posted a third, much simpler answer to this question, and would be grateful for a comment. Thank you. $\endgroup$ – Ralph Dratman Oct 23 '15 at 14:31
5
$\begingroup$
  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]
$\endgroup$
  • $\begingroup$ 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}]];. $\endgroup$ – Szabolcs Oct 23 '15 at 15:53
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Oct 23 '15 at 15:56
  • $\begingroup$ 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? $\endgroup$ – Ralph Dratman Oct 23 '15 at 16:14
  • $\begingroup$ With the Cliquer library (last section in my answer) it takes 0.01 seconds. $\endgroup$ – Szabolcs Oct 23 '15 at 16:15
  • $\begingroup$ My application requires the actual cliques rather than just how many there are. $\endgroup$ – Ralph Dratman Oct 23 '15 at 16:19
1
$\begingroup$

A naive approach is to enumerate all ${n \choose r}$ subsets, and for each check whether is is 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;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.