跳到主要内容

Connectivity & Components 连通性与组件算子集

算子类别：Connectivity & Components（连通性、连通分量与割/切割分析）

适用阶段：网络结构体检、孤岛/分区识别、稳健性评估、关键节点/关键边定位、故障/攻击面分析

产品定位：为“网络是否连通 / 分成几块 / 哪些节点或边一断就分裂 / 最少切多少才能断开”提供统一能力底座

一、算子集概述​

Connectivity & Components 算子集面向无向图与有向图的连通性分析，覆盖三类核心问题：

  1. 连通性与连通分量

    • 无向图是否整体连通？分成多少个连通块？（is_connected / connected_components / number_connected_components）
    • 有向图在方向意义上是否强连通？弱连通？（is_strongly_connected / strongly_connected_components / is_weakly_connected / weakly_connected_components）

  2. 网络稳健性（Connectivity 指标）

    • 最少需要移除多少节点才能让网络断开？（node_connectivity）
    • 最少需要移除多少边才能让网络断开？（edge_connectivity）

  3. 割与关键结构（Cuts / Critical Elements）

    • 最小节点割/边割集合是什么？（minimum_node_cut / minimum_edge_cut）
    • 哪些节点是割点（articulation points）？哪些结构是“桥”分解出来的块？（articulation_points / bridge_components）

二、算子能力分类​

能力类型对应算子功能描述
无向图整体连通性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

三、通用输入输出约定​

  • 输入 G：NetworkX Graph / DiGraph（按算法要求：部分仅支持无向图/有向图）
  • 输出：
    • 判定类：bool
    • 分量类：generator[set(node)]
    • 连通性指标：int
    • 最小割：set(node) 或 set(edge)
    • 割点：迭代器（可转 list）
    • bridge_components：2-边连通分量生成器（每项为节点集合）

说明：

  • “强连通/弱连通”只对有向图有意义。
  • “割点/桥连通块”通常针对无向图的结构稳健性分析。

四、算子详细说明​

1. is_connected —— 无向图是否连通​

功能说明
判断无向图中是否任意两点都存在路径可达。

产品价值

  • 网络健康度的第一道体检
  • 快速判断是否存在孤岛/断裂区域

典型场景

  • 道路网络是否存在完全孤立区域
  • 设备互联拓扑是否为“一张网”
  • 社交网络是否存在完全隔离圈子

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

2. connected_components —— 无向图连通分量划分​

功能说明
输出无向图中每个连通分量的节点集合（一个分量就是一个“互相可达的子网络”）。

产品价值

  • 识别网络被切成了哪些“运营/社群/拓扑区域”
  • 为后续在分量内做统计、建模、调度提供分区边界

典型场景

  • 物流站点网络：分出互不连通的运营区域
  • 设备互联：找出孤立子网
  • 社交网络：识别互相不接触的圈子

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

3. number_connected_components —— 连通分量数量​

功能说明
返回无向图连通分量个数。

产品价值

  • 快速量化“碎片化程度”
  • 作为网络健康 KPI（分量越多通常越不健康/越割裂）

典型场景

  • 城市路网断裂后的分区数量评估
  • 设备网络故障后的子网数量
  • 协作网络中孤立团队数量

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

4. is_strongly_connected —— 有向图是否强连通​

功能说明
判断有向图是否满足：任意两点之间都“来回可达”（u→v 且 v→u 都可达）。

产品价值

  • 判断系统是否形成闭环结构（能否回路）
  • 适合分析“互相调用/互相跳转/资金可循环”的系统

典型场景

  • 服务调用：是否互相可达形成统一模块
  • 页面导航：是否任意页面都能到任意页面并返回
  • 交易流：是否形成可回流的闭环网络

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

5. strongly_connected_components —— 强连通分量（SCC）​

功能说明
输出有向图的 SCC 划分：每个 SCC 内任意两点双向可达。

产品价值

  • 识别“循环模块/闭环群组”
  • 常用于依赖分析、死循环排查、模块化拆解

