Enumerate cliques of size k only

[Yanshuo Sun]

I can use list(nx.enumerate_all_cliques(G)) to find all cliques in a graph. However, it is very slow in my case.

For example, one result is shown as follows:

# 4-clique found  196360

# 5-clique found  688072

# 6-clique found  1723971

# 7-clique found  3237896

...

I do not want to find all cliques; I only need those cliques of size k. k is a fixed parameter, e.g, 4 or 5.

Is there a way to modify enumerate_all_cliques(G)? Could anyone suggest other solutions?

Many thanks in advance.

YS

[Dan Schult]

Since enumerate_all_cliques yields the cliques in order of size, you could check the size of each yielded clique and ignore when less than k and stop when the size is bigger than k.  

I'm not surprised this is a slow function for even medium sized graphs. You should also consider avoiding the need for all cliques of a given size if you can.

​

[Dmitry Zinoviev]

Here's a code fragment that extracts all cliques of size up to 4, inclusive (it uses itertools.takewhile() to suppress the production of large cliques):

import itertools

...

cliques = list(itertools.takewhile(lambda x: len(x) <= 4, enumerate_all_cliques(G))

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To post to this group, send email to networkx...@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.

--

Dmitry Zinoviev, Professor of Computer Science, Suffolk University, Boston, MA 02114

Author of "Data Science Essentials in Python" and "Complex Network Analysis in Python"

https://pragprog.com/book/dzpyds/ https://pragprog.com/book/dzcnapy

[Yanshuo Sun]

Thank you for your reply, Dan.

In my current implementation, I use the following codes:

all_cliques = list(nx.enumerate_all_cliques(a_graph))

for each_clique_all_size in all_cliques :
    if len(each_clique_all_size) == 4:
        cli_4_list.append(sorted(each_clique_all_size))
    elif len(each_clique_all_size) == 5:
        cli_5_list.append(sorted(each_clique_all_size))

In this case, I only need 4-cliques and 5-cliques. Any larger cliques are not needed. However, all_cliques = list(nx.enumerate_all_cliques(a_graph)) will return all these 6-cliques, 7-cliques, etc. This step is very time-consuming.

I hope to find a way to stop nx.enumerate_all_cliques(a_graph) prematurely so that any cliques larger than k will not be generated in the first place.

I will try the code by Dmitry to see whether it helps.

Thanks again.

YS

[Dan Schult]

for each_clique_all_size in all_enumerate_all_cliques(G):
    if len(each_clique_all_size) < 4:

        continue

    elif len(each_clique_all_size) == 4:

        cli_4_list.append(sorted(each_clique_all_size))
    elif len(each_clique_all_size) == 5:
        cli_5_list.append(sorted(each_clique_all_size))

    else:
        break   # this stops after size 5 is done

--

You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.