NetworkX 3.1 版本深度解析:新特性、弃用变更与源码级原理

原创2026-09-20 16:54:461,705 阅读
文章标签:图计算科学计算数据可视化数据分析

NetworkX 3.1 版本深度解析:新特性、弃用变更与源码级原理

导读

NetworkX 3.1 是 2023 年 4 月 4 日发布的里程碑版本,也是最后一个支持 Python 3.8 的版本。本文基于仓库内官方发布说明 release_3.1.rst,结合当前仓库源码,深入解读该版本新增的简单环枚举、谱二分、Laplace 中心性等核心功能,剖析 single_target_shortest_path_length、forest_str 等 API 的弃用原因与迁移方案,并梳理后端调度(dispatch)基础设施的演进。读完本文,你将全面掌握 NetworkX 3.1 的改动全貌,并能正确迁移旧代码。

一、版本概览:3 个月、85+ PR 与 26 位贡献者

NetworkX 3.1 由 26 位贡献者历时 3 个月提交超过 85 个 pull request 完成,官方发布说明将其定位为一次"小步快跑"的版本:以 bug 修复与性能优化为主,同时为后续大版本铺路。

1.1 版本要点清单

依据 release_3.1.rst 的 Highlights 部分,本版本的核心要点包括:

  • 次要 bug 修复与速度提升:修复了 k_truss 对自环不抛出异常、空图负环函数抛异常等问题(见 PR #6521、PR #6473);
  • 插件化后端基础设施改进:为更多算法接入 dispatcher 调度机制,包括最短路径、BFS 系算法;
  • 文档小幅改进:大量 docstring 示例补充与链接修复;
  • 测试覆盖率提升:为 astar.py、edgelist.py、branchings.py、redundancy.py、clique.py、bipartite projection 等模块补充测试;
  • 最后一个支持 Python 3.8 的版本:官方明确 Python 3.8 支持止步于此版本;
  • 停止构建 PDF 版文档:移除 LaTeX/PDF 文档构建流程(对应 PR #5572);
  • 改用 Ruff 做 linting:以 Ruff 统一替代原有 lint 工具链,并同步用于 pyupgrade 与 isort(对应 PR #6371、#6441)。

1.2 支持的 Python 版本

Supports Python 3.8, 3.9, 3.10, and 3.11.

3.1 版本同时支持 Python 3.8~3.11 四个大版本。需要注意的是,3.8 在该版本后即停止支持,升级到 3.1 及以后版本的读者应规划 Python 版本迁移。

二、四大核心改进(Improvements)

发布说明列出了 4 项主要功能改进,以下逐一结合源码展开。

2.1 无向图的简单环枚举器

PR #6461 为无向图类新增简单环(simple cycle)枚举能力,实现在 networkx/algorithms/cycles.py 的 simple_cycles(G, length_bound=None) 函数中。

从源码看,该函数对无向图与有向图采用不同的分解策略:

  • 有向图:限制在强连通分量(strongly connected components)内,生成包含某节点的所有简单环后移除该节点,再对剩余部分继续分解;
  • 无向图:限制在双连通分量(biconnected components)内,生成包含某条边的所有简单环后移除该边,再继续分解剩余双连通分量。
import networkx as nx

# 无向图简单环枚举
G = nx.cycle_graph(5)
list(nx.simple_cycles(G))
# 输出示例(无向图中互为逆转的环视为同一个环)
# [[0, 1, 2, 3, 4], [0, 1, 2, 3], [0, 1, 2], [0, 1, 4, 3, 2], ...]

# 有向图示例(来自 docstring)
DG = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
sorted(nx.simple_cycles(DG))
# [[0], [0, 1, 2], [0, 2], [1, 2], [2]]

该函数还支持 length_bound 参数限制环长。length_bound=None 时使用 Johnson 算法的非递归迭代器/生成器版本,复杂度为 O((n+e)(c+1))(n 节点、e 边、c 个简单环);length_bound > 1 时改用 Gupta 与 Suzumura 的算法,复杂度为 O((c+n)(k-1)d^k)(d 为平均度,k 为长度上界)。

值得注意的边界语义:

  • 无向多重图中,一对平行边被视为长度为 2 的环;
  • 自环被视为长度为 1 的环;
  • 环以节点序列表示,因此环数与多重边、自环的存在无关。

2.2 基于 Fiedler 向量的谱二分(Spectral Bisection)

PR #6404 新增 spectral_bisection 函数,位于 networkx/linalg/algebraicconnectivity.py。它利用图的 Laplacian 矩阵第二小特征值对应的 Fiedler 向量,将图划分为两组节点:

import networkx as nx

G = nx.barbell_graph(3, 0)
nx.spectral_bisection(G)
# ({0, 1, 2}, {3, 4, 5})

从源码可见其核心逻辑非常简洁:先调用 nx.fiedler_vector 求得 Fiedler 向量 v,再按 v >= 0 与 v < 0 将节点集合一分为二并返回两个 set。该函数支持以下参数:

参数 默认值 说明
weight "weight" 边权重数据键,None 时每条边权重为 1
normalized False 是否使用归一化 Laplacian 矩阵
tol 1e-8 特征值计算的相对残差容差
method "tracemin_pcg" 特征值计算方法:TraceMIN(tracemin_pcg 预处理共轭梯度 / tracemin_lu LU 分解)、lanczos(Lanczos 迭代)或 lobpcg(LOBPCG)
seed None 随机数状态,控制特征值求解的随机性

该方法参考 Newman《Networks: An Introduction》第 364-370 页(见函数 docstring 的 References),适用于图分割、社区发现、并行计算负载均衡等场景,可配合 nx.fiedler_vector 与 nx.laplacian_matrix 使用。

2.3 create_using 对 Protocol Mixin 的支持

PR #6244 改进了 create_using 参数的解析逻辑,使其能够接受 typing.Protocol 类型的 Mixin。此前 create_using 只能接受具体的图类或图实例,现在可以基于协议进行更灵活的类型组合判断,这为第三方库通过 typing.Protocol 声明"支持 NetworkX 图接口"的自定义类接入 create_using 铺平了道路,属于后端(backend)基础设施的底层优化。

2.4 新增 Laplace 中心性度量

PR #5399(对应 issue #4973)新增 laplacian_centrality,实现在 networkx/algorithms/centrality/laplacian.py。

核心思想:节点 i 的 Laplace 中心性由删除该节点后图 Laplacian 能量的下降量衡量。Laplacian 能量定义为 Laplacian 矩阵特征值平方和:

C_L(u_i, G) = (ΔE)_i / E_L(G) = (E_L(G) - E_L(G_i)) / E_L(G)
E_L(G) = Σ λ_i²

其中 E_L(G) 为原图 Laplacian 能量,E_L(G_i) 为删除节点 i 后的能量,λ_i 为 Laplacian 矩阵特征值。该公式给出归一化值;不归一化时返回右式分子。

import networkx as nx
from networkx.algorithms.centrality.laplacian import laplacian_centrality

G = nx.Graph()
edges = [(0, 1, 4), (0, 2, 2), (2, 1, 1), (1, 3, 2), (1, 4, 2), (4, 5, 1)]
G.add_weighted_edges_from(edges)
sorted((v, f"{c:0.2f}") for v, c in laplacian_centrality(G).items())
# [(0, '0.70'), (1, '0.90'), (2, '0.28'), (3, '0.22'), (4, '0.26'), (5, '0.04')]

参数说明:

参数 默认值 说明
normalized True 为 True 时按全图能量归一化,使所有节点分数和为 1;为 False 时返回删除节点导致的能量绝对下降量
nodelist None 指定矩阵行列的节点顺序;为 None 时按 G.nodes() 排序
weight "weight" 构造 Laplacian 矩阵的边权重键,None 时权重均为 1
walk_type None 仅对有向图生效,传给 directed_laplacian_matrix:"random"、"lazy" 或 "pagerank";为 None 时按图性质自动选择(强连通且非周期→random,强连通但周期→lazy,其余→pagerank)
alpha 0.95 有向图 pagerank 游走中的遥跳参数,1-alpha 为遥跳概率

边界条件(源码中明确处理):

  • 空图(null graph)抛出 NetworkXPointlessConcept;
  • 无边的图在请求归一化时抛出 ZeroDivisionError(全图能量为 0),不归一化时返回全 0 字典;
  • nodelist 含重复节点或不存在节点时抛出 NetworkXError。

算法参考 Qi 等人 2012 年发表于 Information Sciences 的论文《Laplacian centrality: A new centrality measure for weighted networks》,对有向图的扩展借助 directed_laplacian_matrix 实现。该函数通过 @nx._dispatchable(edge_attrs="weight") 装饰,可被第三方后端调度。

三、弃用与迁移指南(Deprecations)

3.1 版本包含两项明确的弃用声明,均计划在 v3.3 落地或完成替换,请务必关注。

3.1 最短路径函数返回值统一(v3.3 生效)

PR #6564 与 #6567 弃用了两个函数当前的返回值形式:

  1. single_target_shortest_path_length:位于 networkx/algorithms/shortest_paths/unweighted.py,当前返回字典,v3.3 起返回值将改为迭代器(dict 的子类迭代视图);
  2. shortest_path 的 all_pairs 用法:当前对多对节点返回嵌套结构,v3.3 起将改为返回迭代器。

迁移提示:若你的代码依赖这些函数返回的字典结构(如直接下标访问 result[node]),在升级到 v3.3 前应改用 dict(...) 显式包装,或改为遍历迭代器的写法,以保证前向兼容。

3.2 forest_str 弃用:改用 write_network_text

PR #5602 弃用 forest_str 函数,推荐使用新增的 write_network_text / generate_network_text(即"network text"文本可视化能力,旧称 graph_str),实现在 networkx/readwrite/text.py 与 networkx/readwrite/text.py。

import networkx as nx

G = nx.path_graph(3)
nx.write_network_text(G)
# ╙── 0
#     └── 1
#         └── 2

generate_network_text 负责生成文本行的迭代器,write_network_text 负责输出到文件或标准输出,两者共同取代了早期 forest_str 的树形文本渲染能力,支持无向图、有向图与多重图的可读化终端展示。

四、后端调度(Dispatch)基础设施演进

3.1 版本对插件化后端(backend)基础设施投入了大量精力,发布说明中可见多条相关 PR:

  • 为更多最短路径算法接入调度(PR #6415),并允许第一个参数以关键字形式传给 dispatcher(PR #6471);
  • 为更多 BFS 系算法接入调度(PR #6467);
  • 新增 nx-loopback 后端测试机制(PR #6536),用于验证调度流程本身;调整 test_override_dispatch 以支持 G 关键字(PR #6499);
  • 忽略弱引用检查内存泄漏(PR #6466),修复了测试中因弱引用导致的误报。

从源码看,3.1 中新增/改进的算法大量使用了 @nx._dispatchable 装饰器(如 laplacian_centrality、spectral_bisection、simple_cycles、最短路径与 BFS 系列),这是后端调度的统一入口:当传入图对象的类注册了对应后端时,算法调用会被转发给后端实现,实现"一处编写、多后端加速"的插件架构。

五、工程与质量改进

5.1 测试覆盖与缺陷修复

3.1 集中提升了多个模块的测试覆盖,同时修复了一批实际问题:

  • test_clique.py 新增测试(PR #6142)、test_directed.py 新增测试(PR #6208)、bipartite projection 测试改进(PR #6196)、convert_numpy 新增两个测试(PR #6455);
  • prim_mst_edges() 在提升 mst.py 覆盖率过程中被发现并修复 bug(PR #6486);
  • k_truss 修复对自环不抛异常的问题(PR #6521);
  • 负环检测函数修复对空图抛异常的问题(PR #6473);
  • read_graph6 改用生成器以降低内存占用(PR #6519);
  • similarity.py 清理重构并使用 dataclass 存储状态(PR #5831)。

5.2 文档、构建与工具链

  • 移除 PDF/LaTeX 文档构建(PR #5572),此后文档仅提供 HTML 形式;
  • 接入 Ruff(PR #6371、#6441)用于 lint、pyupgrade 与 isort,并在 git-blame-ignore 中登记相关提交;
  • 修复多处文档链接与格式警告,为 dorogovtsev_goltsev_mendes、paley 等生成器补充 docstring;
  • 为 weighted.py、dag.py、boundary.py、mst.py 等补充 docstring 示例,统一最短路径与加权算法文档中的返回值描述(PR #6528、#6568);
  • gexf 写入器的 viz 属性 alpha 默认值调整(PR #6612);
  • weisfeiler_lehman_subgraph_hashes、ismags.py docstring 修正(PR #6598、#6600);
  • UnionAtlas 修复 len 操作(PR #6478);移除 random.sample 对 set 的调用以适配 Python 3.9 弃用(PR #6380)。

六、开发者视角:升级与迁移清单

综合以上分析,从 3.0 升级到 3.1 时建议按以下清单自查:

  1. Python 版本:确认运行环境在 Python 3.8~3.11 之间;若使用 3.8,请规划后续版本升级(3.1 是最后支持 3.8 的版本);
  2. 搜索弃用 API:全局搜索 single_target_shortest_path_length、shortest_path(all_pairs 用法)与 forest_str,按上文迁移方案改造;
  3. 利用新功能:图分割场景可尝试 nx.spectral_bisection;加权网络节点重要性分析可使用 nx.laplacian_centrality;无向图的环结构分析可直接使用 nx.simple_cycles;
  4. 后端生态:若你维护第三方后端或自定义图类,关注 @nx._dispatchable 调度范围的扩大,以及 create_using 对 Protocol Mixin 的新支持;
  5. 构建配置:文档 PDF 构建已被移除,仅依赖 HTML 文档的团队无需调整;lint 工具链已统一为 Ruff。

七、结语

NetworkX 3.1 作为衔接 3.0 大版本与后续迭代的过渡版本,在稳定性、测试质量与后端基础设施上持续深耕:新增的简单环枚举、谱二分与 Laplace 中心性扩展了算法工具箱,两项弃用声明为 v3.3 的返回值统一铺路,Ruff 与文档构建调整则优化了维护者工作流。理解本版本的改动,既能帮助现有用户平滑升级,也能为后续版本的 API 变化做好准备。完整的改动明细可查阅 doc/release/index.rst 下的各版本发布说明,以及 networkx/ 中对应的算法源码与测试。

登录后查看全文
networkx