| sidebar_position | 8 |
|---|
算子类别：Flow & Cut（网络流、割结构与边界分析）
算法数量：7 个
适用阶段：网络容量分析、瓶颈识别、资源调度、最小割评估、全局韧性分析、社区边界刻画、节点/边扩张能力评估
产品定位：为“最大能流多少 / 哪些地方会成为瓶颈 / 切断网络最小代价是多少 / 任意两点之间的最小割结构是什么 / 一个节点集合与外部连接得有多紧 / 社区边界是否清晰”提供统一的流与割能力底座。
Flow & Cut 算子集主要围绕四类核心问题：
-
最大流（Max Flow）
- 从源点到汇点，最多能通过多少流量？
- 哪些边或节点会首先成为瓶颈？
- 典型算法：
edmonds_karp,shortest_augmenting_path,preflow_push
-
容量分级与费用流
- 在容量、供需和成本约束下，如何进行最优流量分配？
- 如何在多源多汇网络中实现成本最优调度？
- 典型算法：
capacity_scaling
-
全局最小割结构
- 任意两点之间的最小割是多少？
- 是否能用一棵树压缩表示所有两两最小割？
- 典型算法：
gomory_hu_tree
-
边界与扩张能力分析
- 一个节点集合与外部连接得有多紧？
- 社区、团伙或子图的边界是否清晰？
- 节点集合向外扩张的连接强度如何？
- 典型算法：
edge_expansion,node_boundary
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 经典最大流 | edmonds_karp |
基于 BFS 增广路径的最大流算法，解释性强，适合中小规模网络 |
| 最短增广路最大流 | shortest_augmenting_path |
使用距离标号和最短增广路径提升最大流求解效率 |
| 预流推进最大流 | preflow_push |
通过 Push / Relabel 操作求解最大流，适合复杂高连接网络 |
| 容量分级费用流 | capacity_scaling |
处理带容量、供需和成本约束的最小费用流问题 |
| 全对最小割结构 | gomory_hu_tree |
用一棵割树压缩表示无向图中任意两点的最小割值 |
| 边扩张度 | edge_expansion |
衡量节点集合与外部之间的边界连接强度 |
| 节点边界 | node_boundary |
返回节点集合外部与其相邻的边界节点集合 |
-
G：NetworkX 图对象
- 最大流算法通常面向有向图，也可根据实现支持无向图转换
gomory_hu_tree通常面向无向图edge_expansion/node_boundary可用于无向图或有向图的集合边界分析
-
capacity：边容量属性名，常见默认值为
"capacity" -
s / t：源点与汇点，用于最大流、最小割或源汇网络分析
-
demand：节点需求属性，用于最小费用流类问题
- 供给节点通常为负需求
- 消费节点通常为正需求
-
weight：边单位流量成本或边权属性，用于费用流、扩张度或边界相关计算
-
nbunch / S：节点集合，用于边界和扩张分析
- 最大流算法：残量网络（Residual Network），可进一步读取流值、流量分配和饱和边
- 容量/费用算法：最优流方案与总成本相关结果
- Gomory-Hu Tree：一棵无向树，树中边权编码原图中两两最小割值
- 边扩张度：数值型指标
- 节点边界：边界节点集合
功能说明
基于 Ford-Fulkerson 方法，每次使用 BFS 寻找从源点 s 到汇点 t 的最短增广路径，并沿该路径增加流量，直到不存在可增广路径为止。
产品价值
- 最大流算法中解释性较强的一类
- 适合中小规模网络、教学分析和调试场景
- 可输出残量网络，便于分析瓶颈边、剩余容量和流量分布
典型场景
- 物流网络：从仓库到目的地最多能运输多少货物
- 通信网络：从源节点到目标节点最大带宽是多少
- 管网系统：从供给端到消费端最大输送能力
- 任务调度：资源从供给侧到需求侧的最大匹配能力
关键参数
s：源点t：汇点capacity：边容量属性cutoff：达到指定流量后提前停止
适用与特性
- 图类型：有向图为主
- 输出：残量网络
- 复杂度：
O(V · E²) - 优点：过程清晰、便于解释
- 注意：大规模高密度网络中可能较慢
功能说明
使用距离标号机制寻找较短的增广路径，通过更有效的增广策略计算最大流。
产品价值
- 相比 Edmonds-Karp，通常在中大规模网络中表现更好
- 适合需要更高性能的最大流计算
- 可用于容量规划、路由分析和网络承载能力评估
典型场景
- 电信网络最大吞吐分析
- 城市交通骨干网络容量计算
- 多链路物流网络承载能力评估
- 服务调用网络中的最大请求通量估计
关键参数
s：源点t：汇点capacity：边容量属性two_phase：对部分单位容量网络可提升性能cutoff：提前终止阈值
适用与特性
- 图类型：有向图为主
- 输出：残量网络
- 复杂度：常见上界约
O(V² · E) - 特点：通常比 Edmonds-Karp 更适合较大网络
功能说明
预流推进算法不要求中间节点在计算过程中始终满足流量守恒，而是允许节点暂时存有“超额流量”，再通过 Push 和 Relabel 操作逐步将流推进到汇点或回退，最终得到最大流。
产品价值
- 适合复杂、高连接、高密度网络
- 工程实践中常具有较好的性能表现
- 可只计算最大流值，减少不必要的流方案输出成本
典型场景
- 数据中心网络最大流分析
- 芯片布线与复杂连接网络
- 高并发通信网络容量评估
- 大规模基础设施网络瓶颈分析
关键参数
s：源点t：汇点capacity：边容量属性global_relabel_freq：全局重标记频率，重要性能调优参数value_only：是否只关心最大流值
适用与特性
- 图类型：有向图为主
- 输出：残量网络或最大流相关结果
- 复杂度：常见上界约
O(V² · E) - 特点：实践中常优于路径型增广算法
功能说明
基于容量缩放思想处理带容量、供需和费用约束的流问题。算法按容量等级逐步调整可用流量，寻找满足节点需求并使总费用最优的流方案。
产品价值
- 支持“供需平衡 + 成本最优”的资源调度
- 适合多源多汇网络中的最小费用流建模
- 能同时考虑容量限制和单位运输成本
典型场景
- 物流调度：多个仓库向多个门店供货，并最小化运输成本
- 云资源分配：多资源池向多业务单元分配容量
- 能源网络：发电侧到用电侧的成本最优输送
- 供应链网络：在供需约束下优化调拨方案
关键参数
demand：节点需求属性，供给为负、需求为正capacity：边容量属性weight：单位流量成本heap：优先队列实现相关参数，影响性能
适用与特性
- 图类型：有向图为主
- 输出：最小费用流方案
- 适合：带容量、供需、费用约束的调度问题
- 注意：节点总供给与总需求通常需要平衡，否则可能无可行解
功能说明
用一棵树表示无向图中任意两点之间的最小割值。树上任意两点路径中的最小边权，就等于原图中这两点之间的最小割值。
产品价值
- 将全对最小割结构压缩成一棵树
- 支持快速查询任意两点的最小割值
- 适合全局网络韧性分析和最薄弱连接识别
典型场景
- 通信网络：快速查询任意两点之间的最小切断容量
- 交通网络：识别城市路网中最脆弱的区域连接
- 供应链网络：评估不同企业或区域之间的断供风险
- 基础设施网络：做全局韧性画像和脆弱连接定位
关键参数
capacity：边容量属性flow_func：底层最大流算法，如edmonds_karp、shortest_augmenting_path、preflow_push
适用与特性
- 图类型：无向图
- 输出：Gomory-Hu Tree
- 复杂度：通常需要执行
n - 1次最大流计算 - 注意：适合需要多次查询两点最小割的场景；只查询单对节点时不一定划算
功能说明
衡量一个节点集合与集合外部之间的边界连接强度。通常可以理解为：从集合内部连到集合外部的边数量或边权，相对于集合规模的扩张程度。
产品价值
- 判断一个社区或子图是否边界清晰
- 衡量节点集合向外扩散或外部暴露的程度
- 可用于社区质量、割结构和网络扩张能力分析
典型场景
- 社区分析：判断一个社区是否与外部连接过多
- 风控团伙识别：评估团伙是否相对封闭
- 网络安全：识别暴露面较大的子网
- 传播分析：衡量某群体向外传播的潜力
- 图划分评估：比较不同分区的边界紧密程度
关键参数
S：待分析的节点集合T：可选的外部目标集合weight：边权属性，可用于加权边扩张edge_boundary：可指定边界边计算方式
适用与特性
- 图类型：无向图 / 有向图
- 输出：数值型扩张度
- 注意：边扩张度高通常表示该集合与外部连接强；边扩张度低通常表示集合边界更清晰、更封闭
功能说明
返回节点集合外部与该集合相邻的节点集合。也就是说，给定内部节点集合 S，找到所有不在 S 中但与 S 有边相连的外部边界节点。
产品价值
- 快速识别一个子图、社区或团伙的外部接触点
- 支持风险外溢、传播入口、攻击面和跨圈层连接分析
- 可作为图扩张、社区边界和割分析的基础能力
典型场景
- 风控网络：找出团伙外围接触账户
- 社交网络：找出一个社区连接到外部的用户
- 供应链网络：识别某供应商群体的外部客户或上游
- 安全网络：找出子网的外部暴露节点
- 舆情传播：识别信息从某圈层向外扩散的接触点
关键参数
nbunch1：内部节点集合nbunch2：可选的候选外部节点集合- 图方向：在有向图中需要结合边方向解释边界含义
适用与特性
- 图类型：无向图 / 有向图
- 输出：节点集合
- 特点：结果直观，适合边界解释和下游筛选
- 想算 s → t 最大流，中小图且重视解释性：使用
edmonds_karp - 想更快计算最大流，网络规模较大：使用
shortest_augmenting_path - 极复杂、高密度、高连接网络最大流：使用
preflow_push - 存在供需平衡和单位成本约束：使用
capacity_scaling - 想一次性支持任意两点最小割查询：使用
gomory_hu_tree - 想评估一个社区或节点集合与外部连接强弱：使用
edge_expansion - 想找一个节点集合的外部接触点 / 边界节点：使用
node_boundary
- “这条网络从 A 到 B 的最大承载能力是多少？”
- “哪些链路在最大流下成为瓶颈？”
- “在当前供需和容量限制下，最低成本的调度方案是什么？”
- “任意两个节点之间，最少切掉多少容量才能隔离？”
- “整个网络中，最脆弱的连接对是哪一组？”
- “这个社区与外部连接是否紧密？”
- “某个团伙的外部接触节点有哪些？”
- “这个子网的边界节点是谁？”
- “哪个节点集合的边扩张度最低，说明它最像一个封闭社区？”
-
容量字段必须明确
- 最大流和割树类算法通常依赖
capacity字段。 - 如果边没有容量属性，算法可能使用默认容量或报错，需在产品层明确规则。
- 最大流和割树类算法通常依赖
-
最大流结果要结合残量网络解释
- 最大流值回答“最多能流多少”。
- 残量网络可以进一步分析哪些边饱和、哪些路径还有剩余容量。
-
不同最大流算法适合不同规模
edmonds_karp解释性强，适合中小图。shortest_augmenting_path更适合较大图。preflow_push在高连接复杂网络中通常更有优势。
-
费用流需要满足供需约束
capacity_scaling通常要求总供给与总需求平衡。- 若供需不平衡，需要增加虚拟源/汇或进行需求修正。
-
Gomory-Hu Tree 适合多次查询
- 构造割树成本较高，因为需要多次最大流计算。
- 如果只查询一对节点，直接做单次最小割或最大流可能更合适。
- 如果需要大量两两最小割查询，割树非常有价值。
-
边界类指标和最大流不是同一类问题
edge_expansion衡量集合与外部的连接强度。node_boundary返回集合外部的邻接节点。- 它们不直接计算最大流，但非常适合社区边界、扩散边界和风险外溢分析。
-
有向图边界要注意方向
- 在有向图中，边界可能区分“从集合流出”与“从外部流入”。
- 产品展示时应明确边界是按出边、入边，还是忽略方向计算。
-
容量与成本语义不要混用
capacity表示最多能通过多少流量。weight在费用流中通常表示单位流量成本。- 同一条边上的容量和成本是两个不同业务含义。
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | edmonds_karp |
Edmonds-Karp 最大流算法 |
| 2 | shortest_augmenting_path |
最短增广路最大流算法 |
| 3 | preflow_push |
预流推进最大流算法 |
| 4 | capacity_scaling |
容量分级最小费用流算法 |
| 5 | gomory_hu_tree |
Gomory-Hu 全对最小割树 |
| 6 | edge_expansion |
边扩张度 |
| 7 | node_boundary |
节点边界 |