group_betweenness_centrality#

group_betweenness_centrality(G, C, normalized=True, weight=None, endpoints=False)[source]#

计算一组节点的组介数中心性。

节点组 $C$ 的组介数中心性是所有全对最短路径中经过 $C$ 中任一顶点的路径所占分数的总和

c_{B} (v) = \sum_{s, t \in V} \frac{σ (s, t | v)}{σ (s, t)}

其中 $V$ 是节点集合， $σ (s, t)$ 是最短 $(s, t)$ -路径的数量，而 $σ (s, t | C)$ 是这些路径中经过组 $C$ 中某些节点的路径数量。注意 $(s, t)$ 不属于该组（ $V - C$ 是 $V$ 中不属于 $C$ 的节点集合）。

参数:

G图: 一个 NetworkX 图。
Clist 或 set 或 list of lists 或 list of sets: 要计算组介数中心性的一组或多组包含属于 G 的节点的集合。
normalizedbool, 可选 (默认为 True): 如果为 True，组介数将通过 1/((|V|-|C|)(|V|-|C|-1)) 进行归一化，其中 |V| 是图 G 中的节点总数，|C| 是组 C 中的节点数。
weightNone 或 string, 可选 (默认为 None): 如果为 None，所有边的权重均被视为相等。否则，它保存用作权重的边属性的名称。边的权重被视为两端之间的长度或距离。
endpointsbool, 可选 (默认为 False): 如果为 True，在最短路径计数中包含端点。

返回:

betweennesslist of floats 或 float: 如果 C 是单个组，则返回一个浮点数。如果 C 是包含多个组的列表，则返回一个组介数中心性列表。

引发:

NodeNotFound: 如果 C 中的节点不存在于 G 中。

另请参阅

betweenness_centrality

注意

组介数中心性在 [1] 中有所描述，其重要性在 [3] 中有所讨论。该算法的初步实现见于 [2]。此函数使用了 [4] 中提出的改进算法。

组中的节点数最多为 n - 2，其中 n 是图中的节点总数。

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

对于有向图和无向图，源节点和目标节点之间的总路径数量的计数方式不同。有向图中“u”和“v”之间的有向路径被视为两条可能的路径（每个方向一条），而无向图中“u”和“v”之间的无向路径被视为一条路径。换句话说，上面的表达式中的求和对于有向图是针对所有 s != t 进行，而对于无向图是针对所有 s < t 进行。

参考

[1]

M G Everett and S P Borgatti: The Centrality of Groups and Classes. Journal of Mathematical Sociology. 23(3): 181-201. 1999. http://www.analytictech.com/borgatti/group_centrality.htm

[2]

Ulrik Brandes: On Variants of Shortest-Path Betweenness Centrality and their Generic Computation. Social Networks 30(2):136-145, 2008. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.9610&rep=rep1&type=pdf

[3]

Sourav Medya et. al.: Group Centrality Maximization via Network Design. SIAM International Conference on Data Mining, SDM 2018, 126–134. https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf

[4]

Rami Puzis, Yuval Elovici, and Shlomi Dolev. “Fast algorithm for successive computation of group betweenness centrality.” https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709