典型场景

  • 服务依赖图：找出互相依赖成环的模块
  • 流程图：找出可以回到起点的循环步骤群
  • 交易网络：识别资金循环小团体

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

6. is_weakly_connected —— 有向图是否弱连通​

功能说明
将有向图视为无向图（忽略方向）后，判断是否连通。

产品价值

  • 判断“结构上是否一张网”，即使方向上不一定互达
  • 适合“有方向但仍想看整体是否割裂”的场景

典型场景

  • 邮件发送网络：忽略方向看组织是否连成整体
  • 关注网络：忽略方向看用户是否割裂成多个群落
  • 页面链接：忽略方向看站点是否被分割成孤岛

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

7. weakly_connected_components —— 弱连通分量（WCC）​

功能说明
在忽略方向后，将有向图划分为若干互相连通的分量。

产品价值

  • 识别方向网络的“结构分区”
  • 为分区内进一步做 SCC、中心性等分析提供边界

典型场景

  • 关注/邮件网络：识别互不相连的社群域
  • 服务调用：识别互不关联的业务域

适用与特性

  • 图类型：有向图
  • 复杂度：O(V + E)

8. node_connectivity —— 节点连通度（稳健性指标）​

功能说明
返回最少需要删除多少节点才能让图断开；若给定 s, t，则返回最少删除多少节点能让 s 与 t 不连通。

产品价值

  • 量化网络“抗节点故障/攻击”能力
  • 评估关键设备/关键岗位的冗余程度

典型场景

  • 数据中心：最少坏几台设备网络会断
  • 城市路网：最少封几处路口会割裂
  • 协作网络：最少离开几个人团队就分裂

关键参数

  • s, t：做局部（源-宿）连通度
  • flow_func：最大流实现选择（影响性能）

适用与特性

  • 图类型：有向/无向（实现基于流）
  • 复杂度：流算法相关（Flow based）

9. edge_connectivity —— 边连通度（稳健性指标）​

功能说明
返回最少需要删除多少边才能让图断开；若给定 s, t，则返回最少删多少边能让 s 与 t 不连通。

产品价值

  • 量化网络“抗链路故障/攻击”能力
  • 用于链路冗余规划与加固

典型场景

  • 机房链路：最少断几条链路会割裂
  • 道路网络：最少封几条路就会分区
  • 物流网络：最少中断几条线路会断供

关键参数

  • flow_func：最大流实现选择
  • cutoff：达到阈值提前停止（加速但可能只适用于阈值判断）

适用与特性

  • 图类型：有向/无向（实现基于流）
  • 复杂度：流算法相关（Flow based）

10. minimum_node_cut —— 最小节点割集合​

功能说明
输出一个最小节点集合，删除这些节点后图断开；或（给定 s, t）删除后 s 与 t 不可达。

产品价值

  • 直接给出“最脆弱节点集合”
  • 用于故障演练、攻击面评估、加固优先级制定

典型场景

  • 数据中心：最少哪几台设备一起坏会断网
  • 交通：最少封哪几个路口会割裂
  • 电网：最少哪几个站点失效会分区

关键参数

  • s, t：做局部割（源-宿）
  • flow_func：最大流实现

11. minimum_edge_cut —— 最小边割集合​

功能说明
输出一个最小边集合，删除这些边后图断开；或（给定 s, t）删除后 s 与 t 不可达。

产品价值

  • 直接定位“最脆弱链路集合”
  • 用于链路加固、备份线路规划

典型场景

  • 机房：最少切哪几条链路会割裂
  • 城市路网：最少封哪几条路会分区
  • 物流：最少中断哪几条线路会断供

关键参数

  • s, t：局部割
  • flow_func：最大流实现

12. articulation_points —— 割点（关键节点）​

功能说明
在无向图中，删除某节点会导致连通分量数量增加，则该节点是割点。

产品价值

  • 识别“单点故障”节点（最典型的关键节点）
  • 与 node_connectivity/最小割互补：割点给出“结构上最明显的薄弱点”

典型场景

  • 城市路网：封闭哪些路口会导致交通割裂
  • 数据中心：哪些设备故障会导致网络分裂
  • 社交网络：哪些用户离开会把社群拆开

