NetworkX 1.7 核心算法解析k-clique 社区发现、多图操作符与近似算法实战【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkxNetworkX 1.7 是 2012 年 7 月发布的一个里程碑式版本为这个 Python 图分析库引入了 k-clique 社区发现、flow hierarchy 度量、面向图列表的多图操作符、二部图双邻接矩阵生成以及一整组基于近似算法的 NP 难问题求解器。本篇技术指南以该版本的官方发布说明doc/release/api_1.7.rst为骨架结合当前仓库中这些功能的源码实现networkx/algorithms/、networkx/algorithms/approximation/、networkx/algorithms/operators/等模块逐一讲解每个新功能的数学定义、调用方式、参数含义与底层原理帮助读者在今天的 NetworkX 中直接使用这些历久弥新的能力。1.7 版本发布的三大亮点NetworkX 1.7 的发布说明Release date: 4 July 2012将本次更新的内容归纳为三类新函数k-clique 社区发现k-clique community finding、flow hierarchy 度量以及能够对图列表lists of graphs进行操作的 union、disjoint union、compose、intersection 四种运算符还新增了生成二部图 biadjacency matrix双邻接矩阵的函数新的近似算法覆盖 dominating set支配集、edge dominating set边支配集、independent set独立集、max clique最大团、min-weighted vertex cover最小权顶点覆盖五个经典 NP 难问题大量 bug 修复与改进并移除了未经测试的bipartite_random_regular_graph()。这些功能今天依然完整保留在仓库中并且经过了 dispatch 机制nx._dispatchable装饰器与测试套件的持续打磨是理解 NetworkX 算法模块组织方式的绝佳入口。k-clique 社区发现重叠社区的渗滤方法发布说明中第一个新函数是 k-clique 社区发现实现位于 networkx/algorithms/community/kclique.py。算法思想该方法源自 Palla 等人 2005 年发表于 Nature 的经典论文Gergely Palla, Imre Derényi, Illés Farkas, Tamás Vicsek,Uncovering the overlapping community structure of complex networks in nature and society, Nature 435, 814-818, 2005其核心定义是一个k-clique 社区是所有可以通过相邻 k-clique互相到达的、大小为 k 的团的并集两个 k-clique 相邻当且仅当它们共享 k-1 个节点。这种定义天然支持重叠社区——一个节点可以同时属于多个社区这对刻画社交网络、生物网络中节点同时参与多个功能模块的现象尤为重要。函数签名与参数nx.community.k_clique_communities(G, k, cliquesNone)参数类型含义GNetworkX 图输入图无向图kint最小团的大小必须大于 1否则抛出nx.NetworkXErrorcliqueslist 或 generator预计算的团列表可用nx.find_cliques(G)生成为None时内部自动调用nx.find_cliques函数返回一个生成器逐个产出代表每个 k-clique 社区的节点集合set。源码实现的三步流程从 kclique.py 的源码看算法分为清晰的三个阶段筛团用nx.find_cliques(G)找出所有极大团过滤掉大小小于 k 的团并转成frozenset便于集合运算构建渗滤图percolation graph先把每个团作为节点加入一个新图再通过_get_adjacent_cliques找出共享节点的相邻团当两个团交集大小 k-1时连边连通分量归并对该渗滤图求nx.connected_components每个连通分量内所有团做frozenset.union即为一个 k-clique 社区。实战示例源码 docstring 中给出了一个直观例子——两个通过共享节点粘连的 K5完全图 K5 有 5 个节点import networkx as nx G nx.complete_graph(5) K5 nx.convert_node_labels_to_integers(G, first_label2) G.add_edges_from(K5.edges()) c list(nx.community.k_clique_communities(G, 4)) sorted(list(c[0])) # [0, 1, 2, 3, 4, 5, 6]两个 K5 通过共享 3 个节点2,3,4渗透成一个大社区 list(nx.community.k_clique_communities(G, 6)) # []不存在大小为 6 的团当 k4 时两个 K5 共享 3 个节点满足k-13的相邻条件因此渗透为一个包含 7 个节点的社区当 k6 时图中根本不存在 6-clique返回空列表。对应的单元测试见 networkx/algorithms/community/tests/test_kclique.py。flow hierarchy度量有向网络的流程层级flow hierarchy流程层级由 Luo 与 Magee 在 2011 年提出Detecting evolving patterns of self-organizing networks by flow hierarchy measurement, Complexity 16(6):53-61用于量化有向网络中层级化的程度。定义与函数签名nx.flow_hierarchy(G, weightNone)定义flow hierarchy 是不参与任何环cycle的边所占的比例。取值在 0 到 1 之间——完全无环的有向无环图DAG为 1所有边都处于环中的图为 0参数G必须是有向图DiGraph或MultiDiGraphweight为可选的边权重属性为None时每条边权重视为 1异常输入空图无任何边或非有向图时抛出nx.NetworkXError。基于强连通分量的高效实现原始论文通过邻接矩阵幂运算计算 flow hierarchy而 networkx/algorithms/hierarchy.py 中的实现采用了一个更精巧的等价转换一条边处于环中当且仅当它位于某个强连通分量SCC内部。因此只需用 Tarjan 算法nx.strongly_connected_components在 O(m) 时间内找出所有 SCC然后计算scc nx.strongly_connected_components(G) return 1 - sum(G.subgraph(c).size(weight) for c in scc) / G.size(weight)即1 - 所有 SCC 内部边权重之和 / 全图边权重之和。分子求和中的G.subgraph(c).size(weight)返回各分量内部带权边数。该实现把论文中的矩阵幂方法从 O(n³) 级别降到了线性级别是对算法本身的一次实质优化。对应测试见 networkx/algorithms/tests/test_hierarchy.py。多图操作符对图列表的 union / disjoint union / compose / intersection1.7 之前 NetworkX 只有两两图之间的union、compose、intersection等操作1.7 引入了接受**图列表iterable of graphs**的批量版本全部位于 networkx/algorithms/operators/all.py。union_allnx.union_all(graphs, rename())要求所有图节点集两两不相交否则抛出nx.NetworkXErrorrename参数可为每个图指定节点前缀如rename(G-, H-)也支持无限生成器如itertools.count源码内部通过chain(rename, repeat(None))自动补None来对齐图的数量返回与列表中第一个图同类型的新图混合有向/无向、Graph/MultiGraph 会抛出异常图、节点、边的属性都会传播到结果图中图属性冲突时取列表中最后一个含该属性的图的值。disjoint_union_allnx.disjoint_union_all(graphs)无需手动指定rename内部用nx.convert_node_labels_to_integers将节点重标号为从 0 开始的连续整数第一个图节点为 0..n₁-1第二个图从 n₁ 开始再调用union_all完成合并 G1 nx.Graph([(1, 2), (2, 3)]) G2 nx.Graph([(4, 5), (5, 6)]) U nx.disjoint_union_all([G1, G2]) list(U.nodes()) # [0, 1, 2, 3, 4, 5] list(U.edges()) # [(0, 1), (1, 2), (3, 4), (4, 5)]compose_all 与 intersection_allcompose_all(graphs)节点与边集的简单并集不要求节点集不相交共享节点上的边会合并且边属性冲突时后者覆盖前者intersection_all(graphs)只保留所有图中都出现的节点和边。源码逐图用对节点集、边集做交集无向图会把(u,v)与(v,u)都计入边集以正确处理且不复制任何属性到结果图需要属性时需自行set_node_attributes等设置docstring 中给出了用min聚合各图节点容量的完整示例。四个函数对空列表都会抛出ValueError(cannot apply ... to an empty list)。测试覆盖见 networkx/algorithms/operators/tests/test_all.py。二部图 biadjacency matrix双邻接矩阵生成对二部图 G(U, V, E)biadjacency matrix 是 r×s 的矩阵 B其中B[i][j] 1当且仅当(u_i, v_j) ∈ E。1.7 新增了生成该矩阵的函数实现在 networkx/algorithms/bipartite/matrix.pynx.bipartite.biadjacency_matrix(G, row_order, column_orderNone, dtypeNone, weightweight, formatcsr)参数默认值含义row_order必填节点列表决定矩阵行顺序为空或含重复节点时抛nx.NetworkXErrorcolumn_orderNone列顺序为None时取set(G) - set(row_order)顺序任意dtypeNoneNumPy 数据类型None用 NumPy 默认值weightweight边属性键用作矩阵值None时每条边取 1formatcsrSciPy 稀疏矩阵格式可选{dense,bsr,csr,csc,coo,lil,dia,dok}非法格式抛nx.NetworkXError实现要点内部用scipy.sparse.coo_array组装(row_index, col_index, value)三元组再按format转换适合大规模稀疏二部图不检查输入图是否为真正的二部图由调用者保证对有向二部图只把successors出边邻居计入矩阵若需要同时计入前驱与后继注释建议生成两个矩阵后做B Bᵀ反向函数from_biadjacency_matrix位于同一文件可将稀疏矩阵还原为图。近似算法族五个 NP 难问题的多项式近似解1.7 发布说明明确列出的新近似算法模块全部位于 networkx/algorithms/approximation/调用时统一通过nx.approximation命名空间访问。这些问题的精确求解都是 NP 难的NetworkX 提供的是有理论保证的近似算法近似比均为常数或对数级别。最小权顶点覆盖min_weighted_vertex_cover实现在 vertex_cover.py采用local-ratio 算法Bar-Yehuda Even, 1985nx.approximation.min_weighted_vertex_cover(G, weightNone)weight指定节点权重属性缺失的节点默认权重 1返回集合的权重和≤ 2 × 最优顶点覆盖权重2-近似比对有向图同样适用忽略边的方向只看端点最坏情况运行时间 O(m log n)n 为节点数m 为边数。源码核心是一个贪心循环每次取一条尚未覆盖的边把成本较小的端点加入覆盖集并同步扣减另一端点的成本。支配集min_weighted_dominating_set 与 min_edge_dominating_set实现在 dominating_set.pymin_weighted_dominating_set(G, weightNone)节点支配集每个不在集合中的节点都至少与集合中某节点相邻。采用成本效益贪心每次选每单位权重覆盖最多未覆盖节点的节点近似比为(log w(V)) · w(V*)运行时间 O(m)。仅支持无向图输入有向图抛nx.NetworkXNotImplemented源码注释中留有 TODO询问为何算法不适用于有向图min_edge_dominating_set(G)边支配集每条不在集合中的边都与集合中某条边共享端点。实现直接返回maximal_matching(G)极大匹配规模 ≤ 2 × OPT运行时间 O(|E|)。空图抛ValueError。独立集与最大团maximum_independent_set 与 max_clique实现在 clique.pymaximum_independent_set(G)返回近似最大独立集两两不相邻的节点集基于 Boppana–Halldórsson 的 clique_removal 方法最坏情况近似度为 O(|V|/(log|V|)²)max_clique(G)最大团与独立集互为对偶——图的团对应补图中的独立集因此源码先求nx.complement(G)再复用clique_removal两者都标注not_implemented_for(directed)与not_implemented_for(multigraph)仅支持简单无向图。最小极大匹配min_maximal_matching实现在 matching.py返回所有极大匹配中规模最小的一个直接返回nx.maximal_matching(G)规模 ≤ 2 × OPT运行时间 O(|E|)。注意它求解的是最小极大匹配与普通最小/最大匹配概念不同近似比 2 只对极大匹配族成立。其他变更与移除项发布说明的 Other 一节指出移除了未经测试的bipartite_random_regular_graph()。这意味着 1.7 起不再提供该随机正则二部图生成器需要此类图的用户应改用其他受支持的生成方式如nx.random_regular_graph结合二部图校验或自行构造且发布说明提醒该函数此前未经过测试移除属于清理行为。此外发布说明引用的完整 ticket 列表功能新增与 bug 修复明细位于当时的 Trac 跟踪系统现已迁移本文所覆盖的功能在当前仓库中均有对应源码与测试可查证。小结如何在今天的 NetworkX 中使用 1.7 功能尽管已是十多年前的版本1.7 引入的这些 API 至今仍是 NetworkX 的常青组件且调用方式与发布说明一致仅命名空间上社区函数需通过nx.community.k_clique_communities访问功能类别入口源码位置k-clique 社区nx.community.k_clique_communities(G, k)networkx/algorithms/community/kclique.py流程层级nx.flow_hierarchy(G, weightNone)networkx/algorithms/hierarchy.py多图 unionnx.union_all(graphs, rename())networkx/algorithms/operators/all.py多图不相交并nx.disjoint_union_all(graphs)同上多图合成/交集nx.compose_all(graphs)/nx.intersection_all(graphs)同上二部图双邻接矩阵nx.bipartite.biadjacency_matrix(G, row_order, ...)networkx/algorithms/bipartite/matrix.py近似顶点覆盖nx.approximation.min_weighted_vertex_cover(G, weightNone)networkx/algorithms/approximation/vertex_cover.py近似支配集nx.approximation.min_weighted_dominating_set(G)/min_edge_dominating_set(G)networkx/algorithms/approximation/dominating_set.py近似独立集/最大团nx.approximation.maximum_independent_set(G)/max_clique(G)networkx/algorithms/approximation/clique.py最小极大匹配nx.approximation.min_maximal_matching(G)networkx/algorithms/approximation/matching.py在使用近似算法时请牢记它们返回的是带理论近似比保证的解而非最优解——对于需要精确结果的小规模问题应配合精确算法如nx.find_cliques用于精确极大团枚举交叉验证。这些函数经过 dispatch 机制nx._dispatchable接入 NetworkX 的调度框架在有后端实现时可由其他图计算后端接管是学习 NetworkX 算法模块组织与 API 设计的上佳范本。【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkx创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考