企业官网建设流程全解析

• 图计算
• 数据分析
• 科学计算

导读

本指南基于 NetworkX 的networkx.algorithms.clique模块（API 文档见 doc/reference/algorithms/clique.rst），系统讲解图中「团」（clique，完全子图）的查找、计数与图变换等 8 个核心函数的原理与用法。读完本文，你将掌握如何用find_cliques枚举最大团、用enumerate_all_cliques按规模枚举所有团、用max_weight_clique求解带节点权重的最大团，并能通过make_clique_bipartite/make_max_clique_graph将团结构转化为可进一步分析的图对象。文中所有示例均可直接在本地 Python 环境中运行。

背景：什么是团，为什么它很难算

团是图论中的基本概念：团（clique）是图中一个节点集合，其中任意两个不同节点之间都有边相连，即一个完全子图。最大团（maximal clique）指无法再并入任何一个相邻节点、继续扩充的团；而所有最大团中规模最大的那个被称为最大团（maximum clique），其规模称为图的团数（clique number）。

正如模块源码 networkx/algorithms/clique.py 开篇注释所指出的，寻找图中的最大团是NP 完全问题，因此本模块中的大部分算法在最坏情况下具有指数级运行时间。这意味着：

• 对完全图（complete graph）这类极端输入，团的数目会随节点数呈指数爆炸；
• 实际使用中应优先借助nodes参数缩小搜索范围，或复用已算出的团列表避免重复计算。

模块中所有团查找算法都忽略自环（self-loop）与平行边，因为团在传统定义中不包含这类边；这一点在 clique.py 的文档注释中有明确说明，测试 test_clique.py 也验证了添加自环后结果不变。

模块总览：8 个 API 一览

networkx.algorithms.clique通过 networkx/algorithms/init.py 的from networkx.algorithms.clique import *导出到nx命名空间，模块__all__定义于 clique.py：

除make_max_clique_graph与make_clique_bipartite外，其余函数（含内部辅助类MaxWeightClique）都标注了@not_implemented_for("directed")，即不支持有向图——传入DiGraph或MultiDiGraph会抛出NetworkXNotImplemented，测试 test_clique.py 对此有专门覆盖。

枚举所有最大团：find_cliques与find_cliques_recursive

算法原理

这两个函数基于Bron–Kerbosch 算法（1973 年发表，论文 "Algorithm 457: finding all cliques of an undirected graph"），并采用了 Tomita、Tanaka 与 Takahashi（2006）的改进（利用 pivot 节点减少递归分支），相关讨论参见 Cazals 与 Karande（2008）的综述；这三个参考文献均记录在 clique.py 的 docstring 中。

find_cliques是迭代式实现（clique.py）：它用一个显式stack模拟递归调用栈，因此不会遇到 Python 递归深度限制问题。find_cliques_recursive则是递归实现（clique.py），代码更贴合论文原始形态、便于教学理解，但在图中存在接近递归深度上限的大团时可能触发RecursionError——模块文档明确提示了这一点，并建议生产环境优先使用迭代版本。

基本用法

import networkx as nx G = nx.karate_club_graph() # Zachary 空手道俱乐部图，34 个节点 # 统计最大团的数量 sum(1 for c in nx.find_cliques(G)) # 36 # 找出最大的最大团（即最大团） max(nx.find_cliques(G), key=len) # [0, 1, 2, 3, 13] # 图的团数（最大团规模） max(len(c) for c in nx.find_cliques(G)) # 5 # 递归版本结果一致 cl = list(nx.find_cliques_recursive(G))

用nodes参数加速定向查询

find_cliques与find_cliques_recursive都接受可选参数nodes：只返回同时包含这些节点的最大团，可显著加快针对特定节点的搜索。前提是传入的nodes本身必须构成一个团，否则抛出ValueError（错误信息形如 "The givennodes... do not form a clique"，见 clique.py）。

# 只返回包含节点 31 的最大团 [c for c in nx.find_cliques(G) if 31 in c] # [[0, 31], [33, 32, 31], [33, 28, 31], [24, 25, 31]] # 直接传 nodes 参数，效果相同且更快 list(nx.find_cliques(G, nodes=[31]))

上述空手道俱乐部示例来自 clique.py 的 docstring，测试 test_clique.py 则用 Havel–Hakimi 图系统验证了nodes=None、[2]、[2,3]、[2,6,4]四种情形下的最大团输出，并确认[2,6,4,1]（非团）会触发ValueError。

按规模枚举所有团：enumerate_all_cliques

