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

Question

我想找到中等大小但密集连接的图形中的所有团，该图形具有 369 个节点和 22,724 条边。首先我简单的通过python接口(interface)调用了igraph的Graph.cliques()方法:

cliques = graph.cliques()

它仍在运行，并且在 i7-4600U 内核上消耗了超过 3 小时的净 CPU 时间。因此我开始寻找其他的可能性，我想起了几年前我已经用过的一个很好的代码。它被称为 justTheCliques，可在此处获得:https://github.com/aaronmcdaid/MaximalCliques .描述说:

runs the Bron-Kerbosch algorithm on an edge list

运行此算法会在几秒钟内在同一张图上给出结果:

justTheCliques edge-list > cliques

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

Answer 1

看起来 igraph 正在使用类似 apriori 的算法因为它实现了 .cliques()。 1-cliques 是单个顶点。 k-cliques 是两个 (k-1)-cliques 的并集，除了两个顶点之外，它们共享所有顶点，它们之间有一条边。我想这个算法在你的图表上明显不如 Bron--Kerbosch。如果您只需要最大派系，它看起来好像 .maximal_cliques() 使用的是类似 B--K 的算法。