number_of_cliques和max_clique计算的是什么？

Question

我不确定max_clique做了什么，number_of_cliques做了什么

from networkx.algorithms.approximation import clique
clique.max_clique(G)

和

clique.number_of_cliques(G)

从doc看不清楚

Answer 1

max_clique希望找到图中最大(或最大)的集团。它将返回一组形成集团的节点，合理的可能性是网络中没有更大的集团。它是近似的，因为计算本身是昂贵的(NP-完全)。https://en.wikipedia.org/wiki/Clique_problem

number_of_cliques (至少在networkxv2.2中)返回一个dict，它的键是图的节点，其值是给定节点所在的最大团的数量。极大团是指如果0-1，0-2，1-2和0-3是边，则节点0的最大团是{0,1,2}和{0,3}。集团{0,1}不计入，因为它包含在更大的集团中。节点1和2各有一个最大团{0,1,2}，节点3有一个最大团{0,3}。因此，number_of_cliques返回dict {0:2, 1:1, 2:1, 3:1}。

Answer 2

这是一个示例：

import networkx as nx
G1 = nx.Graph()
edges = [(1, 2), (2, 3), (1, 3), (3, 4), (3, 0),(1, 4),(4, 2)]
G1.add_edges_from(edges)
nx.draw_networkx(G1)

​

​

res = nx.find_cliques(G1)
cliques = [item for item in res]
cliques = sorted(cliques, key=lambda item: -len(item))
for item in cliques:
    print(item)

​

​

max_clique(G1)

​

​