适用与特性

  • 图类型：无向图
  • 复杂度：O(V + E)

13. bridge_components —— 桥连通块（2-edge-connected components）​

功能说明
找出无向图中所有 2-边连通分量：在同一分量内，任意两点之间至少存在两条边不相交的替代路径（更抗“单边断裂”）。算法通过识别桥（cut edges）并据此分解图。

产品价值

  • 将网络拆成“内部冗余更强”的结构块
  • 适合做网络分区、韧性模块识别、加固分层

典型场景

  • 路网：内部替代路线更丰富的区域块
  • 数据中心：内部链路冗余更高的设备群
  • 协作网络：内部联系更稳固的合作小组

适用与特性

  • 图类型：无向图（支持 multigraph）
  • 复杂度：O(V + E)

五、推荐使用指南（实践建议）​

  • 先回答“是否一张网”：

    • 无向：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
    • 结构块：bridge_components

六、可直接回答的典型问题（示例）​

  • “这张无向图是不是连通的？如果不是，分成了几块？”
  • “有向图在忽略方向后是否连通？方向意义上是否强连通？”
  • “输出所有强连通分量（SCC），并按规模排序。”
  • “这张网络最少断几条边/坏几个节点会被切开？”
  • “给出一个最小节点割/最小边割集合。”
  • “列出所有割点（articulation points），用于单点故障排查。”
  • “把网络拆成 bridge components，看看哪些区域内部更稳健。”

Clustering & Community 聚类与社区算子集

算子类别：Clustering & Community（聚类系数、社区发现、传递性与环结构）

适用阶段：网络结构洞察、圈层/团伙识别、群落质量评估、闭环/循环检测、关系紧密度量化

产品定位：为“网络是否存在紧密小圈子 / 如何把人群或实体切成社区 / 这个切法好不好 / 是否存在闭环循环”提供统一算子能力底座

一、算子集概述​

Clustering & Community 算子集覆盖两大类能力：

  1. 局部紧密度与网络聚集性（Clustering / Transitivity）

    • 节点/网络整体是否“抱团”？
    • 三角闭合（triangle closure）倾向强不强？
    • 适合从“微观局部结构”判断网络是否存在小圈子、团伙、强关系群。

  2. 社区发现与方案评估（Community Detection & Evaluation）

    • 在没有标签的情况下，自动找到社区/阵营/圈层。
    • 支持不同机制：模块度最大化、标签传播、分层拆分、k-clique 渗透（可重叠社区）。
    • 对得到的社区切分进行质量评分与合法性校验。

另外，本类别也包含环结构/循环检测能力（simple_cycles / cycle_basis），用于识别资金回流、循环依赖、反馈回路等闭环模式。

二、算子能力分类​

能力类型对应算子功能描述
节点聚类系数clustering计算指定节点或全部节点的聚类系数
平均聚类系数average_clustering计算全图或子集节点的平均聚类系数
三角闭合计数triangles统计节点参与的三角形数量
全局传递性transitivity计算网络整体“朋友的朋友也是朋友”的程度
四环聚类square_clustering计算节点参与 4-cycle 的局部冗余结构倾向
社区发现-贪心模块度greedy_modularity_communitiesClauset–Newman–Moore 贪心合并最大化模块度
社区发现-分层拆分girvan_newman迭代移除“最关键边”得到分层社区结构
社区发现-同步标签传播label_propagation_communities通过邻居多数标签扩散形成社区
社区发现-异步标签传播asyn_lpa_communities异步更新标签传播（可控权重与随机种子）
社区发现-k cliquek_clique_communities基于 k 团渗透的可重叠社区发现
社区发现-Louvainlouvain_communities多层模块度优化，适合大图快速社区划分
社区发现-Leidenleiden_communitiesLouvain 改进版，更稳定且保证社区内部连通性
环结构-简单环枚举simple_cycles列举图中的所有简单环（可设置长度上限）
环结构-环基cycle_basis无向图的基础环集合（cycle space basis）
方案质量-模块度modularity对给定划分计算 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]] 或迭代器
    • 校验：bool

