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

I am trying to find all 3-cliques using networkx's find_cliques method. However, there should be far more than 2 as the result shows. Please help me to figure out why.

我试图使用networkx的find_cliques方法找到所有3个派系。但是,结果显示应该远远超过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)

1 个解决方案

#1

According to the document, find_cliques returns all maximal cliques. In your case there are cliques with size greater than 3 (abcde)(cdeg) and you will need to also have all possible 3-combination in that bigger clique. This is because each sub-clique of a clique is also a clique but it's not maximal.

根据该文档,find_cliques返回所有最大派系。在你的情况下,有大小大于3(abcde)(cdeg)的派系,你需要在那个更大的集团中拥有所有可能的3组合。这是因为一个集团的每个子集团也是一个集团,但它不是最大的。

EDIT: You will also need use set to avoid overlapped cliques.

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

Use the following code:

使用以下代码:

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

Alternatively, using enumerate_all_cliques will also give cliques of size (cardinality) k = 1, 2, 3, ..., maxDegree - 1. See the document here: http://networkx.github.io/documentation/development/reference/generated/networkx.algorithms.clique.enumerate_all_cliques.html

或者,使用enumerate_all_cliques也会给出大小的基数(基数)k = 1,2,3,...,maxDegree - 1.请参阅此处的文档:http://networkx.github.io/documentation/development/reference/生成/ networkx.algorithms.clique.enumerate_all_cliques.html

#1