在图中查找长度为 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

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