current_flow_betweenness_centrality

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 中的节点数。

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

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

dtype数据类型 (float)

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

solver字符串 (默认=’full’)

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

Returns:

nodes字典

包含节点及其介数中心性值的字典。

See also

approximate_current_flow_betweenness_centrality

betweenness_centrality

edge_betweenness_centrality

edge_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, 第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)。