0

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

cliques = graph.cliques()

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

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

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

justTheCliques edge-list > cliques

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

4

2 回答 2

2

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

于 2014-09-03T16:53:42.050 回答
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
于 2014-09-04T00:05:39.017 回答