edge_current_flow_betweenness_centrality

edge_current_flow_betweenness_centrality(G, normalized=True, weight=None, dtype=<class 'float'>, solver='full')

计算边的电流介数中心性。

电流介数中心性使用电流模型来模拟信息传播，与使用最短路径的介数中心性不同。

电流介数中心性也被称为随机游走介数中心性 [2]。

Parameters:

G图

一个 NetworkX 图

normalizedbool, 可选 (默认=True)

如果为 True，介数值通过 2/[(n-1)(n-2)] 进行归一化，其中 n 是图 G 中的节点数。

weightstring 或 None, 可选 (默认=None)

用作边权重的边数据键。 如果为 None，则每条边的权重为 1。 权重反映了边的容量或强度。

dtype数据类型 (默认=float)

内部矩阵的默认数据类型。 设置为 np.float32 以降低内存消耗。

solverstring (默认=’full’)

用于计算流矩阵的线性求解器类型。 选项有 “full”（使用最多内存），”lu”（推荐），和 “cg”（使用最少内存）。

Returns:

nodes字典

包含边元组及其介数中心性值的字典。

Raises:

NetworkXError

该算法不支持有向图。 如果输入图是 DiGraph 类的实例，则引发 NetworkXError。

See also

betweenness_centrality

edge_betweenness_centrality

current_flow_betweenness_centrality

Notes

电流介数可以在 \(O(I(n-1)+mn \log n)\) 时间内计算 [1]，其中 \(I(n-1)\) 是计算逆拉普拉斯矩阵所需的时间。对于完整矩阵，这是 \(O(n^3)\)，但使用稀疏方法可以实现 \(O(nm{\sqrt k})\)，其中 \(k\) 是拉普拉斯矩阵的条件数。

所需空间为 \(O(nw)\)，其中 \(w\) 是稀疏拉普拉斯矩阵的宽度。最坏情况下是 \(w=n\)，即 \(O(n^2)\)。

如果边具有 ‘weight’ 属性，它们将在此算法中用作权重。未指定的权重设置为 1。

References

[1]

基于电流的中心性度量。 Ulrik Brandes 和 Daniel Fleischer, 第22届计算机科学理论研讨会 (STACS ‘05) 论文集。 LNCS 3404, pp. 533-544. Springer-Verlag, 2005. https://doi.org/10.1007/978-3-540-31856-9_44

[2]

基于随机游走的介数中心性度量， M. E. J. Newman, 社会网络 27, 39-54 (2005).