求图中长度为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) print 'All:',len(list(nx.enumerate_all_cliques(G))) print 'Maximal',len(list(nx.find_cliques(G)))

All: 6087

Maximal 2522

当图中的边数增加时，结果的差异就越大。在