| sidebar_position | 4 |
|---|
算子类别：Connectivity & Components（连通性、连通分量与割/切割分析）
算法数量：17 个
适用阶段：网络结构体检、孤岛/分区识别、稳健性评估、关键节点/关键边定位、故障/攻击面分析、强弱连通分析、桥接结构识别、SCC 压缩建模
产品定位：为“网络是否连通 / 分成几块 / 哪些节点或边一断就分裂 / 最少切多少才能断开 / 有向图如何压缩成组件级 DAG / 哪些边是局部桥梁”提供统一能力底座。
Connectivity & Components 算子集面向无向图与有向图的连通性分析，覆盖以下核心问题：
-
连通性与连通分量
- 无向图是否整体连通？
- 图分成多少个连通块？
- 每个连通块包含哪些节点？
- 典型算法：
is_connected,connected_components,number_connected_components
-
有向图强弱连通分析
- 有向图是否强连通？
- 忽略方向后是否弱连通？
- 哪些节点构成强连通分量或弱连通分量？
- 典型算法：
is_strongly_connected,strongly_connected_components,is_weakly_connected,weakly_connected_components
-
网络稳健性指标
- 最少移除多少节点会让网络断开？
- 最少移除多少边会让网络断开？
- 两个指定节点之间的最小割是多少？
- 典型算法：
node_connectivity,edge_connectivity
-
最小割与关键结构
- 哪些节点一起移除会让网络断开？
- 哪些边一起移除会让网络断开？
- 哪些节点是割点？
- 哪些边是桥？
- 典型算法：
minimum_node_cut,minimum_edge_cut,articulation_points,bridges
-
桥接结构与双连通分解
- 哪些区域内部更稳健？
- 哪些边连接了原本独立的结构块？
- 删除哪些边会造成组件分裂？
- 典型算法：
bridge_components,biconnected_component_edges,local_bridges
-
有向组件压缩
- 如何把强连通分量压缩成组件级 DAG？
- 如何从复杂有向图中提取高层级依赖结构？
- 典型算法：
condensation
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 无向图整体连通性 | is_connected |
判断无向图是否为单一连通块 |
| 无向图连通分量 | connected_components |
输出每个连通分量的节点集合 |
| 无向图分量数量 | number_connected_components |
返回连通分量数量 |
| 有向图强连通性 | is_strongly_connected |
判断有向图中是否任意两点双向可达 |
| 有向图强连通分量 | strongly_connected_components |
输出 SCC（强连通分量）划分 |
| 有向图弱连通性 | is_weakly_connected |
忽略方向后判断有向图是否连通 |
| 有向图弱连通分量 | weakly_connected_components |
输出 WCC（弱连通分量）划分 |
| 稳健性指标（节点） | node_connectivity |
最少移除多少节点可使图断开，或使指定 s-t 断开 |
| 稳健性指标（边） | edge_connectivity |
最少移除多少边可使图断开，或使指定 s-t 断开 |
| 最小节点割集合 | minimum_node_cut |
给出使图断开或使 s-t 不连通的最小节点集合 |
| 最小边割集合 | minimum_edge_cut |
给出使图断开或使 s-t 不连通的最小边集合 |
| 关键节点（割点） | articulation_points |
删除后会增加无向图连通分量数量的节点 |
| 桥连通块分解 | bridge_components |
基于桥边分解出的 2-edge-connected components |
| 双连通分量边集合 | biconnected_component_edges |
输出无向图中双连通分量对应的边集合 |
| 强连通分量压缩 | condensation |
将有向图的 SCC 压缩为 DAG |
| 桥边识别 | bridges |
找出无向图中删除后会增加连通分量数量的边 |
| 局部桥识别 | local_bridges |
找出端点之间没有共同邻居的局部桥边，并可计算跨度 |
-
输入
G：NetworkX Graph / DiGraph- 无向连通性算法通常使用
Graph - 强连通、弱连通、SCC 压缩通常使用
DiGraph - 部分割与连通度算法同时支持有向图和无向图
- 无向连通性算法通常使用
-
常见输出
- 判定类：
bool - 分量类：
generator[set(node)] - 连通性指标：
int - 最小割：
set(node)或set(edge) - 割点：节点迭代器
- 桥边：边迭代器
- 双连通分量：
generator[list[edge]] - SCC 压缩图：
DiGraph
- 判定类：
说明：
- “强连通 / 弱连通”只对有向图有意义。
- “割点 / 桥 / 双连通分量 / 桥连通块”通常用于无向图的结构稳健性分析。
- “最小割 / 节点连通度 / 边连通度”可用于全局网络，也可用于指定节点对
s, t的局部稳健性分析。
功能说明
判断无向图中是否任意两个节点之间都存在路径可达。
产品价值
- 网络健康度的第一道体检
- 快速判断是否存在孤岛、断裂区域或未接入节点
- 适合作为后续全局算法的前置校验
典型场景
- 道路网络是否存在完全孤立区域
- 设备互联拓扑是否为一张完整网络
- 社交网络是否存在完全隔离圈子
- 供应链网络是否存在断裂子网
适用与特性
- 图类型：无向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
输出无向图中每个连通分量的节点集合。一个连通分量代表一个内部互相可达、但与其他分量不连通的子网络。
产品价值
- 识别网络被切成了哪些区域、社群或子系统
- 为后续分区统计、分区建模、分区调度提供边界
- 帮助定位孤立组件和异常断裂结构
典型场景
- 物流站点网络：分出互不连通的运营区域
- 设备互联网络：找出孤立子网
- 社交网络：识别互不接触的圈子
- 企业关系网络：识别互不关联的集团簇
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
返回无向图中的连通分量个数。
产品价值
- 快速量化网络碎片化程度
- 可作为网络健康 KPI
- 便于监控故障前后网络被分裂成多少块
典型场景
- 城市路网断裂后的分区数量评估
- 设备网络故障后的子网数量统计
- 协作网络中孤立团队数量统计
- 风控网络中独立团伙数量估算
适用与特性
- 图类型：无向图
- 输出：
int - 复杂度：
O(V + E)
功能说明
判断有向图是否满足任意两个节点之间都双向可达，即 u → v 且 v → u 都存在路径。
产品价值
- 判断有向网络是否形成完整闭环结构
- 适合分析互相调用、互相跳转、资金可回流等系统
- 可用于识别是否存在方向性阻断
典型场景
- 服务调用：是否任意服务都能经调用链互相到达
- 页面导航：是否任意页面都能到达并返回
- 交易网络：是否形成可回流的闭环网络
- 状态机分析：是否所有状态互相可达
适用与特性
- 图类型：有向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
输出有向图的强连通分量划分。每个 SCC 内任意两个节点都双向可达。
产品价值
- 识别循环模块、闭环群组、互相依赖结构
- 常用于依赖分析、死循环排查、模块化拆解
- 是有向图压缩和层级建模的重要基础
典型场景
- 服务依赖图：找出互相依赖成环的模块
- 流程图：找出可以回到起点的循环步骤群
- 交易网络：识别资金循环小团体
- 代码依赖：定位循环 import 或循环引用模块
适用与特性
- 图类型：有向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
将有向图视为无向图，忽略边方向后判断图是否连通。
产品价值
- 判断有向网络在结构上是否仍是一张网
- 即使方向上不互达，也能判断整体是否割裂
- 适合做有向网络的宏观连通体检
典型场景
- 邮件发送网络：忽略方向看组织是否连成整体
- 关注网络：忽略方向看用户是否割裂成多个群落
- 页面链接：忽略方向看站点是否被分割成孤岛
- 服务调用：判断业务域结构上是否互有关联
适用与特性
- 图类型：有向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
在忽略方向后，将有向图划分为若干互相连通的分量。
产品价值
- 识别方向网络的结构分区
- 为分区内进一步做 SCC、中心性、社区发现等分析提供边界
- 可用于识别孤立业务域或独立传播域
典型场景
- 关注网络：识别互不相连的社群域
- 邮件网络：识别组织内互不沟通的群体
- 服务调用：识别互不关联的业务系统
- 交易网络：识别没有交易连接的账户群
适用与特性
- 图类型：有向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
返回最少需要删除多少个节点才能让图断开；如果指定 s, t，则返回最少删除多少节点能让 s 与 t 不连通。
产品价值
- 量化网络抗节点故障或攻击的能力
- 评估关键设备、关键岗位、关键账户的冗余程度
- 可用于稳健性评分和加固预算评估
典型场景
- 数据中心：最少坏几台设备会断网
- 城市路网：最少封几个路口会割裂交通
- 协作网络：最少离开几个人团队会分裂
- 供应链网络：最少失效几个企业会造成断供
关键参数
s, t：指定源节点和目标节点，做局部连通度分析flow_func：最大流实现选择，影响性能
适用与特性
- 图类型：有向图 / 无向图
- 输出：
int - 复杂度：与最大流算法相关
功能说明
返回最少需要删除多少条边才能让图断开；如果指定 s, t，则返回最少删除多少条边能让 s 与 t 不连通。
产品价值
- 量化网络抗链路故障或边攻击的能力
- 用于链路冗余规划、网络加固和容灾设计
- 能判断系统是否存在低冗余连接瓶颈
典型场景
- 机房网络：最少断几条链路会割裂网络
- 道路网络：最少封几条路会导致分区
- 物流网络：最少中断几条线路会断供
- 通信网络：链路冗余能力评估
关键参数
s, t：指定源节点和目标节点flow_func：最大流实现选择cutoff：阈值提前停止，适合只判断是否低于某个冗余等级
适用与特性
- 图类型：有向图 / 无向图
- 输出：
int - 复杂度：与最大流算法相关
功能说明
输出一个最小节点集合，删除这些节点后图会断开；如果指定 s, t，则删除这些节点后 s 与 t 不再连通。
产品价值
- 直接给出最脆弱节点集合
- 支持故障演练、攻击面评估和加固优先级制定
- 比单纯连通度指标更具可执行性
典型场景
- 数据中心：最少哪几台设备一起故障会断网
- 交通网络：最少封哪几个路口会割裂城市路网
- 电网网络：最少哪几个站点失效会分区
- 组织网络：哪些关键人员离开会造成协作断裂
关键参数
s, t：指定源节点和目标节点，做局部割分析flow_func：最大流实现选择
适用与特性
- 图类型：有向图 / 无向图
- 输出：
set(node) - 复杂度：与最大流算法相关
功能说明
输出一个最小边集合，删除这些边后图会断开；如果指定 s, t，则删除这些边后 s 与 t 不再连通。
产品价值
- 直接定位最脆弱链路集合
- 支持备份线路规划、链路加固和故障演练
- 可用于评估跨区域、跨系统连接的脆弱性
典型场景
- 机房网络：最少切断哪几条链路会割裂网络
- 城市路网：最少封哪几条路会形成分区
- 物流网络：最少中断哪几条线路会断供
- 供应链网络：关键运输关系识别
关键参数
s, t：指定源节点和目标节点flow_func：最大流实现选择
适用与特性
- 图类型：有向图 / 无向图
- 输出：
set(edge) - 复杂度：与最大流算法相关
功能说明
在无向图中，如果删除某个节点会导致连通分量数量增加，则该节点是割点。
产品价值
- 识别典型单点故障节点
- 与节点连通度和最小节点割互补
- 适合快速定位结构上最明显的薄弱点
典型场景
- 城市路网：封闭哪些路口会导致交通割裂
- 数据中心：哪些设备故障会导致网络分裂
- 社交网络：哪些用户离开会把社群拆开
- 供应链网络：哪些企业失效会造成上下游断裂
适用与特性
- 图类型：无向图
- 输出：节点迭代器
- 复杂度：
O(V + E)
功能说明
找出无向图中所有 2-边连通分量。一个桥连通块内部通常不会因为单条边失效而被切开，块与块之间由桥边连接。
产品价值
- 将网络拆成内部边冗余更强的结构块
- 适合做网络分区、韧性模块识别和加固分层
- 可以辅助定位网络的骨架结构与脆弱连接
典型场景
- 路网：内部替代路线更丰富的区域块
- 数据中心：内部链路冗余更高的设备群
- 协作网络：内部联系更稳固的合作小组
- 通信网络：抗单链路故障的子网识别
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
输出无向图中双连通分量对应的边集合。双连通分量内部通常没有单个割点可以将该分量拆开。
产品价值
- 识别内部节点冗余更强的结构块
- 辅助分析哪些区域不容易因单点节点故障而分裂
- 可与
articulation_points一起用于块-割点结构分析
典型场景
- 路网：抗单路口封闭的区域识别
- 通信网络：抗单设备故障的链路块分析
- 社交网络：内部关系更稳固的群体结构
- 供应链网络：节点冗余较强的子系统识别
适用与特性
- 图类型：无向图
- 输出：
generator[list[edge]] - 复杂度：通常
O(V + E)
功能说明
将有向图中的每个强连通分量压缩为一个节点，得到一个新的有向无环图（DAG）。压缩图中的边表示不同强连通分量之间的依赖或可达关系。
产品价值
- 将复杂有向图抽象为组件级结构
- 适合从循环依赖中提取高层 DAG
- 可用于模块化分析、依赖分层和流程简化
典型场景
- 服务依赖：将互相依赖的一组服务压缩为一个模块
- 代码依赖：将循环引用包压缩后分析包间层级
- 交易网络：将资金循环团伙压缩后观察团伙间流向
- 流程网络：将循环步骤压缩后进行高层流程排序
适用与特性
- 图类型：有向图
- 输出：
DiGraph - 特点：输出图是 DAG
- 复杂度：通常
O(V + E)
功能说明
找出无向图中的桥边。桥边是删除后会增加连通分量数量的边，也称割边。
产品价值
- 直接识别单链路故障风险
- 适合链路加固、备份线路规划和网络脆弱性分析
- 与
articulation_points形成“关键边 + 关键点”的结构诊断组合
典型场景
- 道路网络：封闭后会割裂区域的道路
- 通信网络：断开后会导致子网隔离的链路
- 物流网络：中断后会导致供应断裂的运输线
- 设备网络：无备份路径的关键连接
适用与特性
- 图类型：无向图
- 输出：边迭代器
- 复杂度：
O(V + E)
功能说明
找出局部桥边。局部桥通常指边的两个端点之间没有共同邻居；如果移除该边，端点之间的最短替代路径会变长。可进一步计算该边的跨度。
产品价值
- 识别局部结构中的跨圈层连接
- 可发现不一定是全局桥、但在局部关系中非常关键的连接
- 适合社交网络、推荐网络和局部脆弱性分析
典型场景
- 社交网络：连接两个朋友圈的弱关系边
- 合作网络：连接两个团队的跨组协作关系
- 推荐网络：连接两个兴趣圈层的关键交互
- 风控网络：连接两个局部团伙的可疑关系
关键参数
with_span：是否返回局部桥的跨度weight：用于计算替代路径长度的边权字段
适用与特性
- 图类型：无向图
- 输出：边迭代器，或带跨度的边信息
- 适合局部桥接结构和弱连接分析
-
先回答“是否一张网”
- 无向图：
is_connected - 有向图结构上是否连通：
is_weakly_connected - 有向图方向上是否互达：
is_strongly_connected
- 无向图：
-
再做“分成几块、每块是谁”
- 无向图：
connected_components+number_connected_components - 有向图：
weakly_connected_components/strongly_connected_components
- 无向图：
-
做“韧性与断点定位”
- 节点冗余指标：
node_connectivity - 边冗余指标：
edge_connectivity - 最小节点割：
minimum_node_cut - 最小边割：
minimum_edge_cut
- 节点冗余指标：
-
找直观关键点与关键边
- 割点：
articulation_points - 桥边：
bridges - 局部桥边：
local_bridges
- 割点：
-
做组件级结构分析
- 桥连通块：
bridge_components - 双连通分量边集合：
biconnected_component_edges - 有向 SCC 压缩：
condensation
- 桥连通块：
- “这张无向图是不是连通的？如果不是，分成了几块？”
- “有向图在忽略方向后是否连通？方向意义上是否强连通？”
- “输出所有强连通分量，并按规模排序。”
- “将强连通分量压缩成 DAG，看看组件之间的依赖层级。”
- “这张网络最少断几条边或坏几个节点会被切开？”
- “给出一个最小节点割或最小边割集合。”
- “列出所有割点，用于单点故障排查。”
- “列出所有桥边，找出没有备份路径的关键链路。”
- “哪些边是局部桥，连接了不同的局部圈层？”
- “把网络拆成 bridge components，看看哪些区域内部更稳健。”
- “输出双连通分量的边集合，用于分析抗单点故障结构。”
-
先区分图类型
- 无向图使用
is_connected、connected_components、bridges、articulation_points等。 - 有向图使用
is_strongly_connected、strongly_connected_components、is_weakly_connected、weakly_connected_components、condensation等。
- 无向图使用
-
强连通和弱连通含义不同
- 强连通要求方向上双向可达。
- 弱连通只要求忽略方向后结构连通。
- 有向业务网络中，两者经常差异很大。
-
全局连通度与局部 s-t 连通度要区分
- 全局
node_connectivity/edge_connectivity衡量整张图最脆弱处。 - 指定
s, t后衡量两个节点之间的局部冗余能力。
- 全局
-
割点与桥边适合快速体检
articulation_points和bridges通常计算较快、解释直观。- 它们能快速定位明显单点或单边故障风险。
-
最小割更适合制定加固方案
minimum_node_cut和minimum_edge_cut直接给出需要加固或保护的节点/边集合。- 适合用于故障演练、攻击模拟和容灾规划。
-
SCC 压缩适合复杂有向图降维
- 原图中存在大量循环依赖时，可先做
condensation。 - 压缩后的图是 DAG，更适合做拓扑排序、层级分析和高层可视化。
- 原图中存在大量循环依赖时，可先做
-
局部桥不等于全局桥
bridges删除后会增加全图连通分量数量。local_bridges更强调局部邻域中的桥接作用，适合社交弱关系和跨圈层连接分析。
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | is_connected |
判断无向图是否连通 |
| 2 | connected_components |
无向图连通分量 |
| 3 | number_connected_components |
无向图连通分量数量 |
| 4 | is_strongly_connected |
判断有向图是否强连通 |
| 5 | strongly_connected_components |
强连通分量 |
| 6 | is_weakly_connected |
判断有向图是否弱连通 |
| 7 | weakly_connected_components |
弱连通分量 |
| 8 | node_connectivity |
节点连通度 |
| 9 | edge_connectivity |
边连通度 |
| 10 | minimum_node_cut |
最小节点割 |
| 11 | minimum_edge_cut |
最小边割 |
| 12 | articulation_points |
割点 |
| 13 | bridge_components |
桥连通块 |
| 14 | biconnected_component_edges |
双连通分量边集合 |
| 15 | condensation |
强连通分量压缩图 |
| 16 | bridges |
桥边 / 割边 |
| 17 | local_bridges |
局部桥 |
算子类别：Clustering & Community（聚类系数、社区发现、传递性与环结构）
算法数量：23 个
适用阶段：网络结构洞察、圈层/团伙识别、群落质量评估、闭环/循环检测、关系紧密度量化、图划分优化、二部图社区分析
产品定位：为“网络是否存在紧密小圈子 / 如何把人群或实体切成社区 / 这个切法好不好 / 是否存在闭环循环 / 如何做二分或多社区划分 / 如何识别三元结构模式”提供统一算子能力底座。
Clustering & Community 算子集覆盖四大类能力：
-
局部紧密度与网络聚集性
- 节点邻居之间是否彼此相连？
- 网络整体三角闭合程度如何？
- 是否存在小圈子、团伙或局部高密度结构？
- 典型算法：
clustering,average_clustering,triangles,transitivity,square_clustering
-
社区发现与图划分
- 在没有标签的情况下，如何自动发现社区、阵营、圈层？
- 如何进行大规模网络快速社区划分？
- 如何进行二分划分或指定社区数量划分？
- 典型算法：
greedy_modularity_communities,naive_greedy_modularity_communities,louvain_communities,leiden_communities,girvan_newman,label_propagation_communities,asyn_lpa_communities,asyn_fluidc,kernighan_lin_bisection
-
可重叠社区与二部图社区分析
- 一个节点是否可以同时属于多个社区？
- 二部图如何进行模块度意义下的二分划分？
- 典型算法：
k_clique_communities,spectral_modularity_bipartition
-
环结构与循环检测
- 图中有哪些简单环？
- 无向图的基础环集合是什么？
- 是否存在最小权重环基？
- 典型算法：
simple_cycles,cycle_basis,minimum_cycle_basis
-
社区结果评估与合法性校验
- 社区划分质量如何？
- 是否是严格分区？
- 组内边是否足够多，组间边是否足够少？
- 典型算法：
modularity,partition_quality,is_partition
-
三元结构模式分析
- 有向图中三节点之间有哪些典型结构模式？
- 网络是否存在闭合三元组、传递关系、循环三元组？
- 典型算法：
triadic_census
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 节点聚类系数 | clustering |
计算指定节点或全部节点的局部聚类系数 |
| 平均聚类系数 | average_clustering |
计算全图或指定节点集合的平均聚类系数 |
| 三角闭合计数 | triangles |
统计节点参与的三角形数量 |
| 全局传递性 | transitivity |
计算网络整体三角闭合程度 |
| 四环聚类 | square_clustering |
计算节点参与 4-cycle 的局部冗余结构倾向 |
| 社区发现-贪心模块度 | greedy_modularity_communities |
Clauset-Newman-Moore 贪心合并最大化模块度 |
| 社区发现-朴素贪心模块度 | naive_greedy_modularity_communities |
使用朴素贪心策略进行模块度优化，适合教学或小图验证 |
| 社区发现-分层拆分 | girvan_newman |
迭代移除关键边，得到层级社区结构 |
| 社区发现-同步标签传播 | label_propagation_communities |
通过邻居多数标签扩散形成社区 |
| 社区发现-异步标签传播 | asyn_lpa_communities |
异步更新标签传播，支持权重和随机种子 |
| 社区发现-k clique | k_clique_communities |
基于 k 团渗透发现可重叠社区 |
| 社区发现-Louvain | louvain_communities |
多层模块度优化，适合大图快速社区划分 |
| 社区发现-Leiden | leiden_communities |
Louvain 改进版，更稳定并强调社区内部连通性 |
| 社区发现-异步流体 | asyn_fluidc |
基于流体扩散思想划分指定数量社区 |
| 图二分划分 | kernighan_lin_bisection |
使用 Kernighan-Lin 启发式将图划分为两个部分 |
| 二部图谱模块度二分 | spectral_modularity_bipartition |
基于谱方法对二部图进行模块度二分 |
| 环结构-简单环枚举 | simple_cycles |
枚举图中的所有简单环 |
| 环结构-环基 | cycle_basis |
输出无向图的基础环集合 |
| 环结构-最小环基 | minimum_cycle_basis |
输出无向图中总权重较小的环基 |
| 三元结构普查 | triadic_census |
统计有向图中不同三节点结构模式数量 |
| 方案质量-模块度 | modularity |
对给定社区划分计算模块度 Q 值 |
| 方案质量-覆盖/性能 | partition_quality |
计算社区划分的 coverage 和 performance |
| 方案合法性 | is_partition |
检查社区列表是否为严格 partition |
-
输入
G：NetworkX Graph / DiGraph- 聚类系数多数用于无向图，也可支持部分有向或加权形式
- 简单环枚举常用于有向图，也可用于部分无向场景
- 社区发现多数用于无向图
- 二部图相关算法要求输入符合二部图结构
-
常见输出
- 指标类：
float - 计数类：
dict/int - 社区结果：
list[set]/iterable[set]/iterator[tuple[set]] - 环结构：
list[list[node]]或迭代器 - 二分结果：
tuple[set, set] - 校验类：
bool
- 指标类：
说明：
- 社区发现算法的输出通常是节点集合列表。
k_clique_communities允许重叠社区，因此其结果不一定满足严格 partition。- 模块度、覆盖率、性能等评估指标通常要求社区结果覆盖全部节点且互不重叠。
- 环枚举和 clique 类算法可能产生指数级结果，大图中应设置限制或先做子图筛选。
功能说明
计算节点聚类系数，衡量一个节点的邻居之间互相连接的比例，也就是“邻居是否也彼此认识”。
产品价值
- 识别紧密朋友圈或局部团伙核心
- 发现高密度关系区域中的关键节点
- 可作为反欺诈、社群分析和推荐系统的结构特征
典型场景
- 社交网络：找朋友圈最紧密的用户
- 交易网络：识别闭合交易关系中的账户
- 合作网络：发现高协作密度成员
- 风控网络：识别局部团伙结构
关键参数
nodes：单个节点、多节点或全图weight：边权，表示关系强度
适用与特性
- 图类型：无向图为主
- 输出：
{node: score}或单节点分数 - 复杂度：通常与节点度数平方相关
功能说明
返回全图或指定节点集合的平均聚类系数，取值通常在 0 到 1 之间，用于概括网络整体抱团程度。
产品价值
- 一句话概括网络整体聚集程度
- 适合跨网络、跨时间窗口、跨区域对比
- 可用于监控网络是否出现团伙化或圈层化趋势
典型场景
- 社交网络整体抱团程度评估
- 风控网络团伙化趋势监测
- 不同城市路网局部冗余程度对比
- 组织协作网络紧密程度比较
关键参数
nodes：只计算某个子群weight：考虑关系强度count_zeros：是否将聚类系数为 0 的节点计入平均值
适用与特性
- 图类型：无向图为主
- 输出：
float - 复杂度：通常与节点度数平方相关
功能说明
计算网络整体传递性，即闭合三元组占所有三元组的比例，用于衡量全局“三角闭合”程度。
产品价值
- 判断网络整体是否具有“朋友的朋友也是朋友”的倾向
- 可用于分析网络是否更像随机网络、小世界网络或团伙网络
- 适合全局结构特征建模
典型场景
- 社交网络：整体三角闭合程度
- 合作网络：合作关系是否容易形成三人闭环
- 风控网络：资金或账户是否形成闭合结构
- 知识网络：概念之间是否形成高度传递关系
适用与特性
- 图类型：无向图为主
- 输出：
float - 复杂度：通常与三角形计数相关
功能说明
统计每个节点参与的三角形数量，或返回指定节点的三角形数。
产品价值
- 三角形越多，节点越处于闭合小圈子中
- 可作为团伙识别、局部密度和社群核心判断特征
- 与聚类系数配合可以区分“连接多”和“连接紧密”
典型场景
- 社交网络：参与多个朋友圈闭环的用户
- 交易网络：闭合交易关系中的账户
- 合作网络：频繁形成三方合作的小组成员
- 推荐网络：共同兴趣闭环分析
关键参数
nodes：单节点、多节点或全图
适用与特性
- 图类型：无向图
- 输出：
dict或int - 复杂度：通常与节点度数和边数相关
功能说明
衡量节点参与四元环结构的倾向。四环结构常用于表示两条不同路径连接同一目标的局部冗余关系。
产品价值
- 适合分析二部图或近似二部结构中的闭合关系
- 可发现局部替代路径和结构冗余
- 在用户-商品、作者-论文、账户-设备等网络中比三角形更有解释力
典型场景
- 用户-商品网络：多个用户共同购买多个商品
- 作者-论文网络：多个作者共同参与多篇论文
- 账户-设备网络：多个账户共享多个设备
- 路网分析：局部替代路径冗余
关键参数
nodes：只计算部分节点
适用与特性
- 图类型：无向图为主
- 输出：
{node: score} - 复杂度：通常与局部邻域规模相关
功能说明
通过贪心合并策略最大化模块度，输出社区列表。该算法从小社区开始逐步合并，使模块度提升最大。
产品价值
- 经典、稳定、解释性较强
- 适合中大规模无向图的默认社区发现
- 支持通过分辨率参数控制社区尺度
典型场景
- 社交网络自然圈层识别
- 交易网络团伙初筛
- 企业关系网络集团划分
- 知识网络主题簇识别
关键参数
weight：边权resolution：社区尺度，较大通常得到更小社区cutoff：最少社区数量best_n：最多社区数量
适用与特性
- 图类型：无向图
- 输出：
list[set] - 适合：中大规模社区划分
功能说明
迭代移除最关键边，默认通常选择边介数最高的边，使图逐步分裂，从而得到从粗到细的层级社区结构。
产品价值
- 解释性强，适合展示社区如何被拆分
- 能输出多层级社区方案
- 适合小图或需要层次结构说明的场景
典型场景
- 小规模组织关系拆分
- 复杂网络教学演示
- 关键边驱动的社群分裂分析
- 需要可解释拆分路径的风控调查
关键参数
most_valuable_edge：自定义最关键边选择策略
适用与特性
- 图类型：无向图
- 输出：社区划分迭代器
- 注意：复杂度较高，不适合超大图
功能说明
基于邻居多数标签扩散形成社区。节点不断根据邻居标签更新自身标签，最终相同标签的节点形成社区。
产品价值
- 无需指定社区数量
- 速度快，适合大图快速粗分群
- 可作为后续精细社区发现的预处理结果
典型场景
- 大规模社交网络快速圈层划分
- 推荐系统用户兴趣群初筛
- 通信网络粗粒度分区
- 风控网络团伙候选发现
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：每轮通常
O(V + E)
功能说明
异步更新节点标签的标签传播算法。更新顺序会影响结果，可通过随机种子提高可复现性，也可通过权重影响邻居标签的重要性。
产品价值
- 相比同步标签传播更灵活
- 支持权重和随机性控制
- 适合大图快速社区发现
典型场景
- 权重社交网络圈层发现
- 大规模交易网络初步团伙识别
- 组织沟通网络快速分群
- 推荐网络兴趣社区划分
关键参数
weight：边权影响标签传播seed：随机种子，控制结果可复现性
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：每轮通常
O(V + E)
功能说明
以 k-clique 为基本单元，若两个 k-clique 共享 k-1 个节点，则它们属于同一社区。该方法允许节点属于多个社区。
产品价值
- 适合发现非常紧密的核心圈子
- 支持重叠社区，更符合真实社交和合作网络
- 对团伙、共谋、小团体识别具有较强解释性
典型场景
- 社交网络：允许一个人属于多个朋友圈
- 合作网络：作者参与多个研究团队
- 风控网络：账户同时参与多个团伙结构
- 生物网络：蛋白参与多个功能模块
关键参数
k：最小 clique 大小，越大越严格cliques：可传入预计算 clique 列表以减少重复计算
适用与特性
- 图类型：无向图
- 输出：
generator[frozenset(node)] - 注意：结果可重叠，不一定是严格 partition
功能说明
经典多层模块度优化方法。算法先进行局部节点移动提升模块度，再将社区压缩为超节点进行多层优化。
产品价值
- 工业界常用的大图社区发现算法
- 速度快，效果通常较好
- 支持多层社区结构和分辨率控制
典型场景
- 大规模社交网络社区划分
- 交易网络团伙识别
- 通信网络结构分区
- 知识图谱主题社区发现
关键参数
weight：边权resolution：社区尺度threshold：模块度提升阈值max_level：最大层数seed：随机种子
适用与特性
- 图类型：无向图
- 输出：
list[set] - 特点：结果可能受随机性影响，建议设置 seed
功能说明
Leiden 是 Louvain 的改进方法，通常更稳定，并强调社区内部连通性，避免出现内部断裂但仍被划为同一社区的问题。
产品价值
- 社区质量通常比 Louvain 更稳健
- 适合对社区内部连通性有要求的场景
- 更适合严谨的社区结构分析和产品化输出
典型场景
- 大规模社交网络严谨分群
- 金融风控团伙识别
- 生物网络功能模块识别
- 组织网络稳定圈层划分
关键参数
weight：边权resolution：社区尺度max_level：最大层数seed：随机种子
适用与特性
- 图类型：无向图
- 输出：
list[set] - 特点：通常比 Louvain 更稳定
功能说明
使用朴素贪心方式进行模块度优化。相比优化版本更直观，但性能较弱，更适合教学、小图验证或算法结果对照。
产品价值
- 算法逻辑更容易解释
- 适合小规模图上的社区发现验证
- 可作为贪心模块度算法的参考实现或对照方案
典型场景
- 小规模网络社区划分
- 教学演示模块度最大化过程
- 与优化版贪心模块度算法做结果对比
- 调试社区划分逻辑
关键参数
weight：边权resolution：社区尺度
适用与特性
- 图类型：无向图
- 输出：社区集合列表
- 注意：不建议用于超大图
功能说明
基于谱方法对二部图进行模块度意义下的二分划分，将节点划分为两个模块。
产品价值
- 适合二部图结构的社区划分
- 能保留用户-物品、作者-论文等两侧关系的原始结构
- 避免直接投影到单侧图造成信息损失
典型场景
- 用户-商品网络社区划分
- 作者-论文网络研究方向划分
- 机构-项目网络模块识别
- 账户-设备网络风险簇拆分
适用与特性
- 图类型：二部图
- 输出：二分结果
- 适合：二部图模块度分析
功能说明
基于流体扩散思想进行社区发现。用户需要指定社区数量 k，算法通过异步更新逐步形成指定数量的社区。
产品价值
- 可以显式控制社区数量
- 速度较快，适合需要固定分群数量的场景
- 与标签传播类算法一样，适合作为快速社区划分方法
典型场景
- 需要固定划分为 K 个区域的网络
- 用户分群数量已知的推荐系统
- 运维网络固定分区
- 风控策略中按指定数量生成候选团伙
关键参数
k：需要划分的社区数量max_iter：最大迭代次数seed：随机种子
适用与特性
- 图类型：通常要求连通无向图
- 输出：
iterable[set(node)] - 注意：需要提前指定社区数量
功能说明
使用 Kernighan-Lin 启发式方法将图划分为两个部分，目标是减少两个部分之间的割边权重。
产品价值
- 适合图二分、负载均衡和任务拆分
- 可用于需要两个区域、两组节点或二分实验的场景
- 比单纯社区发现更偏向“平衡切分”或“降低跨组连接”
典型场景
- 计算任务图二分调度
- 网络分区与负载均衡
- A/B 分组中的结构化拆分
- 电路或模块划分
关键参数
partition：可传入初始二分max_iter：最大迭代次数weight：边权seed：随机种子
适用与特性
- 图类型：无向图
- 输出：
tuple[set, set] - 特点：启发式算法，不保证全局最优
功能说明
枚举图中的所有简单环。简单环指起点和终点相同，且中间节点不重复的环路。
产品价值
- 发现资金回流、循环交易、循环依赖
- 识别反馈回路和闭环传播结构
- 可用于有向网络中的闭环风险排查
典型场景
- 资金网络：循环交易链路
- 软件依赖：循环依赖链
- 生物网络：反馈调控环
- 流程网络：异常闭环流程
关键参数
length_bound：限制环长度，避免输出爆炸
适用与特性
- 图类型：有向图为主
- 输出：环路径迭代器或列表
- 注意：环数量可能非常多，建议设置长度上限
功能说明
为无向图输出一个 cycle basis，即能够组合生成所有环的基础独立环集合。
产品价值
- 将复杂环结构分解为基础构件
- 适合电路、路网、管网等环状结构分析
- 比枚举所有环更适合做结构摘要
典型场景
- 电路网络：基础回路分析
- 道路网络：基本闭合街区识别
- 管网系统：基础环路结构识别
- 关系网络：基础闭环结构摘要
关键参数
root：可选起始节点
适用与特性
- 图类型：无向图
- 输出：
list[list[node]]
功能说明
输出无向图的最小环基，即在权重意义下总长度或总成本较小的一组基础环。
产品价值
- 相比普通环基，更偏向选择成本更低、规模更小或权重更优的基础环集合
- 适合需要最简闭环解释的场景
- 可用于电路、路网、管网中的低成本环结构分析
典型场景
- 电路网络：最小基础回路分析
- 路网网络：最短闭合街区识别
- 管网系统：低成本基础环路分析
- 化学结构：最小环系统识别
关键参数
weight：边权字段，表示距离、成本或长度
适用与特性
- 图类型：无向图
- 输出：
list[list[node]] - 适合：中小规模图或需要最小闭环摘要的场景
功能说明
统计有向图中所有三节点子图的结构类型数量。不同三元组模式可表示互惠、传递、循环、空连接等不同关系形态。
产品价值
- 从三节点模式层面刻画有向网络结构
- 可用于判断网络是否偏向传递关系、循环关系或互惠关系
- 适合社交、交易、通信、组织和生态网络的微观结构分析
典型场景
- 社交网络：互粉、单向关注、三人闭环模式统计
- 交易网络：三账户循环交易结构分析
- 组织网络：层级传递关系和反馈关系识别
- 通信网络：三节点消息流模式分析
适用与特性
- 图类型：有向图
- 输出：三元组类型计数字典
- 适合：微观结构模式统计和网络画像
功能说明
对给定社区划分计算模块度 Q 值，衡量社区内部边是否多于随机期望、社区之间边是否相对较少。
产品价值
- 为社区划分提供统一质量评分
- 适合比较不同社区发现算法或不同参数结果
- 是 Louvain、Leiden、贪心模块度等算法的核心优化目标
典型场景
- 比较 Louvain 与 Leiden 的社区划分质量
- 调整 resolution 参数后选择更合适的结果
- 评估人工分群是否符合网络结构
- 社区发现结果上线前质量校验
关键参数
communities：社区列表，通常应为严格 partitionweight：边权resolution：分辨率参数
适用与特性
- 输出：
float - 注意：模块度越高通常越好，但需结合业务场景和社区尺度解释
功能说明
计算社区划分的两个质量指标：
- coverage：社区内部边占全部边的比例
- performance：社区内部边和社区外部非边在所有节点对中的比例
产品价值
- 从不同角度评估社区划分质量
- coverage 强调组内连接是否多
- performance 同时考虑组内连接和组间分离是否合理
典型场景
- 社区划分方案质量评估
- 人工分群与算法分群对比
- 社群边界清晰度判断
- 风控团伙切分效果评估
适用与特性
- 输入：社区划分
- 输出：
(coverage, performance) - 注意：通常要求社区划分为严格 partition
功能说明
检查给定社区列表是否为严格 partition，即是否覆盖全部节点且各社区之间互不重叠。
产品价值
- 社区评估前的基础校验
- 防止漏节点、重复分配节点导致指标失真
- 适合社区发现结果进入下游流程前做质量检查
典型场景
- 检查算法输出是否覆盖所有用户
- 检查人工分群是否有重复成员
- 在计算 modularity 前验证社区结果
- 社区结果写入数据库前做合法性校验
适用与特性
- 输入：图和社区列表
- 输出：
bool - 注意：可重叠社区如
k_clique_communities通常不满足严格 partition
-
想先衡量网络是否抱团
- 全局抱团程度：
average_clustering/transitivity - 局部抱团程度：
clustering - 三角闭合结构：
triangles - 四环冗余结构：
square_clustering
- 全局抱团程度：
-
想快速得到社区
- 大图默认优先：
louvain_communities/leiden_communities - 快速粗分群：
label_propagation_communities/asyn_lpa_communities - 指定社区数量：
asyn_fluidc
- 大图默认优先：
-
想要解释性或层级拆分
- 分层社区：
girvan_newman - 二分划分：
kernighan_lin_bisection - 小图贪心验证：
naive_greedy_modularity_communities
- 分层社区：
-
想找重叠小圈子
- 可重叠紧密社区：
k_clique_communities
- 可重叠紧密社区：
-
想处理二部图社区
- 二部图谱模块度二分：
spectral_modularity_bipartition
- 二部图谱模块度二分：
-
想查闭环、循环依赖或资金回流
- 所有简单环：
simple_cycles - 基础环集合：
cycle_basis - 最小基础环集合：
minimum_cycle_basis
- 所有简单环：
-
想做三节点模式分析
- 有向三元结构统计：
triadic_census
- 有向三元结构统计：
-
想评估社区结果
- 模块度：
modularity - 覆盖率与性能：
partition_quality - 合法性校验：
is_partition
- 模块度：
- “网络整体更像松散随机还是小世界？给我一个总体指标。”
- “哪些节点的朋友圈最紧？列 Top-20 聚类系数。”
- “哪些节点参与最多三角形？”
- “这个二部网络是否存在明显四环冗余结构？”
- “把网络自动分成几个自然社区，并输出每个社区成员。”
- “用 Louvain 和 Leiden 分别划分社区，并比较模块度。”
- “我希望固定分成 5 个社区，应该怎么划分？”
- “把图二分成两个部分，尽量减少跨组连接。”
- “找允许重叠的核心小圈子。”
- “这个社区结果是不是严格分区？有没有漏节点或重复分配？”
- “我有两种社区划分方案，哪个更好？给出 modularity 和 coverage/performance。”
- “找出所有资金闭环或循环依赖链路，并限制环长度不超过 6。”
- “输出无向图的最小环基，用于分析基础闭环结构。”
- “统计有向图中的三元结构模式，看看传递关系和循环关系分别有多少。”
-
先明确分析目标
- 聚类系数回答“局部关系是否紧密”。
- 社区发现回答“节点如何自然分组”。
- 环结构算法回答“是否存在闭环或循环路径”。
- 社区评估算法回答“这个划分好不好”。
-
社区发现算法没有唯一正确答案
- Louvain、Leiden、标签传播、Girvan-Newman 机制不同，结果可能不同。
- 建议结合
modularity、partition_quality和业务解释综合选择。 - 随机算法建议设置
seed保证可复现。
-
大图优先选择高效算法
- 大规模图优先使用
louvain_communities、leiden_communities、asyn_lpa_communities。 girvan_newman解释性强，但更适合小图。- clique、环枚举类算法在大图中可能非常慢。
- 大规模图优先使用
-
重叠社区与严格分区要区分
k_clique_communities允许节点属于多个社区。modularity、partition_quality、is_partition通常面向严格 partition。- 不要用严格分区指标直接评估重叠社区，除非先做转换。
-
二部图不要随意投影
- 用户-商品、作者-论文等二部图投影后可能产生大量虚假边。
- 二部图社区分析优先考虑
spectral_modularity_bipartition等保留二部结构的方法。 - 如需投影，应明确投影规则和边权含义。
-
环结构算法要控制输出规模
simple_cycles的结果数量可能指数级增长。- 工程中建议使用
length_bound或先筛选子图。 - 若只需要结构摘要，无向图可优先使用
cycle_basis或minimum_cycle_basis。
-
三角形、四环、三元组适合做结构特征
triangles、square_clustering、triadic_census可作为机器学习或风控规则特征。- 它们不一定直接给出社区，但能刻画局部模式和结构异常。
-
模块度存在分辨率限制
resolution会影响社区大小。- 较高 resolution 往往得到更小社区，较低 resolution 往往得到更大社区。
- 不同业务场景应选择不同尺度，不宜只追求最高模块度。
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | clustering |
节点聚类系数 |
| 2 | average_clustering |
平均聚类系数 |
| 3 | transitivity |
全局传递性 |
| 4 | triangles |
三角形数量统计 |
| 5 | square_clustering |
四环聚类系数 |
| 6 | greedy_modularity_communities |
贪心模块度社区发现 |
| 7 | girvan_newman |
Girvan-Newman 分层社区发现 |
| 8 | label_propagation_communities |
同步标签传播社区发现 |
| 9 | asyn_lpa_communities |
异步标签传播社区发现 |
| 10 | k_clique_communities |
k 团渗透可重叠社区发现 |
| 11 | louvain_communities |
Louvain 社区发现 |
| 12 | leiden_communities |
Leiden 社区发现 |
| 13 | simple_cycles |
简单环枚举 |
| 14 | cycle_basis |
环基 |
| 15 | modularity |
模块度评分 |
| 16 | partition_quality |
覆盖率与性能评估 |
| 17 | is_partition |
社区分区合法性校验 |
| 18 | naive_greedy_modularity_communities |
朴素贪心模块度社区发现 |
| 19 | spectral_modularity_bipartition |
二部图谱模块度二分 |
| 20 | minimum_cycle_basis |
最小环基 |
| 21 | triadic_census |
三元结构普查 |
| 22 | asyn_fluidc |
异步流体社区发现 |
| 23 | kernighan_lin_bisection |
Kernighan-Lin 图二分 |