edge_current_flow_betweenness_centrality

edge_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”（使用最少内存）。

返回:

result字典

键为边元组，值为介数中心性的字典。

抛出:

NetworkXError

该算法不支持有向图（DiGraph）。如果输入图是 DiGraph 类的实例，则会抛出 NetworkXError。

另请参阅

betweenness_centrality

edge_betweenness_centrality

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]

Centrality Measures Based on Current Flow. Ulrik Brandes and 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]

A measure of betweenness centrality based on random walks, M. E. J. Newman, Social Networks 27, 39-54 (2005).