在图中找出长度为k的团 [英] Find cliques of length k in a graph

问题描述

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

然而，希望该算法不会耗尽内存 因为它只在内存中保存候选子列表，并且 连续删除耗尽的子列表。"source code for enumerate_all_cliques()

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

推荐答案

您的首要任务似乎是节省内存，而不是获取所有的小圈子。在这种情况下，使用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

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

这篇关于在图中找出长度为k的团的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！