图计算数据分析科学计算【免费下载链接】networkxNetwork Analysis in Python项目地址https://gitcode.com/gh_mirrors/ne/networkx点击查看免费下载导读本指南基于 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函数功能返回enumerate_all_cliques(G)按规模从小到大枚举所有团含单点团迭代器元素为节点列表find_cliques(G, nodesNone)迭代式 Bron–Kerbosch枚举所有最大团迭代器元素为节点列表find_cliques_recursive(G, nodesNone)同上的递归版本迭代器元素为节点列表make_max_clique_graph(G, create_usingNone)构建最大团图团为节点、非不相交则连边NetworkX 图make_clique_bipartite(G, fposNone, create_usingNone, nameNone)构建团-节点二分图NetworkX 二分图node_clique_number(G, nodesNone, cliquesNone)每个节点所在的最大团规模int 或 dictnumber_of_cliques(G, nodesNone, cliquesNone)每个节点属于多少个最大团int 或 dictmax_weight_clique(G, weightweight)分支定界法求最大权重团(clique, weight)元组除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 与 Takahashi2006的改进利用 pivot 节点减少递归分支相关讨论参见 Cazals 与 Karande2008的综述这三个参考文献均记录在 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), keylen) # [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 图系统验证了nodesNone、[2]、[2,3]、[2,6,4]四种情形下的最大团输出并确认[2,6,4,1]非团会触发ValueError。按规模枚举所有团enumerate_all_cliquesfind_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()化。统计类 APInode_clique_number与number_of_cliques节点所在的最大团规模node_clique_numbernode_clique_number返回每个给定节点所在最大最大团的规模clique.pynodes传入单个节点 → 返回intnodes传入列表或None→ 返回dict键为节点、值为规模。G nx.complete_graph(3) nx.add_cycle(G, [0, 3, 4]) # 在 0-3-4 上加一个环 nx.node_clique_number(G, nodes0) # 30 所在的 K3 nx.node_clique_number(G, nodes1) # 3 nx.node_clique_number(G) # {0: 3, 1: 3, 2: 3, 3: 2, 4: 2}实现细节当nodes非空时源码会先用nx.ego_graph收缩到目标节点的邻居子图再求团从而显著减小搜索规模当cliques参数提供了已算出的团列表时则直接复用避免重复运行指数级算法。节点属于的最大团数量number_of_cliquesnumber_of_cliques统计每个节点同时属于多少个最大团clique.py。它接受三种调用形态返回类型同样取决于nodes是单值还是列表G nx.complete_graph(3) nx.add_cycle(G, [0, 3, 4]) nx.number_of_cliques(G, nodes0) # 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, cliquescl) # 结果同上从源码看列表分支通过Counter(chain.from_iterable(cliques))一次性完成所有计数clique.py比逐节点扫描更高效。测试 test_clique.py 覆盖了单节点、节点列表、cliques预计算等全部参数组合。团结构图变换make_clique_bipartite与make_max_clique_graph团-节点二分图make_clique_bipartitemake_clique_bipartite将原图G转换为一个二分图clique.py底部节点原图G的节点带节点属性bipartite1顶部节点G的每个最大团用负整数-1, -2, -3, …作为标签带节点属性bipartite0边原节点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_graphmake_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, weightweight)返回(clique, weight)元组clique.pyweight指定存放权重的节点属性名默认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], weight30虽然 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由内部辅助类MaxWeightCliqueclique.py驱动核心是分支定界branch and bound初始化按度降序排列节点并剔除权重 ≤ 0 的节点clique.py这有助于更快找到优质可行解递归展开expand(C, C_weight, P)C是当前构造中的团P是候选扩展节点集每进入一层先尝试用C更新最优解update_incumbent_if_improved贪心独立集上界find_branching_nodes在候选集中贪心构造加权独立集覆盖以估算「还能增加多少权重」的上界当上界不超过当前最优解时立即剪枝clique.py分支在剪枝后剩余的节点上逐个尝试扩展并递归。源码注释指出该算法与 Tavares et al. (2015) 的算法高度相似NetworkX 版本不使用 bitset 加速其「最大权重团 补图上的最大权重独立集」思路可追溯到 Warren Hicks (2016) 的 Algorithm B。由于是递归实现若图中存在节点数接近递归深度上限的大团仍可能遇到递归深度问题clique.py 对此有明确警告。实战把 8 个 API 串成一条分析流水线以一个典型社区发现场景为例串联本模块的各类 APIimport 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说明求所有最大团生产环境find_cliques迭代式无递归深度风险求所有最大团教学/理解算法find_cliques_recursive代码贴近 Bron–Kerbosch 论文按规模枚举所有团enumerate_all_cliques输出严格按规模递增只关心含特定节点的最大团find_cliques(G, nodes[...])传非团节点会抛ValueError节点级团统计node_clique_number/number_of_cliques可传入预计算cliques复用团结构二次分析make_clique_bipartite/make_max_clique_graph输出标准 NetworkX 图带权重的最大团max_weight_clique分支定界需整数权重所有 API 的权威行为说明、参数细节与文献出处可直接查阅模块源码 networkx/algorithms/clique.py 及各函数 docstring行为正确性由 test_clique.py 与 test_max_weight_clique.py 两个测试套件保障可作为深入学习与回归验证的参考。最后再次提醒团问题是 NP 完全的对稠密大图应谨慎使用优先利用nodes参数、预计算cliques与权重剪枝来控制计算规模。赞分享图计算数据分析科学计算【免费下载链接】networkxNetwork Analysis in Python项目地址https://gitcode.com/gh_mirrors/ne/networkx点击查看免费下载相关推荐mlx-community/LFM2.5-2.6B-4bit快速上手指南从安装到生成的完整流程mlx community/LFM2.5 2.6B 4bit快速上手指南从安装到生成的完整流程 mlx community/LFM2.5 2.6B 4bit是OI-wiki 最大团搜索详解Bron–Kerbosch 算法原理、剪枝优化与 C 实现OI wiki 最大团搜索详解Bron–Kerbosch 算法原理、剪枝优化与 C 实现 本篇技术指南以 OI wiki 图论章节的 最大团搜索文档 ht文档知识库教育教程DB-GPT GraphRAG 实战基于 TuGraph 的社区摘要知识图谱构建与混合检索全解析DB GPT GraphRAG 实战基于 TuGraph 的社区摘要知识图谱构建与混合检索全解析 本篇技术文章基于 DB GPT 官方文档 graph_rag人工智能AI 应用AI AgentRAG本地部署数据分析上一篇从限制到自由开源项目如何重塑智能音箱的音乐生态下一篇高效社交媒体数据采集5分钟搞定小红书抖音快手B站微博的智能爬虫工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考