中间性中心度（中心度度量）

如果我们想找到一个节点，它被用作连接图的一个部分到另一个部分的桥梁，那么我们可以使用中间性中心度。中间性中心度可以用于图论，以便我们能够基于最短路径来衡量中心度。换句话说，我们可以说它用于图中，以便计算所有节点对之间的非加权最短路径。如果节点频繁地出现在其他节点之间的最短路径上，那么这些节点将具有更高的中间性中心度得分。

在一个连通图中，任意一对顶点之间必须至少有一条最短路径，通过这条路径我们可以最小化边的权重之和（仅在加权图中可行）或路径经过的边的数量（仅在非加权图中可行）。对于每个顶点，中间性中心度可以描述为通过该顶点/节点的最短路径的数量。

在网络理论中，中间性中心度有广泛的应用，即它能够表示节点在彼此之间所处的程度。例如，我们可以将其用于电信网络。如果一个节点具有较高的中间性中心度，那么该节点将对网络拥有更多控制权。因此，我们可以借助该节点传递更多信息。中间性可以作为中心度的一个通用度量推导出来，即在网络理论中，我们可以将其应用于广泛的问题，如交通问题、社交网络问题、科学合作问题和生物学问题。

定义

下面的表达式用于描述节点 v 的中间性中心度。

这里 用于表示从节点 s 到节点 t 的最短路径总数。

用于表示经过 v 的那些路径的数量。

我们可以通过节点对的数量将节点缩放到中间性中心度，这可以通过求和索引来暗示。我们还可以通过除以不包含 v 的节点对的数量来重新缩放计算，例如 g ∈ [0, 1]。在有向图中，使用以下公式进行除法

在无向图中，使用以下公式进行除法

这里 N 用于表示巨大连通分量中的节点数。

注意：我们可以将任何节点缩放到最高的可能值，其中该节点必须通过每条最短路径。这种情况并不经常发生，我们可以进行归一化处理而不损失精度。

该公式将生成结果为

借助此公式，不会丢失精度，因为此公式始终会从较小的范围缩放到较大的范围。

加权网络

在加权网络中用于连接节点的链接不再被视为二元交互。这些节点根据其频率、容量、影响力等进行加权。这些因素将用于在拓扑效应之外为网络增加另一个维度。在加权网络中，我们可以通过加权相邻边的权重来找出任何节点的强度。执行此操作的语法描述如下

这里 a_ij 和 w_ij 分别是节点 i 和 j 之间的邻接矩阵和加权矩阵。在无标度网络中，我们可以找到与度数的幂律分布类似的分布。给定节点的强度也遵循幂律分布。

考虑和采样

中间性中心度的计算可能需要大量资源。单源最短路径（SSSP）可以通过 Brandes 的近似算法为一组源节点计算。如果所有节点都被选作源节点，该算法将产生额外结果。在此算法中，对于大型图，运行时间会非常长。因此，我们可以说，通过计算 SSSPs 来近似结果仅对一部分节点有用。此技术在 GDS 中将被称为采样。这里还有采样大小，即源节点集的大小。

假设我们有大型图并希望执行此算法。在这种情况下，我们必须考虑两件事，它们描述如下

1. 如果并行度更高，则会导致内存消耗更高。这是因为每个线程顺序执行源节点子集的单源最短路径（SSSPs）。在任何最坏情况下，单个 SSSP 都需要将整个图复制到内存中。
2. 如果采样大小更大，那么我们将能够获得更准确的结果，但执行过程将花费更长的时间。

采样策略

有很多由 Brandes 定义的选取源节点的策略。GDS 的实现基于某种随机度数选择策略。在此策略中，节点将根据其度数的概率进行选择。使用此策略的原因是，这类节点很可能出现在图中的许多最短路径上。这就是为什么该策略对中间性中心度得分有更高的贡献。