我有一个大图（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 的集团。
谢谢
adjacent.triangles()和之间存在巨大差异cliques()。adjacent.triangles()只需要计算三角形，而cliques()需要将它们全部存储。如果有很多三角形，这可以很容易地解释时间差。（另一个因素是算法cliques()是通用的并且不限于三角形 - 它可能adjacent.triangles()包含一些优化，因为我们知道我们只对三角形感兴趣）。
对于它的价值，cliques()没有找到所有的最大派系；它从 2-cliques（即边缘）开始，然后将它们合并为 3-cliques、4-cliques 等，直到达到您指定的最大尺寸。但是同样，如果您的图中有很多 3-clique，这很容易成为瓶颈，因为算法中有一个点必须存储所有 3-clique（即使您对它们不感兴趣），因为我们需要他们找到 4-cliques。
您最好maximal.cliques()先大致了解图中的最大派系有多大。这里的想法是你有一个大小为k的最大集团，那么它的所有大小为 5 的子集都是 5 集团。这意味着搜索最大派系就足够了，保留至少大小为 5 的派系，然后枚举它们所有大小为 5 的子集。但是你有一个不同的问题，因为某些派系可能被计算多次。
更新：我检查了源代码adjacent.triangles，基本上它所做的只是循环所有顶点，并且对于每个顶点v，它枚举其邻居的所有(u, w)对，并检查u和w是否连接。如果是这样，则在顶点v上有一个相邻的三角形。如果您有n个顶点且平均度数为d ，则这是一个 O(nd 2 ) 操作，但它不能推广到任意大小的顶点组（因为您需要在代码中硬编码k -1 嵌套 for 循环一组大小为k )。