approximate_current_flow_betweenness_centrality#

approximate_current_flow_betweenness_centrality(G, normalized=True, weight=None, dtype=<class 'float'>, solver='full', epsilon=0.5, kmax=10000, seed=None)[source]#

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

在高概率下，近似计算绝对误差小于 epsilon 的当前流介数中心性 [1]。

参数:

G图: 一个 NetworkX 图
normalizedbool, 可选 (默认为 True): 如果为 True，介数值将除以 2/[(n-1)(n-2)] 进行归一化，其中 n 是图 G 中的节点数。
weightstring 或 None, 可选 (默认为 None): 用作边权重的边数据键。如果为 None，则每条边的权重为 1。权重反映了边的容量或强度。
dtype数据类型 (float): 内部矩阵的默认数据类型。设置为 np.float32 可降低内存消耗。
solverstring (默认为 ‘full’): 用于计算流矩阵的线性求解器类型。选项包括 “full”（占用内存最多）、“lu”（推荐）和 “cg”（占用内存最少）。
epsilon: float: 绝对误差容忍度。
kmax: int: 用于近似计算的最大采样节点对数。
seedinteger, random_state, 或 None (默认): 随机数生成状态的指示器。参见随机性。

返回:

nodes字典: 以介数中心性作为值的节点字典。

另见

current_flow_betweenness_centrality

注意

对于 \(n\) 个节点和 \(m\) 条边，运行时间为 \(O((1/\epsilon^2)m{\sqrt k} \log n)\)，所需空间为 \(O(m)\)。

如果边具有 ‘weight’ 属性，则将在此算法中用作权重。未指定的权重设置为 1。

参考文献

[1]

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