介数中心性#
- betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None)[源代码]#
计算节点的基于最短路径的介数中心性。
节点 \(v\) 的介数中心性是所有节点对之间通过 \(v\) 的最短路径比例之和
\[c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}\]其中 \(V\) 是节点集合，\(\sigma(s, t)\) 是 \(s\) 和 \(t\) 之间的最短路径数量，\(\sigma(s, t|v)\) 是那些经过节点 \(v\) 的最短路径数量（其中 \(v\) 不是 \(s\) 或 \(t\)）。如果 \(s = t\)，则 \(\sigma(s, t) = 1\)；如果 \(v \in {s, t}\)，则 \(\sigma(s, t|v) = 0\) [2]。
- 参数：
- G图
一个 NetworkX 图。
- kint, 可选 (默认=None)
如果 k 不是 None，则使用 k 个节点样本来估计介数。k 的值必须小于等于图中的节点数 n。值越大，近似效果越好。
- normalizedbool, 可选
如果为 True，对于无向图，介数值将除以
2/((n-1)(n-2))进行归一化；对于有向图，介数值将除以1/((n-1)(n-2))进行归一化，其中n是图 G 中的节点数。- weightNone 或 string, 可选 (默认=None)
如果为 None，则所有边的权重被视为相等。否则，它表示用作权重的边属性的名称。权重用于计算加权最短路径，因此它们被解释为距离。
- endpointsbool, 可选
如果为 True，则在最短路径计数中包含端点。
- seedinteger, random_state, 或 None (默认)
随机数生成状态的指示器。参见随机性。请注意，这仅在 k 不是 None 时使用。
- 返回：
- nodes字典
节点的字典，其值是介数中心性。
注意
该算法来自 Ulrik Brandes [1]。关于最初发布的版本详见 [4]，关于变体和相关度量的算法详情详见 [2]。
对于近似介数计算，将 k 设置为 #样本，使用 k 个节点（“枢轴”）来估计介数值。关于所需枢轴数量的估计，请参见 [3]。
对于加权图，边的权重必须大于零。零权重边可能会在节点对之间产生无限数量的等长路径。
对于有向图和无向图，源节点和目标节点之间的路径总数计算方式不同。有向路径很容易计算。无向路径比较复杂：从“u”到“v”的路径应该算作 1 条无向路径还是 2 条有向路径？
对于 betweenness_centrality 函数，当 G 是无向图时，我们报告无向路径的数量。
对于 betweenness_centrality_subset 函数，报告方式不同。如果源子集和目标子集相同，则我们希望计算无向路径。但如果源子集和目标子集不同——例如，如果 sources 是 {0}，targets 是 {1}，那么我们只计算一个方向的路径。它们是无向路径，但我们以有向的方式计算它们。为了将它们算作无向路径，每条路径应计算为半条路径。
如果边的权重是浮点数，该算法不能保证正确性。一种变通方法是，可以将相关的边属性乘以一个合适的常数因子（例如 100）并转换为整数，从而使用整数权重。
参考文献
[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] (1,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
[3]Ulrik Brandes and Christian Pich: Centrality Estimation in Large Networks. International Journal of Bifurcation and Chaos 17(7):2303-2318, 2007. https://dx.doi.org/10.1142/S0218127407018403
[4]Linton C. Freeman: A set of measures of centrality based on betweenness. Sociometry 40: 35–41, 1977 https://doi.org/10.2307/3033543