R:使用 igraph 有效地查找特殊大小的团

Question

我有一个大图(100000 个节点)，我想找到它的大小为 5 的团。我使用这个命令来实现这个目标:

cliques(graph, min=5, max=5) 

计算此操作需要花费大量时间。似乎它首先尝试找到图中的所有最大派系，然后选择大小为 5 的派系；我猜这是因为这两个命令在执行相同的工作时运行时间存在巨大差异:

adjacent.triangles (graph)  # takes about 30s
cliques(graph, min=3, max=3)    # takes more than an hour

我正在寻找像 adjacent.triangles 这样的命令来有效地找到大小为 5 的 clique。

谢谢

Answer 1

adjacent.triangles() 和 cliques() 之间存在巨大差异。 adjacent.triangles() 只需要计算 三角形，而 cliques() 需要存储它们。如果有很多三角形，这可以很容易地解释时间差异。 (另一个因素是 cliques() 中的算法是通用的，不限于三角形 - adjacent.triangles() 可能包含一些优化，因为我们知道我们只对三角形感兴趣)。

就其值(value)而言，cliques() 确实没有找到所有的最大团；它从 2-cliques(即边)开始，然后将它们合并为 3-cliques、4-cliques 等，直到达到您指定的最大大小。但是同样，如果你的图中有很多 3-cliques，这很容易成为瓶颈，因为算法中有一个点必须存储所有 3-cliques(即使你对它们不感兴趣)因为我们需要他们找到 4-cliques。

您最好先使用 maximal.cliques() 来大致了解图中的最大集团有多大。这里的想法是，您有一个大小为 k 的最大团，然后其大小为 5 的所有子集都是 5-团。这意味着搜索最大派系就足够了，保留大小至少为 5 的派系，然后枚举它们的所有大小为 5 的子集。但是你会遇到一个不同的问题，因为某些派系可能被计算多次。

更新:我已经检查了adjacent.triangles 的源代码，基本上它所做的就是遍历所有顶点，并且对于每个顶点v 它枚举所有 (u, w) 对它的邻居，并检查 u 和 w 是否连接。如果是这样，则在顶点 v 上有一个相邻的三角形。如果您有 n 个顶点且平均度数为 d，则这是一个 O(nd²) 操作，但它不会推广到组任意大小的顶点(因为您需要在代码中硬编码 k-1 嵌套 for 循环以获取一组大小 k)。