python - 在图中查找长度为 k 的团

Question

我正在处理约 200 个节点和约 3500 个边的图形。我需要找到该图的所有派系。使用 networkx 的 enumerate_all_cliques() 适用于最多 100 个节点的较小图形，但对于较大的图形会耗尽内存。

"This algorithm however, hopefully, does not run out of memory since it only keeps candidate sublists in memory and continuously removes exhausted sublists."source code for enumerate_all_cliques()

有没有办法返回一个包含所有长度为 k 的团的生成器，而不是所有的团，以节省内存？

Answer 1

看来您的首要任务是节省内存而不是获取所有派系。在那种情况下使用 networkx.find_cliques(G)是一个令人满意的解决方案，因为您将获得所有最大派系(包含给定节点的最大完整子图)而不是所有派系。

我比较了两个函数的列表(子图)的数量:

G = nx.erdos_renyi_graph(300,0.08)
打印“全部:”，len(列表(nx.enumerate_all_cliques(G)))
打印 '最大',len(列表(nx.find_cliques(G)))

All: 6087

Maximal 2522

当图中的边数增加时，结果的差异会变大。