prominent_group

prominent_group(G, k, weight=None, C=None, endpoints=False, normalized=True, greedy=False)

找到图 \(G\) 中大小为 \(k\) 的显著群组。群组的显著性通过群组介数中心性评估。

节点群组 \(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图

一个 NetworkX 图。

kint

群组中的节点数量。

normalizedbool, 可选 (默认=True)

如果为 True，群组介数通过 1/((|V|-|C|)(|V|-|C|-1)) 进行归一化，其中 |V| 是 G 中的节点总数，|C| 是 C 中的节点数量。

weightNone 或 string, 可选 (默认=None)

如果为 None，则所有边的权重被视为相等。否则，表示用作权重的边属性的名称。边的权重被视为两端之间的长度或距离。

endpointsbool, 可选 (默认=False)

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

Clist 或 set, 可选 (默认=None)

不会成为显著群组候选者的节点列表。

greedybool, 可选 (默认=False)

使用朴素贪婪算法寻找非最优的显著群组。对于无标度网络，结果与最优结果的差异微不足道。

返回值:

max_GBCfloat

显著群组的群组介数中心性。

max_grouplist

显著群组中的节点列表。

抛出异常:

NodeNotFound

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

另见

betweenness_centrality, group_betweenness_centrality

注释

群组介数中心性在 [1] 中有描述，其重要性在 [3] 中进行了讨论。算法在 [2] 中有描述，并基于 [4] 中提到的技术。

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

对于加权图，边的权重必须大于零。零边权重可能在节点对之间产生无限多条等长路径。

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

参考文献

[1]

M G Everett 和 S P Borgatti: 群组和类别的中心性. Journal of Mathematical Sociology. 23(3): 181-201. 1999. http://www.analytictech.com/borgatti/group_centrality.htm

[2]

Rami Puzis, Yuval Elovici 和 Shlomi Dolev: “在复杂网络中寻找最显著的群组” AI communications 20(4): 287-296, 2007. https://www.researchgate.net/profile/Rami_Puzis2/publication/220308855

[3]

Sourav Medya 等: 通过网络设计最大化群组中心性. SIAM International Conference on Data Mining, SDM 2018, 126–134. https://sites.cs.ucsb.edu/~arlei/pubs/sdm18.pdf

[4]

Rami Puzis, Yuval Elovici 和 Shlomi Dolev. “连续计算群组介数中心性的快速算法。” https://journals.aps.org/pre/pdf/10.1103/PhysRevE.76.056709