group_betweenness_centrality#

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

计算一组节点之间的群中心度。

一组结点的组间中心性 \(C\) 中所有通过顶点的最短路径的分数之和。 \(C\)

\[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|C)\) 是经过组中某个节点的那些路径的数目 \(C\) 。请注意, \((s, t)\) 不是该组的成员 (\(V-C\) 是中的节点集 \(V\) 不在其中的 \(C\) )。

参数
G图表

网络X图。

C列表或集合或列表或集合列表

包含属于G的节点的组或组的列表,要为其计算组的介数中心度。

normalized布尔值,可选(默认值=True)

如果为True,则按以下方式归一化组之间 1/((|V|-|C|)(|V|-|C|-1)) 哪里 |V| 是G和G中的节点数 |C| 是C中的节点数。

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

如果没有,则所有边权重被视为相等。否则,保留用作权重的边属性的名称。边的权重被视为两边之间的长度或距离。

endpoints布尔值,可选(默认值=FALSE)

如果为True,则将最短路径中的终结点包括在内。

返回
betweenness浮点数或浮点数列表

如果C是一个单独的组,则返回一个浮点数。如果C是具有多个组的列表,则返回组居间中心性的列表。

加薪
NodeNotFound

如果C中的节点不在G中。

笔记

中描述了组之间的中心性 [1] 以及它的重要性在 [3]. 中提到了该算法的初始实现 [2]. 此函数使用中提出的改进算法 [4].

组中的节点数必须最大为N 2。 n 是图表中的节点总数。

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

对于有向图和无向图,源和目标之间的路径总数计算方式不同。“u”和“v”之间的有向路径被计为两条可能的路径(每个方向一个),而“u”和“v”之间的无向路径被计为一条路径。换句话说,上面表达式中的总和就是全部。 s != t 对于有向图和对于 s < t 用于无向图。

工具书类

1

M G Everett和S P Borgatti:群和类的中心性。数学社会学杂志。23(3):181-201。1999年。http://www.analytictech.com/borgatti/group_centrality.htm

2

Ulrik Brandes:关于最短路径在中心性和它们的一般计算之间的变化。社交网络30(2):136-1452008。http://citeserx.ist.psu.edu/viewdoc/下载?doi=10.1.1.72.9610&rep=rep1&type=pdf

3

来源于网络设计的群体中心最大化。暹罗国际数据挖掘会议,SDM 2018,126–134。https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf

4

拉米·普齐斯、尤瓦尔·埃洛维奇和什洛米·多列夫。“连续计算群居中中心度的快速算法。”Https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709