为什么igraph的组()方法比justTheCliques慢几个数量级？

Question

我想在一个中等大小，但密集连通的图中找到所有的团，它有369个节点和22,724个边。首先，我简单地通过python接口调用igraph的Graph.cliques()方法：

cliques = graph.cliques()

它仍然在运行，并且在i7-4600 U核上消耗了超过3个小时的净cpu时间。因此，我开始考虑其他可能性，并记得几年前我已经使用过的一段很好的代码。它名为justTheCliques，可在这里获得：https://github.com/aaronmcdaid/MaximalCliques。描述说：

在边缘列表上运行Bron-Kerbosch算法。

运行此算法在几秒钟内给出相同图的结果：

justTheCliques edge-list > cliques

我喜欢照片，我只想知道，这背后的根本原因是什么？使用不同的算法？结果应该是一样的？

Answer 1

大卫是对的，如果你想要最大的集团，那么你应该使用maximal.cliques()。我做了一个快速的比较，看起来iGraph实际上比您使用的C++库快4-5，尽管这可能取决于您的图形：

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

Answer 2

看起来iGraph正使用像先验这样的算法来实现.cliques()。1-群是单顶点.K-群是两个(k-1)-cliques的联合，除了两个顶点外，它们之间都有一个边。我想这个算法明显不如图上的Bron--Kerbosch。如果您只需要最大的团，它看起来就像是.maximal_cliques()在使用类似B的算法。