跳到主要内容

Distance & Measures 距离与结构度量算子集

算子类别：Distance & Measures（距离与结构度量）
描述：提供一组全局/半全局图指标，用于衡量网络的“跨度、紧凑性、中心位置、边缘位置、整体距离成本、同质连接倾向”等结构属性。常用于网络体检、拓扑对比、韧性评估、传播/追踪成本评估与结构偏好分析。

一、算子集概述​

Distance & Measures 算子集主要覆盖两类指标：

1️⃣ 距离相关的全局结构指标（Distance-based）​

围绕 最短路距离（Shortest Path Distance）构建：

  • eccentricity（离心率）：单个节点“到最远点的距离”
  • radius（半径）：全图最小离心率（最优中心的最坏距离）
  • diameter（直径）：全图最大离心率（网络最远两点距离）
  • center（中心）：离心率最小的节点集合
  • periphery（边缘）：离心率等于直径的节点集合
  • wiener_index（维纳指数）：全对最短路距离总和（整体“距离成本/紧凑性”）

2️⃣ 结构偏好与同配性（Assortativity）​

衡量“连接是否倾向于相似者相连”：

  • degree_assortativity_coefficient：度同配（高活跃是否更爱连高活跃）
  • attribute_assortativity_coefficient：属性同配（同标签/同类型是否更爱互连）

二、算子列表​

算子核心输出直观含义
eccentricitydict[node→e]节点到最远节点的最短路距离
radiusint/float全图最小离心率（最佳中心的最坏距离）
diameterint/float全图最大离心率（最远两点距离）
centerlist[nodes]离心率最小的中心节点集合
peripherylist[nodes]离心率等于直径的边缘节点集合
wiener_indexnumber全对最短路距离之和（整体距离成本）
degree_assortativity_coefficientfloat r度同配系数（-1~1）
attribute_assortativity_coefficientfloat r属性同配系数（-1~1）

三、通用输入输出约定​

3.1 输入（Input）​

  • G：NetworkX graph（支持有向/无向，部分优化仅对无向图有效）

  • weight（可选）：边权字段名 / 函数 / None

    • None：每条边距离=1（无权图）
    • string：从 G.edges[u, v][weight] 取距离
    • function：自定义边距离函数（需返回正数）
      ⚠️ 说明：浮点权重可能带来微小舍入误差，尽量使用整数权重；权重应为正（距离语义）。

  • e（可选）：预计算的 eccentricity 字典（center / radius / diameter / periphery 可复用）

  • usebounds（可选）：无向图的 extrema bounding 加速开关（仅在 e is None 时生效）

  • sp（可选）：预计算的最短路距离字典（eccentricity 可复用）

  • nodes（可选）：assortativity 指标可限定在某个节点子集上计算

  • attribute（必填）：attribute_assortativity_coefficient 的节点属性键

  • x / y（可选）：有向图的度类型选择（degree assortativity，用于指定源/目标使用 in 或 out）

3.2 输出（Output）​

  • 距离类：数值（int/float）、节点列表或节点→指标字典
  • 同配性：单个浮点数 r（通常在 [-1, 1] 区间）

四、算子详细说明​

4.1 eccentricity —— 离心率（节点最远距离）​

功能说明​

对节点 v，离心率定义为：

v 到所有可达节点的最短路距离中的最大值

输出默认给出 所有节点 的离心率字典；也可通过 v 仅查询某个节点。

参数要点​

  • v（可选）：仅返回指定节点的离心率
  • sp（可选）：传入预计算 all-pairs shortest path lengths，避免重复计算
  • weight（可选）：按加权最短路计算距离

原理与复杂度​

  • 依赖最短路计算（无权 BFS / 有权 Dijkstra 等）
  • 时间复杂度：通常为 O(V · (V + E))（按 APSP/多源最短路规模）

适用场景​

  • 识别“最偏远/最难触达”的节点（离心率大）
  • 评估单点监控入口的最坏追踪距离

4.2 radius —— 图半径（最佳中心的最坏距离）​

功能说明​

半径定义为全图离心率的最小值：

radius(G) = min_v eccentricity(v)

它回答的是：

  • “如果选最优的中心点，最坏情况下离最远点有多远？”

调优点​

  • 传入 e（预计算离心率）可以复用，加速多指标联算
  • 无向图可用 usebounds=True 尝试加速（当 e 未提供）

复杂度​

  • 时间复杂度：O(V · (V + E))（通常与 eccentricity 同量级）

4.3 diameter —— 图直径（网络跨度上界）​

功能说明​

直径定义为全图离心率的最大值：

diameter(G) = max_v eccentricity(v)

