为什么在 Python 中使用 networkx 查找 3-cliques 结果不正确？

Question

我正在尝试使用 networkx 的 find_cliques 方法查找所有 3-cliques。但是，结果显示应该远远超过 2 个。请帮我弄清楚原因。

import networkx as nx
G = nx.Graph()
edges_fig_4 = [('a','b'),('a','c'),('a','d'),('a','e'),
           ('b','c'),('b','d'),('b','e'),
           ('c','d'),('c','e'),
           ('d','e'),('e','d'),
           ('f','b'),('f','c'),('f','g'),
           ('g','f'),('g','c'),('g','d'),('g','e')]
G.add_edges_from(edges_fig_4)
cliques = nx.find_cliques(G)
cliques3 = [clq for clq in cliques if 3<=len(clq)<= 3]

print(cliques3)

Answer 1

根据文档，find_cliques returns 所有最大派系。在您的情况下，存在大小大于 3 (abcde)(cdeg) 的派系，您还需要在更大的派系中拥有所有可能的 3 种组合。这是因为一个集团的每个子集团也是一个集团，但它不是最大的。

编辑：您还需要使用 set 来避免重叠的派系。

使用以下代码：

import itertools
cliques3 = set(sum([list(itertools.combinations(set(clq), 3)) for clq in cliques if len(clq)>=3],[]))

或者，使用 enumerate_all_cliques 也会给出大小（基数）k = 1, 2, 3, ..., maxDegree - 1 的派系。请参阅此处的文档：http://networkx.github.io/documentation/development/reference/generated/networkx.algorithms.clique.enumerate_all_cliques.html

为什么在 Python 中使用 networkx 查找 3-cliques 结果不正确？

Why the result is incorrect to find 3-cliques using networkx in Python?

python

networkx