betweenness_centrality_subset

betweenness_centrality_subset(G, sources, targets, normalized=False, weight=None)

计算节点子集的介数中心性。

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

其中 \(S\) 是源节点的集合，\(T\) 是目标节点的集合，\(\sigma(s, t)\) 是 \((s, t)\)-最短路径的数量，并且 \(\sigma(s, t|v)\) 是那些经过节点 \(v\)（非 \(s, t\)）的最短路径的数量。如果 \(s = t\)，则 \(\sigma(s, t) = 1\)；如果 \(v \in {s, t}\)，则 \(\sigma(s, t|v) = 0\) [2]。

参数:

G图

一个 NetworkX 图。

sources: 节点列表

在计算介数中心性时用作最短路径源节点的节点

targets: 节点列表

在计算介数中心性时用作最短路径目标节点的节点

normalizedbool，可选

如果为 True，则介数中心性值会进行归一化，对于无向图，归一化因子为 \(2/((n-1)(n-2))\)；对于有向图，归一化因子为 \(1/((n-1)(n-2))\)，其中 \(n\) 是图 G 中的节点数量。

weightNone 或 string，可选 (默认=None)

如果为 None，所有边的权重被视为相等。否则，它表示用作权重的边属性名称。权重用于计算加权最短路径，因此被解释为距离。

返回值:

nodes字典

一个字典，键为节点，值为其介数中心性。

另请参阅

edge_betweenness_centrality

load_centrality

说明

基本算法来自 [1]。

对于加权图，边的权重必须大于零。零权重边可能导致节点对之间存在无限数量的等长路径。

归一化可能看起来有点奇怪，但其目的是为了使 betweenness_centrality(G) 的结果与 betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()) 的结果一致。

对于有向图和无向图，源节点和目标节点之间的总路径数计算方式不同。有向路径易于计数。无向路径比较棘手：从“u”到“v”的路径应该算作 1 条无向路径还是 2 条有向路径？

对于 betweenness_centrality，当 G 是无向图时，我们报告无向路径的数量。

对于 betweenness_centrality_subset，报告方式不同。如果源节点子集和目标节点子集相同，则我们希望计算无向路径。但如果源节点子集和目标节点子集不同——例如，sources 是 {0} 而 targets 是 {1}，那么我们只计算一个方向的路径。它们是无向路径，但我们以有向方式计算它们。要将它们算作无向路径，每条路径应计为半条路径。

参考文献

[1]

Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001. https://doi.org/10.1080/0022250X.2001.9990249

[2]

Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. https://doi.org/10.1016/j.socnet.2007.11.001