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图表

网络X图。

sources: list of nodes

用作中间最短路径的源的节点

targets: list of nodes

用作中间最短路径的目标的节点

normalized布尔值,可选

如果为True,则介数值通过以下方式标准化 \(2/((n-1)(n-2))\) 对于图形,和 \(1/((n-1)(n-2))\) 对于有向图,其中 \(n\) 是G中的节点数。

weight无或字符串,可选(默认值=无)

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

返回
nodes词典

以介数中心度为值的节点字典。

笔记

基本算法来自于 [1].

对于加权图,边权重必须大于零。零边缘权重可以在节点对之间生成无限多的等长路径。

规范化可能看起来有点奇怪,但它的目的是使中间性(g)与中间性子集(g,sources=g.nodes(),targets=g.nodes())相同。

对于有向图和无向图,源和目标之间的路径总数是不同的。有向路径很容易计数。无向路径很棘手:从“u”到“v”的路径应该算作1个无向路径还是2个有向路径?

对于中间性,当g是无向时,我们报告无向路径的数目。

对于中间性子集,报告是不同的。如果源和目标子集是相同的,那么我们要计算无向路径。但是如果源和目标子集不同——例如,如果源是{0},目标是{1},那么我们只计算一个方向的路径。它们是无向的路径,但我们以有向的方式计算它们。若要将它们计为无向路径,则每个路径应计为半条路径。

工具书类

1

Ulrik Brandes,一种更快的中间度中心性算法。《数学社会学学报》第25卷第2期:163-177,2001。Https://doi.org/10.1080/0022250X.2001.9990249

2

Ulrik Brandes:关于最短路径、中间性、中心性及其一般计算的变体。社交网络30(2):136-145,2008。Https://doi.org/10.1016/j.socnet.2007.11.001