Odd behaviour of 'clique' function

Usage
1

Hello,
I am struggling with something appears odd. But it might be that I am the one off track.

I have a graph:
IGRAPH UN-- 8111 7531 –
+ attr: name (v)

When I run
cliques = graph.cliques(min=k, max=k)

and k=3 it returns 43906 cliques,
instead if k=4, it returns 231018 cliques. 5 times more.

If I am not mistaken, the higher is the size of the clique, the less cliques we would identify from the same network. Am I right?

But still I can’t explain why increasing k, increases the number of cliques.
Do you think, there is a problem with the implementation?

To help reproduce my probem, I am sharing the pickled network Dropbox - test_graph.pickle - Simplify your life.
To load it just run:
graph = Graph.Read_Pickle("test_graph.pickle")

Looking forward to hearing your insights.
Angelo

2

No. Consider a complete graph on n vertices. The number of k-cliques is then \binom{n}{k}, which increases with k up to n/2 and decreases from thereon. This is the typical pattern you will see in all dense graphs or graphs that have dense parts.

2 Likes
3

Ah! Makes sense now.

Thanks a lot.
Angelo