介数中心性 (BC)#

介数中心性是一种基于衡量经过每个顶点或每条边的最短路径数量来衡量相对重要性的指标。介数中心性较高的顶点会有更多的最短路径穿过该顶点。同样，介数中心性较高的边会有更多的最短路径经过该边。

有关算法的更多详细信息，请参阅 维基百科上的介数中心性。

节点 𝑣 的介数中心性是所有经过 𝑣 的点对最短路径比例之和

\[ c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)} \]

何时使用 BC#

介数中心性常用于回答以下问题：

  • 网络中哪些顶点最具影响力？

  • 网络中的桥接顶点是什么？

  • 网络有多健壮/冗余？

  • 在社交网络分析中，介数中心性可用于识别组织中的角色。

何时不使用 BC#

在某些情况下，介数中心性的效率较低

  • 对于大型图，由于计算成本增加，可能需要近似计算介数中心性。

  • 不连通的网络或包含许多孤立组件的网络会限制介数中心性的价值

  • 在加权图中，介数中心性成本更高且不太有用。

  • 在具有层级结构的网络中，BC 可能无法准确反映真实影响力

  • 具有多种边类型的网络通常需要针对每种边类型采用单独的方法来衡量影响力。

BC 的计算成本有多高？#

尽管 cuGraph 的并行性降低了运行时间，但 大 O 表示法 (Big O notation) 仍是比较算法成本的标准。

  • 对于非加权图，成本为 O(V(E+V))；对于加权图，成本为 O(V(E+V)log(V))。

  • 在计算 BC 之前，会进行广度优先搜索以确定所有节点之间的最短路径。

样本基准测试#

即将推出

Copyright (c) 2023-2025, NVIDIA CORPORATION.

根据 Apache 许可证 2.0 版（“许可证”）的授权，除非遵守许可证，否则您不得使用此文件。您可以在 https://apache.ac.cn/licenses/LICENSE-2.0 获取许可证的副本

除非适用法律要求或书面同意，根据本许可证分发的软件均按“原样”提供，不附带任何明示或默示的担保或条件。有关许可证下特定语言管理权限和限制，请参阅许可证。