edge_current_flow_betweenness_centrality_subset

edge_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字典

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

另请参阅

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 和 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]

基于随机游走的介数中心性度量 (A measure of betweenness centrality based on random walks)，M. E. J. Newman，Social Networks 27, 39-54 (2005)。