它回答的是：

  • “网络中最远的两点，至少要走多少最短路距离？”

调优点​

同 radius：

  • 传入 e 可加速
  • 无向图可尝试 usebounds=True

复杂度​

  • 时间复杂度：O(V · (V + E))（通过 APSP/多源最短路）

4.4 center —— 图中心（最小离心率节点集合）​

功能说明​

中心是离心率最小的节点（可能不止一个）：

center(G) = { v | eccentricity(v) == radius(G) }

输出：中心节点列表。

典型解释​

  • 这些点最适合作为“全局协调中心/监控入口/枢纽选址”，因为它们到最远点的距离最小。

4.5 periphery —— 图边缘（最大离心率节点集合）​

功能说明​

边缘节点定义为离心率等于直径的节点：

periphery(G) = { v | eccentricity(v) == diameter(G) }

输出：边缘节点列表。

典型解释​

  • 这些点往往是“最偏远/最难覆盖”的位置，适合用于识别结构边界、孤立风险点、覆盖盲区。

4.6 wiener_index —— 维纳指数（全对距离总成本）​

功能说明​

维纳指数是 所有节点对 之间最短路距离的总和：

Wiener(G) = Σ(u<v) dist(u, v)

（或按 NetworkX 定义累计所有对）

它衡量：

  • 网络整体是否紧凑（距离和越小越紧凑）
  • 全局传播/追踪/协作的“距离成本”水平

参数要点​

  • weight（可选）：若提供，则按加权距离累计

复杂度​

  • 时间复杂度：O(V · (V + E))（本质需要大量最短路距离）

适用场景​

  • 不同网络结构的全局紧凑性对比
  • 交通/供应链/协作网络的总体路径成本评估

4.7 degree_assortativity_coefficient —— 度同配系数​

功能说明​

衡量“连接两端节点的度”是否相关（Pearson 相关系数的一种形式）：

  • r > 0：同配（高连接更爱连高连接）
  • r < 0：异配（高连接更爱连低连接，呈层级/中心辐射结构）
  • r ≈ 0：无明显偏好

参数要点​

  • 有向图可指定：
    • x：源端使用 in/out-degree（默认 out）
    • y：目标端使用 in/out-degree（默认 in）
  • weight（可选）：按边权累积度（度=邻接边权和）
  • nodes（可选）：限定子图节点集合计算（用于分群对比）

复杂度​

  • 时间复杂度：O(E)

适用场景​

  • 判断网络是否“核心-边缘”明显（常见为负同配）
  • 判断活跃账号是否“抱团”或“向外辐射”

4.8 attribute_assortativity_coefficient —— 属性同配系数​

功能说明​

衡量“相同属性的节点是否更倾向互连”：

  • r > 0：同质连接明显（同类型抱团）
  • r < 0：异质连接明显（跨类型连接更强）
  • r ≈ 0：属性对连接偏好影响弱

参数要点​

  • attribute（必填）：节点属性键（如 risk_level / account_type / department）
  • nodes（可选）：在指定节点子集上计算（例如只看某个社区/区域）

复杂度​

  • 时间复杂度：O(E)

适用场景​

  • 风险等级/账号类型是否“同类相连”
  • 医疗机构层级/科室属性是否“同级互联”
  • 组织结构是否“部门内连接为主”或“跨部门协作为主”

五、选型指南（怎么选）​

  • 想知道网络最大跨度：diameter
  • 想知道最佳中心的最坏距离：radius + center
  • 想找最偏远的边界节点：periphery（或看 eccentricity 最大）
  • 想对所有节点做“最坏可达距离”排名：eccentricity
  • 想看全局紧凑程度/距离成本：wiener_index
  • 想看是否“高活跃抱团/核心-边缘结构”：degree_assortativity_coefficient
  • 想看是否“同类型抱团/跨类型连接”：attribute_assortativity_coefficient

六、工程与使用注意事项（常见坑位）​

  1. 连通性要求
    直径/半径/中心/边缘/离心率等指标在“不可达”情形下会受影响。

    • 无向图：若非连通，通常需要先对每个连通分量分别计算或取最大连通分量
    • 有向图：可能需要考虑强连通分量或在可达子图上解释结果

  2. 加权距离的语义
    weight 表示“距离/成本/耗时”，应为正数；如果你的边权是“容量/相似度/强度”，不要直接当距离用（需要先做转换，如取倒数或取负对数等，且要保证正权）。

  3. 性能建议
    同一次分析里若同时要 eccentricity + diameter + radius + center + periphery：

    • 先计算 eccentricity（e），再传给其它指标复用
    • 无向图可尝试 usebounds=True（在 e 未预先提供时）