Find cliques of length k in a graph
I am working with plots of ~ 200 nodes and ~ 3500 edges. I need to find all the clicks of this graph. Using networkx enumerate_all_cliques()
works great with smaller graphs up to 100 nodes, but they have more memory for larger ones.
"This algorithm is hopefully not running out of memory as it only keeps candidates in memory and continually removes exhausted sublists. Source code for enumerate_all_cliques ()
Is there a way to return a generator of all k-length clicks rather than all clicks in order to save memory?
source to share
It seems like your priority is to save memory and not get all the clicks. In this case, using networkx.find_cliques (G) is a satisfactory solution, as you will get all the maximum clicks (the largest complete subgraph containing the given node) instead of all clicks.
I compared the number of lists (subgraphs) of both functions:
G = nx.erdos_renyi_graph(300,0.08)
print 'All:',len(list(nx.enumerate_all_cliques(G)))
print 'Maximal',len(list(nx.find_cliques(G)))
All: 6087
Maximum value 2522
And as the number of edges increases on the graph, the difference in results becomes wider.
source to share