NetworkX 1.8 版本解析从线性时间图度序列检测到有向拉普拉斯矩阵的全面升级【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkx本篇技术指南围绕 NetworkX 1.8发布于 2013 年 7 月 28 日的官方发布说明展开系统梳理该版本引入的核心算法、性能优化与 API 变更并结合当前仓库源码逐项验证其实现原理。读者将掌握线性时间 graphicality 测试、Havel-Hakimi 图生成、有向拉普拉斯矩阵、Katz 中心性、全部简单路径枚举、加权二部图投影等功能的实际用法与迁移注意事项。版本概览NetworkX 1.8 是 Python 图分析库在 2013 年的一次重要功能版本重点在于算法效率提升与图论分析能力扩展。官方发布说明doc/release/api_1.8.rst列出了以下核心亮点更快的线性时间graphicality 测试与 Havel-Hakimi 图生成器有向拉普拉斯矩阵生成器Katz 中心性算法生成全部简单路径的函数改进的 shapefile 读取器更灵活的二部图加权投影更快的 DAG 拓扑排序、后代与祖先计算力导向布局的缩放参数该版本同时修复了若干已知缺陷并引入了三项需要使用者注意的 API 变更。下文逐一展开并给出当前仓库源码中的实现位置作为佐证。一、Highlights新增与增强功能详解1.1 线性时间 graphicality 测试与 Havel-Hakimi 图生成器graphicality度序列图性指判断一个整数序列是否能够被某个简单图实现为度序列。1.8 之前的相关实现效率不佳该版本将其优化为线性时间算法。当前仓库中图性测试的核心实现位于 networkx/algorithms/graphical.pyis_graphical(sequence, methodeg)统一入口默认使用Erdős-Gallai算法methodeg也可指定methodhh切换到Havel-Hakimi算法两者均通过_basic_graphical_tests先做快速否决负度数、度数不小于序列长度、度数和为奇数、过饱和等见 networkx/algorithms/graphical.py#L76-L93。is_valid_degree_sequence_havel_hakimi(deg_sequence)实现 Havel-Hakimi 定理的迭代削减最坏时间复杂度为 $O(s)$其中 $s$ 为序列度数之和networkx/algorithms/graphical.py#L97-L183。其先利用 Zverovich-ZverovichZZ条件快速判定可图性再循环取出最大度 stub削减其连接的 dmax 个最大 stub。is_valid_degree_sequence_erdos_gallai(deg_sequence)Erdős-Gallai 判据的等价形式最坏时间复杂度为 $O(n)$$n$ 为序列长度networkx/algorithms/graphical.py#L187-L240。配套的Havel-Hakimi 图生成器位于 networkx/generators/degree_seq.pyhavel_hakimi_graph(deg_sequence, create_usingNone)networkx/generators/degree_seq.py#L442按 Havel-Hakimi 构造法从度序列生成简单图。directed_havel_hakimi_graph(in_deg_sequence, out_deg_sequence, create_usingNone)networkx/generators/degree_seq.py#L535为有向图生成器要求入度与出度序列分别可图化。典型用法import networkx as nx seq [3, 3, 2, 2, 2, 2] # 一个可图序列 nx.is_graphical(seq) # True默认 Erdős-Gallai nx.is_graphical(seq, methodhh) # TrueHavel-Hakimi G nx.havel_hakimi_graph(seq) # 直接构造出该度序列对应的图 print(sorted(d for _, d in G.degree()))1.2 有向拉普拉斯矩阵生成器1.8 新增了针对有向图的规范化拉普拉斯矩阵函数directed_laplacian_matrix实现于 networkx/linalg/laplacianmatrix.py#L411-L503。其数学定义为$$L I - \frac{1}{2}\left(\Phi^{1/2} P \Phi^{-1/2} \Phi^{-1/2} P^T \Phi^{1/2}\right)$$其中 $P$ 是图的转移矩阵$\Phi$ 是以 $P$ 的 Perron 向量为对角线元素的对角矩阵源自 Fan Chung 关于有向图拉普拉斯与 Cheeger 不等式的经典工作。关键参数walk_type决定转移矩阵 $P$ 的构造方式可选random随机游走、lazy惰性随机游走或pagerank带传送概率的 PageRank 随机游走默认None时根据图的性质自动选择——强连通且非周期用random强连通但周期用lazy其余情况用pagerank。alphaPageRank 传送参数1 - alpha为传送概率默认0.95。weight边权重属性名默认weight设为None则所有边权重视为 1。实现细节上该函数通过eigs(P.T, k1)求解 Perron 向量并归一化最终结果恒为对称矩阵它基于图的出度计算如需基于入度可先G.reverse(copyFalse)再取转置。该文件还提供了directed_combinatorial_laplacian_matrixnetworkx/linalg/laplacianmatrix.py#L509作为组合型变体二者仅对DiGraph可用。import networkx as nx DG nx.DiGraph([(0, 1), (1, 2), (2, 0), (0, 2)]) L nx.directed_laplacian_matrix(DG, walk_typepagerank, alpha0.9)1.3 Katz 中心性算法Katz 中心性是特征向量中心性的推广衡量节点在网络中的相对影响力它不仅统计一跳邻居还通过衰减因子 $\alpha$ 计入远端邻居的贡献。定义式为$$x_i \alpha \sum_j A_{ij} x_j \beta$$其中 $\beta$ 为初始中心性可为标量或逐节点字典且必须满足 $\alpha 1/\lambda_{\max}$$\lambda_{\max}$ 为邻接矩阵最大特征值以保证幂迭代收敛。实现位于 networkx/algorithms/centrality/katz.py#L13-L120函数签名为katz_centrality(G, alpha0.1, beta1.0, max_iter1000, tol1.0e-6, nstartNone, normalizedTrue, weightNone)alpha衰减因子默认0.1必须严格小于最大特征值倒数max_iter/tol幂迭代的最大次数默认 1000与收敛误差默认1e-6不收敛时抛出PowerIterationFailedConvergencenormalized是否对结果归一化默认Trueweight边权重属性默认None无权此处权重解释为连接强度。官方文档示例路径图 $P_4$取 $\alpha 1/\phi - 0.01$$\phi$ 为黄金比例即略小于最大特征值倒数import math G nx.path_graph(4) phi (1 math.sqrt(5)) / 2.0 # 邻接矩阵最大特征值 centrality nx.katz_centrality(G, 1 / phi - 0.01) for n, c in sorted(centrality.items()): print(f{n} {c:.2f}) # 0 0.37 / 1 0.60 / 2 0.60 / 3 0.37同模块还提供katz_centrality_numpy用于基于稠密线性代数的求解。需注意该函数标注not_implemented_for(multigraph)不适用于多重图。1.4 生成全部简单路径的函数all_simple_paths(G, source, target, cutoffNone)用于枚举图中从source到target的所有简单路径不重复经过节点的路径实现于 networkx/algorithms/simple_paths.py#L95-L258。其底层基于改进的深度优先搜索Sedgewick《Algorithms in C》中的方法单条路径可在 $O(VE)$ 时间内找到但图中简单路径总数可能呈指数级完全图上为 $O(n!)$。使用要点target可传入单个节点或可迭代节点集合一次性枚举到多个终点的全部路径cutoff限制路径长度边数上限cutoff2时只返回不超过 2 条边的路径返回生成器惰性求值适合路径数量巨大的场景从source到自身的单节点路径[source]也会被返回多重图中若平行边提供多条等价遍历方式同一节点序列会按平行边数量重复返回该函数不预先检查source与target之间是否连通在大图上建议先用has_path检查避免长时间空转。G nx.complete_graph(4) for path in nx.all_simple_paths(G, source0, target3): print(path) # [0, 1, 2, 3] [0, 1, 3] [0, 2, 1, 3] [0, 2, 3] [0, 3] # 只返回长度不超过 2 的路径 print(list(nx.all_simple_paths(G, source0, target3, cutoff2))) # [[0, 1, 3], [0, 2, 3], [0, 3]] # 同时指定多个目标 for path in nx.all_simple_paths(G, source0, target[2, 3]): print(path)若需要以边序列表示路径可使用同文件中的all_simple_edge_pathsnetworkx/algorithms/simple_paths.py#L262。1.5 改进的 shapefile 读取器发布说明提到 1.8 增强了 shapefileESRI 矢量格式读取能力可读取几何要素及其属性并转换为图。需注意当前主仓库的 networkx/readwrite 目录已不再包含 shapefile 模块该功能属于 1.8 时代的历史实现后续版本已将其移出核心分发因此本文不提供其源码位置与调用示例。若需在旧版 1.8 环境中使用请以对应历史版本的文档为准。1.6 更灵活的二部图加权投影二部图投影将参与者-事件二分结构压缩为单侧节点图。1.8 增强了加权投影的灵活性核心实现位于 networkx/algorithms/bipartite/projection.pyweighted_projected_graph(B, nodes, ratioFalse)networkx/algorithms/bipartite/projection.py#L123投影图的边权重默认为两端节点共享邻居的数量当ratioTrue时权重改为实际共享邻居数与最大可能共享邻居数之比从而消除另一侧节点集合规模带来的偏差。同模块还提供collaboration_weighted_projected_graph、overlap_weighted_projected_graph、generic_weighted_projected_graph、projected_graph等变体分别面向合作网络、重叠度Jaccard归一化、自定义权重函数等不同场景。from networkx.algorithms import bipartite B nx.path_graph(4) # 0-1-2-3视为二部图 G bipartite.weighted_projected_graph(B, [1, 3]) list(G.edges(dataTrue)) # [(1, 3, {weight: 1})] G bipartite.weighted_projected_graph(B, [1, 3], ratioTrue) list(G.edges(dataTrue)) # [(1, 3, {weight: 0.5})]实现细节投影函数按输入方向性构造DiGraph或Graph浅拷贝图与节点属性并会校验投影节点数不小于图中节点总数这一异常情况此时共享邻居计算将失去意义。1.7 更快的 DAG 拓扑排序、后代与祖先计算DAG有向无环图三件套在 1.8 中做了性能优化当前实现集中于 networkx/algorithms/dag.pytopological_sort(G)networkx/algorithms/dag.py#L312基于 Kahn 算法的生成器式拓扑排序descendants(G, source)networkx/algorithms/dag.py#L36返回从source出发可达的全部节点集合实现为{child for parent, child in nx.bfs_edges(G, source)}即一次 BFS 即得结果$O(VE)$ancestors(G, source)networkx/algorithms/dag.py#L73返回存在路径到达source的全部节点集合。注意descendants的结果不包含 source 自身需要时可用descendants(DG, 2) | {2}手动并入。三者均在 DAG 语义下使用但对一般有向图亦可工作topological_sort在存在环时会抛出异常。DG nx.path_graph(5, create_usingnx.DiGraph) sorted(nx.descendants(DG, 2)) # [3, 4] sorted(nx.ancestors(DG, 2)) # [0, 1] list(nx.topological_sort(DG)) # [0, 1, 2, 3, 4]1.8 力导向布局的缩放参数spring_layoutFruchterman-Reingold 算法在 1.8 中新增了scale参数用于在模拟结束后整体缩放坐标当前签名位于 networkx/drawing/layout.py#L452-L511spring_layout(G, kNone, posNone, fixedNone, iterations50, threshold1e-4, weightweight, scale1, centerNone, dim2, seedNone, ...)scale默认1控制最终布局的整体尺寸若同时传入center则以该点为中心缩放。算法内部有硬编码的最小节点间距0.01与温度0.1防止节点飞散。k节点间最优距离默认1/sqrt(n)$n$ 为节点数增大k可让节点间距更大fixed指定固定节点时布局结束阶段的重缩放会被关闭将scaleNone同样可关闭重缩放pos可提供初始位置配合seed可复现随机初始化。G nx.barbell_graph(5, 2) pos nx.spring_layout(G, k0.8, scale5, center(0, 0), seed42)二、Bug fixes1.8 修复的关键缺陷发布说明列出的修复项可归纳为以下几组涉及模块均可在当前仓库对应路径中找到实现算法正确性修复有向图的加权平均连通度计算错误含自环图的规范化拉普拉斯矩阵归一化错误相关实现见 networkx/linalg/laplacianmatrix.py 的normalized_laplacian_matrix单节点图的load betweenness负载介数计算异常见 networkx/algorithms/centrality/load.pyDFS/BFS 树中孤立节点缺失见 networkx/algorithms/traversal/depth_first_search.py 与 networkx/algorithms/traversal/breadth_first_search.pyHITS 算法改为 L1 范数归一化见 networkx/algorithms/link_analysis/hits_alg.py含自环图的密度计算处理见 networkx/classes/function.py 的density。I/O 与绘图兼容性修复与 Matplotlib 的当前 figure 状态交互更干净Pajek 文件不再写出容易引起解析问题的表头行见 networkx/readwrite/pajek.pyGEXF 文件设置合理的默认alpha透明度值见 networkx/readwrite/gexf.py支持从yEd GraphML读取曲线边见 networkx/readwrite/graphml.py。这些修复使数值算法结果与文件读写行为在边界条件下单节点图、自环、孤立点、无向图误用更加稳健。三、API changes升级到 1.8 必须注意的三处变更3.1 Laplacian 函数一律返回矩阵从 1.8 起所有 Laplacian 相关函数laplacian_matrix、normalized_laplacian_matrix、directed_laplacian_matrix等统一返回numpy.matrix而非 ndarray。若需要 numpy 数组使用L nx.laplacian_matrix(G).A # 取底层 ndarray这一约定一直延续到后续版本且在 networkx/linalg/laplacianmatrix.py 中保持文档一致。升级后若有依赖 ndarray 运算如逐元素乘法、广播的代码务必显式调用.A转换。3.2is_directed_acyclic_graph不再对无向图抛异常1.8 之前对无向图调用is_directed_acyclic_graph(G)会抛出异常现在改为直接返回False。当前实现见 networkx/algorithms/dag.py#L135官方示例G nx.Graph([(1, 2), (2, 3)]) nx.is_directed_acyclic_graph(G) # False不再抛异常 DG nx.DiGraph([(1, 2), (2, 3), (3, 1)]) nx.is_directed_acyclic_graph(DG) # False存在环 DG nx.DiGraph([(1, 2), (2, 3)]) nx.is_directed_acyclic_graph(DG) # True这一行为使该函数可以作为是否为 DAG的安全守卫无需先判断图的有向性。3.3simple_cycles返回的环不再重复末节点1.8 之前simple_cycles(G)返回的每个环在列表尾部重复包含起点节点如[0, 1, 2, 0]现在每个环只包含一次各节点如[0, 1, 2]。当前实现基于 Johnson 算法有界长度时采用 Gupta-Suzumura 算法见 networkx/algorithms/cycles.py#L106-L150G nx.DiGraph([(0, 1), (1, 2), (2, 0)]) list(nx.simple_cycles(G)) # [[0, 1, 2]]不再有重复的尾部节点升级后若存在依赖旧格式含闭合尾节点的代码例如自行拼接cycle [cycle[0]]绘制闭合回路需相应调整逻辑。四、升级建议与兼容性小结综合 1.8 的三项 API 变更升级时建议按以下清单自查变更点旧行为新行为迁移动作Laplacian 返回值ndarray部分函数一律numpy.matrix需要数组时加.Ais_directed_acyclic_graph无向图抛异常无向图返回False删除 try/except直接判 Falsesimple_cycles输出格式环含重复末节点环不含重复末节点需要闭合表示时自行cycle [cycle[0]]同时新功能Katz 中心性、有向拉普拉斯、全部简单路径、加权二部投影、spring_layout的scale参数均以向后兼容的方式加入不破坏既有调用。性能方面图性测试、拓扑排序/祖先/后代等热路径均达到线性或近线性复杂度适合在度序列校验、DAG 分析、路径枚举等批量任务中直接替换旧实现获得提速。延伸阅读版本发布记录总览doc/release/index.rst1.8 的 API 变更在后续版本中的演化可参考迁移指南doc/release/migration_guide_from_1.x_to_2.0.rst本文涉及的源码模块图性测试 networkx/algorithms/graphical.py、度序列生成器 networkx/generators/degree_seq.py、拉普拉斯矩阵 networkx/linalg/laplacianmatrix.py、Katz 中心性 networkx/algorithms/centrality/katz.py、简单路径 networkx/algorithms/simple_paths.py、二部投影 networkx/algorithms/bipartite/projection.py、DAG 算法 networkx/algorithms/dag.py、力导向布局 networkx/drawing/layout.py、环枚举 networkx/algorithms/cycles.py。【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkx创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
