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

Question

我正在处理约 200 个节点和约 3500 条边的图。我需要找到这张图的所有派系。使用 networkxenumerate_all_cliques()可以很好地处理最多 100 个节点的较小图，但对于较大的图，内存不足。

“然而，这种算法希望不会耗尽内存，因为它只会将候选子列表保留在内存中并不断删除用尽的子列表。” enumerate_all_cliques() 的源代码

为了节省内存，有没有办法返回所有长度为 k 的派系的生成器，而不是所有派系？

Answer 1

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

我比较了两个函数的列表（子图）的数量：

G = nx.erdos_renyi_graph(300,0.08) print 'All:',len(list(nx.enumerate_all_cliques(G))) print 'Maximal',len(list(nx.find_cliques(G)))

全部：6087

最大 2522

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