find_cliques系列只产出最大团，而enumerate_all_cliques产出图中所有团，且严格按规模从小到大排序：先是所有单点团，再是规模为 2 的团，依此类推（clique.py）。其实现改编自 Zhang 等人 2005 年的论文（"Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology"），通过一个队列维护当前候选节点列表，用生成器（chain与filter/islice组合）降低内存占用。

G = nx.Graph() G.add_edges_from([("a", "b"), ("b", "c"), ("a", "c"), ("c", "d")]) cliques = list(nx.enumerate_all_cliques(G)) # 按规模输出：先单点，再两点，再三点…… # [['a'], ['b'], ['c'], ['d'], # ['a', 'b'], ['a', 'c'], ['b', 'c'], ['c', 'd'], # ['a', 'b', 'c']] sizes = [len(c) for c in cliques] assert sorted(sizes) == sizes # 输出规模非递减

测试 test_clique.py 使用论文 Fig. 4 的 7 节点图，验证了 45 个团的完整输出列表与规模有序性。需要注意：若图是完整图，所有团的数量为2^n - 1（指数级），务必通过迭代器消费而非一次性list()化。

统计类 API：node_clique_number与number_of_cliques

节点所在的最大团规模：node_clique_number

node_clique_number返回每个给定节点所在最大最大团的规模（clique.py）：

• nodes传入单个节点 → 返回int；
• nodes传入列表或None→ 返回dict，键为节点、值为规模。

G = nx.complete_graph(3) nx.add_cycle(G, [0, 3, 4]) # 在 0-3-4 上加一个环 nx.node_clique_number(G, nodes=0) # 3（0 所在的 K3） nx.node_clique_number(G, nodes=1) # 3 nx.node_clique_number(G) # {0: 3, 1: 3, 2: 3, 3: 2, 4: 2}

实现细节：当nodes非空时，源码会先用nx.ego_graph收缩到目标节点的邻居子图再求团，从而显著减小搜索规模；当cliques参数提供了已算出的团列表时则直接复用，避免重复运行指数级算法。

节点属于的最大团数量：number_of_cliques

number_of_cliques统计每个节点同时属于多少个最大团（clique.py）。它接受三种调用形态，返回类型同样取决于nodes是单值还是列表：

G = nx.complete_graph(3) nx.add_cycle(G, [0, 3, 4]) nx.number_of_cliques(G, nodes=0) # 2 nx.number_of_cliques(G, nodes=[0, 1]) # {0: 2, 1: 1} nx.number_of_cliques(G) # {0: 2, 1: 1, 2: 1, 3: 1, 4: 1} # 预计算团列表，多次调用时避免重复搜索 cl = list(nx.find_cliques(G)) nx.number_of_cliques(G, cliques=cl) # 结果同上

从源码看，列表分支通过Counter(chain.from_iterable(cliques))一次性完成所有计数（clique.py），比逐节点扫描更高效。测试 test_clique.py 覆盖了单节点、节点列表、cliques预计算等全部参数组合。

团结构图变换：make_clique_bipartite与make_max_clique_graph

团-节点二分图：make_clique_bipartite

make_clique_bipartite将原图G转换为一个二分图（clique.py）：

• 底部节点：原图G的节点，带节点属性bipartite=1；
• 顶部节点：G的每个最大团，用负整数-1, -2, -3, …作为标签，带节点属性bipartite=0；
• 边：原节点v与团节点C之间有边，当且仅当v ∈ C。

这符合 NetworkX 二分图的约定（bipartite属性取 0/1），便于后续用networkx.algorithms.bipartite中的投影、匹配等工具继续处理。

G = nx.Graph([(1, 2), (2, 3), (3, 1), (3, 4)]) B = nx.make_clique_bipartite(G) sorted(B) # [-4, -3, -2, -1, 1, 2, 3, 4] # 负编号节点代表团，正编号节点是原图节点

fpos参数若为真值，返回图会额外携带pos属性（节点到平面坐标的映射），便于直接绘图。测试 test_clique.py 验证了：把二分图投影回原节点后邻接关系与原图完全一致（H.adj == G.adj）。

最大团图：make_max_clique_graph

make_max_clique_graph构建最大团图：节点为G的所有最大团，两个团节点之间连边当且仅当它们共享至少一个原图节点（即不相交才无边）（clique.py）。

G = nx.Graph([(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 6), (6, 4)]) M = nx.make_max_clique_graph(G) # M 的节点数 = G 的最大团数 list(M.edges()) # 团间存在交集则连边

源码 docstring 给出了它与二分图方法的等价关系：make_max_clique_graph等价于「先make_clique_bipartite，投影到团节点，再把负编号重标号为 0 起算的非负整数」三步操作，但直接实现跳过了全部中间步骤、速度更快。测试 test_clique.py 验证了两条路径产出的图邻接矩阵完全一致，且create_using参数可指定输出图类型（如nx.Graph）。