四、算子详细说明​

4.1 局部紧密度与聚集性​

1) clustering —— 节点聚类系数​

功能说明
计算节点聚类系数：衡量一个节点的邻居之间互相连接的比例（“邻居是否也彼此认识”）。

产品价值

  • 找“紧密朋友圈”中心节点
  • 团伙/密集团体的候选核心点

关键参数

  • nodes：单个节点 / 多节点 / None（全图）
  • weight：加权聚类（边权表示关系强度）

复杂度：O(V * d^2)（d 为平均度）

2) average_clustering —— 平均聚类系数​

功能说明
返回全图或指定节点集合的平均聚类系数，取值 0~1。

产品价值

  • 一句话概括“整体抱团程度”
  • 用于网络对比、版本对比、区域对比

关键参数

  • nodes：只看某个子群
  • weight：考虑关系强度
  • count_zeros：是否把聚类系数为 0 的节点计入平均值

复杂度：O(V * d^2)

3) triangles —— 三角形数量统计​

功能说明
统计每个节点参与的三角形数量，或返回指定节点的三角形数。

产品价值

  • 三角形越多，节点越处于“闭合小圈子”中
  • 可用于反欺诈/团伙识别中的结构特征

关键参数

  • nodes：单节点 / 多节点 / None（全图）

复杂度：O(V * d^2) 或 O(E^{1.5})（实现相关）

4) transitivity —— 全局传递性​

功能说明
全局指标：闭合三元组（triangle）占所有三元组的比例，衡量整体“三角闭合”程度。

产品价值

  • “朋友的朋友也更可能是朋友”在网络整体是否成立
  • 判断网络是否更像随机网络还是小世界网络（倾向性指标）

复杂度：O(V * d^2)

5) square_clustering —— 四环聚类系数（4-cycle）​

功能说明
衡量节点参与“4-cycle（四元环）”结构的倾向，常用于二部图或替代路径冗余分析。

产品价值

  • 发现“通过两条不同路径连接同一目标”的冗余关系
  • 二部图中经常比三角形更有意义（例如用户-商品）

关键参数

  • nodes：只计算子集节点

复杂度：O(V * d^2)

4.2 社区发现（Community Detection）​

6) greedy_modularity_communities —— 贪心模块度社区​

功能说明
通过贪心合并策略最大化 modularity，输出社区列表（按规模排序）。

适用特点

  • 速度快、实现经典
  • 适合中大规模无向图，支持边权

关键参数

  • weight：边权
  • resolution：控制社区尺度（<1 更大社区；>1 更小社区）
  • cutoff / best_n：控制停止条件与社区数量范围

7) girvan_newman —— Girvan–Newman 分层社区​

功能说明
迭代移除“最关键边”（默认边介数最大）使图逐步分裂，得到一棵分层社区结构（从粗到细）。

产品价值

  • 适合解释性强的“结构拆分”
  • 能输出多层级方案（适合小图/需要层次结构）

关键参数

  • most_valuable_edge：自定义“最关键边”的评分/选择方式

复杂度：较高（O(E^2 * V)），不适合超大图

8) label_propagation_communities —— 同步标签传播​

功能说明
基于邻居多数投票的标签扩散，无需优化目标，通常速度快。

产品价值

  • 超大图快速粗分群
  • 适合“先出结果再细化”的场景

复杂度：每轮 O(V + E)（迭代轮数依图而定）

9) asyn_lpa_communities —— 异步标签传播​

功能说明
与 LPA 类似，但采用异步更新顺序，允许通过随机种子控制可复现性，并可使用权重影响标签频率。

关键参数

  • weight：边权影响邻居标签“出现频率”
  • seed：随机状态，影响结果稳定性/可复现性

10) k_clique_communities —— k 团渗透（可重叠社区）​

功能说明
以 k-clique（完全子图）为基本单元，若两个 k-clique 共享 k-1 个节点则视为相邻，从而形成“渗透社区”。节点可属于多个社区（重叠）。

