Spring_layout不能正确处理权重

spring_layout 实现了Fruchterman-Reingold算法,该算法将图建模为节点相互排斥的系统。排斥力被放置在连接节点之间的弹簧抵消。

networkx中的实现存在一些问题,特别是排斥项。这在您的示例图中很明显,其中节点3永远不应该位于中心,因为它是连接最少的节点。

然而,你的主要不满是吸引力条款。基本上,你定义了克服任何排斥项的极强弹簧。因此,节点都聚集在一个点上。当networkx返回这些基本上随机的位置时,这些位置会被重新缩放到由 scale 和 center 参数。

通过将权重平均值归一化,可以在一定程度上改善你的问题:

然而,请注意,即使(2,4)和(1,2)的权重非常大,边(1,4)的小权重(即1和4之间的排斥>吸引)也会阻止节点1和4靠近节点2。换句话说,由此产生的布局也受到三角不等式的约束,任何归一化都不可能改变这一点。因此, 弹簧布局 一般来说,将无法反映所有权重(权重为实际几何距离的树和图除外)。

#!/usr/bin/env python
"""
https://stackoverflow.com/q/67116565/2912349
"""
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

if __name__ == '__main__':

    edge_weights = {
        (1, 2) : 7_000_000_000,
        (2, 3) : 700_000,
        (1, 4) : 1_000_000,
        (2, 4) : 5_000_000_000,
    }

    G1 = nx.Graph([(source, target, {'weight' : w}) for (source, target), w in edge_weights.items()])
    pos1 = nx.spring_layout(G1)

    mean = np.mean(list(edge_weights.values()))
    G2 = nx.Graph([(source, target, {'weight' : w / mean}) for (source, target), w in edge_weights.items()])
    pos2 = nx.spring_layout(G2)

    fig, (ax1, ax2) = plt.subplots(1, 2)
    nx.draw_networkx(G1, pos1, ax=ax1)
    nx.draw_networkx(G2, pos2, ax=ax2)
    ax1.set_title('Raw')
    ax2.set_title('Normalized')
    ax1.axis('off')
    ax2.axis('off')

    plt.show()