Skip to content
返回搜索结果

加权介数中心性

提出者
Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
年份
2010
类型
Centrality measure (path-based)
类别
Network science

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

加权介数中心性将弗里曼的介数度量扩展到边加权图,通过可调的边权重变换来路由最短路径。位于许多高价值最短路径上的节点会获得高分,从而识别出在连接强度很重要的社交、生物和信息网络中的中介者和桥梁。

方法背后的直觉

想象一座城市,道路具有不同的交通容量。最有影响力的交叉口不仅是那些拥有许多道路的交叉口,而且是那些位于许多地点对之间最快或容量最大的路线上的交叉口。加权介数中心性正是捕捉了这一点:它找到了充当关键中继点的节点,并考虑了经过它们的连接的强度或弱度。一个具有高加权介数的节点是一个桥梁或看门人,它的移除会破坏许多强大的路径。

历史学

介数中心性由 Linton Freeman 于 1977 年引入,作为衡量节点通过最短路径连接他人的作用的度量。Ulrik Brandes 于 2001 年开发了一种里程碑式的有效算法,将无权重图的计算复杂度从 O(n^3) 降低到 O(n + m)。加权扩展由 Opsahl、Agneessens 和 Skvoretz 于 2010 年系统地形式化,他们提出了参数化 alpha 的权重到距离的变换,并针对经验合作网络和航空网络进行了验证。

何时使用

当边权重代表有意义的连接强度(接触频率、流量、合作强度、相似性)并且您想识别网络中的中介者、看门人或单点故障时,请使用加权介数中心性。它适用于社交网络、合作网络、交通网格和生物通路,其中连接的强度决定了实际使用的路径。当边权重嘈杂或任意时,请避免使用它——在这种情况下,普通的介数中心性更安全。此外,对于没有近似算法的非常大的网络(数百万个节点),也应避免使用它,因为在最坏的情况下,精确计算的复杂度为 O(n^3)。

局限与注意事项

  • 对于密集图,精确计算的空间和时间复杂度为 O(n^3),限制了其在大规模网络上的可扩展性。
  • 结果对 alpha 的选择敏感;不同的值可能显著改变节点的排名。
  • 假设信息或影响仅沿测地线(最短)路径流动,这可能无法反映真实的扩散过程。
  • 负或零边权重需要特殊处理,并可能破坏最短路径算法。
  • 断开连接的网络会导致不同组件中的节点对的介数未定义,需要进行组件级分析。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 在连接强度决定首选路径的网络中捕捉中介和控制作用。
  • alpha 调优参数允许分析人员混合无权重和全权重路径逻辑,使度量具有适应性。
  • 直接识别瓶颈节点,其移除将导致网络碎片化或减速。
  • 与 Brandes 的高效算法兼容,使得对于拥有数万个节点的网络进行计算是可行的。
  • 标准化得分在不同大小的网络之间具有可解释性。
  • 基于同行评审的通用化框架(Opsahl 等人,2010 年)有广泛引用,基础扎实。

应用

  • 识别组织和合作网络中的知识中介者和边界跨越者。
  • 在通信或供应链网络中定位关键中继节点以进行弹性分析。
  • 在交通网络中寻找承载最多城际交通的枢纽机场或中转站。
  • 在蛋白质相互作用或基因调控网络中检测调控瓶颈。
  • 在加权流行病或信息传播模型中找出有影响力的传播者。
  • 在加权合著和引文网络中进行社区级别中介分析。

使用方式

使用方式

1

使用由调优参数 alpha 控制的逆变换将边权重转换为距离。当 alpha 等于零时,度量简化为标准的无权重介数;当 alpha 增加到一(接近一)时,较强的连接被视为较短的路径,因此是首选路径,这使得度量对连接强度敏感。

公式
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]
2

Dijkstra 算法(或为了效率的 Brandes 线性代数变体)使用变换后的距离,计算网络中每对源节点和目标节点之间的最短加权路径集。此步骤确定了在给定的权重配置下,哪些路径在测地线上是最优的。

3

对于每对有序节点,算法计算最短加权路径的总数以及通过每个候选节点 v 的这些路径的子集。使用 Brandes 的反向传播技术可以有效地累积这些计数,从而使算法对于中等规模的网络具有可处理性。

4

对于每个节点 v,原始介数得分是所有源-目标对的最短路径中通过 v 的比例的总和。位于一对节点之间所有最短路径上的节点,为该对贡献 1.0 分;被所有路径绕过的节点贡献 0 分。

公式
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}
5

原始得分除以最大可能值——对于无向网络是 (n-1)(n-2)/2 —— 使得分落在 [0, 1] 范围内,并且可以跨不同大小的网络进行比较。对于有向网络,分母加倍为 (n-1)(n-2)。

公式
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

常见陷阱

  • 使用默认的 alpha 值而不报告或论证其值——始终说明并论证您的 alpha 选择。
  • 将原始(未标准化)得分视为可跨不同大小网络进行比较。
  • 忽略有向网络中的边方向,而计算无向介数。
  • 将高介数解释为高影响力,而不考虑流是否实际遵循领域中的最短路径。
  • 忘记检查断开连接的组件,这会人为地降低小组件中节点的介数得分。

常见问题

如何选择 alpha 参数?

Alpha 控制权重对路径选择的影响程度。当 alpha=0 时,您得到经典的无权重介数;当 alpha=1 时,较强的连接完全定义了最短路径。一种常见的做法是测试 alpha=0、0.5 和 1,并报告敏感性。如果节点排名在不同值之间保持稳定,则任何选择都是合理的;如果存在显著差异,则应根据强连接是否应被优先考虑来从理论上论证您的选择。

加权介数中心性与无权重介数中心性有何区别?

无权重介数计算跳数;每条边长度相同。加权介数使用边权重(转换为距离),以便路径优先遵循较强的或较短的连接。在连接强度具有实质性意义的网络中——例如合作频率或贸易量——加权版本能更准确地描绘控制实际流动的节点。

加权介数中心性是否适用于非常大的网络?

精确计算在节点数超过约 100,000 个时会变得昂贵。对于非常大的网络,请使用近似算法,例如随机枢轴采样(在 NetworkX 中通过 k 参数实现 betweenness_centrality)或利用 GPU 加速工具(如 cuGraph)。报告您使用的是精确计算还是近似计算。

我的网络有孤立节点或多个组件时,可以使用加权介数中心性吗?

可以,但孤立节点的分数将始终为零,小组件中节点的得分仅基于其组件内的路径。如果您想获得组件内的排名,请为每个组件单独计算介数,并与得分一起报告组件结构。

在论文中应如何报告加权介数中心性?

报告使用的软件和版本(例如,NetworkX、igraph),alpha 值,得分是否已标准化,如何处理断开连接的组件,以及除了排名靠前的节点之外的汇总统计数据(平均值、范围)。度数与介数的散点图或节点大小与其得分成比例的网络可视化有助于理解。

相关方法

参考文献

  1. Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.

    打开 DOI 文献
    已复制。
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    打开 DOI 文献
    已复制。