带权重场景：max_weight_clique分支定界求解器

问题定义与参数

最大权重团问题：给每个节点赋予整数权重，团的权重为其所有节点权重之和，目标是找到权重最大的团。当所有权重都取 1 时，该问题退化为普通最大团问题。

max_weight_clique(G, weight="weight")返回(clique, weight)元组（clique.py）：

• weight：指定存放权重的节点属性名，默认"weight"；传None表示每个节点权重均为 1（等价于求最大团）；
• 若某个节点缺少指定的权重属性，抛出KeyError；若权重值不是整数，抛出ValueError——这两类校验在辅助类MaxWeightClique.__init__中完成（clique.py），对应测试 test_max_weight_clique.py。

G = nx.Graph() G.add_nodes_from([1, 2, 3]) G.add_edges_from([(1, 2), (1, 3), (2, 3)]) G.nodes[1]["weight"] = 10 G.nodes[2]["weight"] = 20 G.nodes[3]["weight"] = 5 clique, weight = nx.max_weight_clique(G) # clique=[2, 1], weight=30（虽然 K3 本身权重 35 更大吗？不——K3 权重为 35，见下方说明）

注意：最大权重团不一定是最大团——上例中三元完全图的权重为 35，此时返回的就是[2, 1, 3]、权重 35。要观察「大团不如权重集中」的现象，可构造两个节点权重远大于第三个节点的场景（如测试用例two_node_graph：节点 1 权重 10、节点 2 权重 20，无边时答案仍为[2, 1]权重 30 之外，还需两个节点有边相连）。测试套件 test_max_weight_clique.py 中的TEST_CASES提供了空图、单点图、两点图、三点团、独立集、不连通图共 6 组基准，并验证了 30 节点稀疏图上期望权重 111 的求解结果。

实现原理：带剪枝的分支定界

max_weight_clique由内部辅助类MaxWeightClique（clique.py）驱动，核心是分支定界（branch and bound）：

1. 初始化：按度降序排列节点，并剔除权重 ≤ 0 的节点（clique.py），这有助于更快找到优质可行解；
2. 递归展开expand(C, C_weight, P)：C是当前构造中的团，P是候选扩展节点集；每进入一层先尝试用C更新最优解（update_incumbent_if_improved）；
3. 贪心独立集上界：find_branching_nodes在候选集中贪心构造加权独立集覆盖，以估算「还能增加多少权重」的上界；当上界不超过当前最优解时立即剪枝（clique.py）；
4. 分支：在剪枝后剩余的节点上逐个尝试扩展并递归。

源码注释指出，该算法与 Tavares et al. (2015) 的算法高度相似（NetworkX 版本不使用 bitset 加速），其「最大权重团 = 补图上的最大权重独立集」思路可追溯到 Warren & Hicks (2016) 的 Algorithm B。由于是递归实现，若图中存在节点数接近递归深度上限的大团，仍可能遇到递归深度问题（clique.py 对此有明确警告）。

实战：把 8 个 API 串成一条分析流水线

以一个典型社区发现场景为例，串联本模块的各类 API：

import networkx as nx from collections import Counter from itertools import chain G = nx.karate_club_graph() # 1. 枚举全部最大团 max_cliques = list(nx.find_cliques(G)) # 2. 团的规模分布 print(sorted(Counter(len(c) for c in max_cliques).items())) # 3. 每个节点参与的团数（识别「枢纽节点」） involvement = nx.number_of_cliques(G) print(involvement[0], involvement[33]) # 0 号与 33 号节点参与团数最多 # 4. 每个节点所在最大团的规模 clique_size = nx.node_clique_number(G) print(clique_size[0]) # 5 # 5. 团重叠图：节点=团，边=共享成员 overlap = nx.make_max_clique_graph(G) # 6. 团-成员二分图（便于可视化或投影分析） B = nx.make_clique_bipartite(G) # 7. 给节点加权重后求最大权重团 for i, w in nx.degree(G): G.nodes[i]["weight"] = w best_clique, best_weight = nx.max_weight_clique(G) print(best_clique, best_weight)

小结与选型建议

所有 API 的权威行为说明、参数细节与文献出处，可直接查阅模块源码 networkx/algorithms/clique.py 及各函数 docstring；行为正确性由 test_clique.py 与 test_max_weight_clique.py 两个测试套件保障，可作为深入学习与回归验证的参考。最后再次提醒：团问题是 NP 完全的，对稠密大图应谨慎使用，优先利用nodes参数、预计算cliques与权重剪枝来控制计算规模。

• 图计算
• 数据分析
• 科学计算