betweenness_centrality

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]。

Parameters:

G图

一个 NetworkX 图。

k整数, 可选 (默认=None)

如果 k 不是 None，使用 k 个节点样本来估计介数。 k 的值应小于等于图中的节点数 n。 更高的值给出更好的近似。

normalized布尔值, 可选

如果为 True，介数值通过 2/((n-1)(n-2)) 归一化， 对于有向图，归一化因子为 1/((n-1)(n-2)) ，其中 n 是图 G 中的节点数。

weightNone 或 字符串, 可选 (默认=None)

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

endpoints布尔值, 可选

如果为 True，在最短路径计数中包括端点。

seed整数, random_state, 或 None (默认)

随机数生成状态的指示器。 参见 Randomness 。 注意，这仅在 k 不是 None 时使用。

Returns:

nodes字典

包含节点及其介数中心性值的字典。

See also

edge_betweenness_centrality

load_centrality

Notes

该算法来自 Ulrik Brandes [1]。 参见 [4] 获取最初发表的版本和 [2] 获取关于变体和相关度量算法的详细信息。

对于近似介数计算，设置 k=#samples 以使用 k 个节点（“枢纽”）来估计介数值。关于所需枢纽数量的估计，参见 [3]。

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

源和目标之间的总路径数在有向图和无向图中计算方式不同。有向路径的计数很简单。无向路径的计数较为复杂：从“u”到“v”的路径应计为 1 条无向路径还是 2 条有向路径？

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

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

如果边权重是浮点数，此算法不保证正确。作为一种解决方法，可以通过乘以一个方便的常数因子（例如 100）并将相关边属性转换为整数来使用整数。

References

[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

[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

---

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The parallel computation is implemented by dividing the nodes into chunks and computing betweenness centrality for each chunk concurrently.

Additional parameters:

get_chunksstr, function (default = “chunks”)

A function that takes in a list of all the nodes as input and returns an iterable node_chunks. The default chunking is done by slicing the nodes into n chunks, where n is the number of CPU cores.

[Source]