current_flow_betweenness_centrality

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

计算节点的当前流介数中心性。

当前流介数中心性使用电流模型表示信息传播，这与使用最短路径的介数中心性不同。

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

参数:

G图

一个 NetworkX 图

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

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

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

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

dtype数据类型 (float)

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

solver字符串 (默认为 ‘full’)

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

返回:

nodes字典

节点及其介数中心性值组成的字典。

另请参阅

approximate_current_flow_betweenness_centrality

betweenness_centrality

edge_betweenness_centrality

edge_current_flow_betweenness_centrality

备注

当前流介数可以在 \(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。

参考文献

[1]

基于当前流的中心性度量。Ulrik Brandes 和 Daniel Fleischer, Proc. 22nd Symp. Theoretical Aspects of Computer Science (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, Social Networks 27, 39-54 (2005)。