I wanted to find all the cliques in a medium size, but densely connected graph, having 369 nodes and 22,724 edges. First I simply called igraph's Graph.cliques() method through the python interface:
cliques = graph.cliques()
It's still running, and consumed more then 3 hours net cpu time on an i7-4600U core. Therefore I started to look after other possibilities, and I remembered a nice code I already used few years before. It is called justTheCliques, and available here: https://github.com/aaronmcdaid/MaximalCliques. The description says:
runs the Bron-Kerbosch algorithm on an edge list
Running this algorithm gives result on the same graph within a few seconds:
justTheCliques edge-list > cliques
I love igraph, and I just want to know, what is the essential reason behind this? Igraph uses a different algorithm? The result should be the same?
David is right, if you want maximum cliques, then you should use maximal.cliques(). I did a quick comparison, and it seems that igraph is in fact 4-5 faster than the C++ library you used, although this probably depends on your graph:
library(igraph)
g <- erdos.renyi.game(369, 22724, type="gnm")
system.time(xx <- maximal.cliques(g))
# user system elapsed
# 1.432 0.012 1.448
write.graph(g, format = "edgelist", file = "graph.txt")
vagrant@logus:~/cli/MaximalCliques$ time ./justTheCliques graph.txt > cliques.txt
Network loaded after 0.15 seconds. 369 nodes and 22724 edges. Max degree is 149
processing node: 100 ...
processing node: 200 ...
processing node: 300 ...
388111 cliques found
0 #3
10367 #4
209815 #5
151633 #6
15896 #7
396 #8
4 #9
real 0m6.419s
user 0m5.324s
sys 0m1.036s