current_flow_betweenness_centrality_subset

current_flow_betweenness_centrality_subset(G, sources, targets, normalized=True, weight=None, dtype=<class 'float'>, solver='lu')

计算节点子集的电流介数中心性。

电流介数中心性使用电流模型来模拟信息传播，这与使用最短路径的介数中心性形成对比。

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

参数:

G图

一个 NetworkX 图

sources: 节点列表

用作电流源的节点

targets: 节点列表

用作电流汇的节点

normalized布尔值，可选 (默认=True)

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

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

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

dtype: 数据类型 (float)

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

solver: 字符串 (默认=’lu’)

用于计算流矩阵的线性求解器类型。选项包括 “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]

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).