产品价值

  • 找“非常紧密”的核心圈子
  • 允许成员重叠，符合真实社交/合作网络

关键参数

  • k：最小 clique 大小（越大越严格，社区更小更紧）
  • cliques：可传入预计算 clique 列表（可显著节省重复计算）

复杂度：受 clique 枚举影响，通常指数级（适合中小图或局部子图）

11) louvain_communities —— Louvain 社区​

功能说明
经典多层模块度优化方法，速度快、适合大规模无向图（支持权重）。

关键参数

  • weight：边权
  • resolution：社区尺度
  • threshold / max_level / seed：收敛阈值、层数、随机性控制

特点

  • 工业界常用的“默认首选”之一
  • 结果可能随随机性变化（seed 可控）

12) leiden_communities —— Leiden 社区​

功能说明
Louvain 的改进版本，通常更稳定，且强调社区内部连通性（避免“看起来一组但内部断裂”的坏社区）。

关键参数

  • weight / resolution
  • max_level / seed

特点

  • 质量更稳，适合对社区结构有严谨性要求的场景

4.3 环结构与循环检测​

13) simple_cycles —— 简单环枚举​

功能说明
枚举图中所有简单环（不重复节点，起点=终点）。可设置 length_bound 限制环长度。

产品价值

  • 发现资金回流、循环交易
  • 发现软件依赖中的循环依赖
  • 发现生物代谢/调控网络的反馈环

关键参数

  • length_bound：限制环长度，避免爆炸式输出

复杂度：O((V + E) * (C + 1))（C 为环数量）

14) cycle_basis —— 环基（无向图）​

功能说明
为无向图输出一个 cycle basis：能够组合生成所有环的“基础独立环集合”。

产品价值

  • 电路网格分析（基尔霍夫法则）
  • 道路网络的基本闭合街区识别
  • 分解复杂环结构为基本构件

4.4 社区结果评估与校验​

15) modularity —— 模块度评分（Q 值）​

功能说明
对给定社区划分计算 modularity：衡量“组内边多、组间边少”的程度。

关键参数

  • communities：必须是对节点的 partition（互斥且覆盖）
  • weight / resolution

产出：float（通常越大越好，但需结合网络类型与分辨率理解）

16) partition_quality —— 覆盖率与性能​

功能说明
输出 (coverage, performance)：

  • coverage：社区内部边占比（内部边多不多）
  • performance：内部边 + 外部非边的比例（分隔做得好不好）

17) is_partition —— 分区合法性校验​

功能说明
检查给定社区列表是否是严格 partition：

  • 是否覆盖全部节点
  • 是否互相不重叠

注意

  • 对于允许重叠社区的算法（如 k_clique_communities），其输出通常不满足 partition 定义，此时不应强行用 is_partition 验证。

五、推荐使用指南（选型建议）​

  • 想先衡量网络是否“抱团”：average_clustering + transitivity
  • 想找局部紧密核心点/团伙特征：clustering + triangles（必要时 square_clustering）
  • 想快速得到社区（大图优先）：louvain_communities 或 leiden_communities
  • 想要更解释性的分层拆分（小图）：girvan_newman
  • 想极快粗分群（超大图）：label_propagation_communities / asyn_lpa_communities
  • 想找可重叠、极紧密的小圈子：k_clique_communities
  • 想给划分打分：modularity + partition_quality（先 is_partition 校验）
  • 想查闭环/循环依赖/资金回流：simple_cycles（必要时加 length_bound），无向图用 cycle_basis

六、可直接回答的典型问题（示例）​

  • “网络整体更像松散随机还是小世界？给我一个总体指标。”
  • “哪些节点的朋友圈最紧？列 Top-20 的聚类系数/三角形数。”
  • “把网络自动分成几个自然社区，并输出每个社区成员。”
  • “我有两种社区划分方案，哪个更好？给出 modularity 和 coverage/performance。”
  • “这个社区结果是不是严格分区？有没有漏人/重复分配？”
  • “找出所有资金闭环/循环依赖链路（可限制环长度）。”
  • “找允许重叠的核心小圈子（铁三角串起来的社群）。”