Spring_layout 不能正确处理权重

Question

我正在尝试使用权重来定义节点之间的距离，但它不起作用。我什至尝试使用标准化值，但没有成功。

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()

raw_values = [(1,2, {'weight':70000000000}), (2,3,{'weight':700000}), 
                  (1,4,{'weight':1000000}), (2,4,{'weight':50000000000})]

normalized_values = []
for l in list1:
    norm_value = np.log10(l[2]['weight'])
    normalized_values.append((l[0], l[1], {'weight': norm_value}))

G.add_edges_from(raw_values)

pos = nx.spring_layout(G)

nx.draw_networkx(G,pos)
edge_labels = nx.draw_networkx_edge_labels(G, pos)

plt.show()

这是我得到的结果，您可以看到节点非常接近，尽管值非常不同：

Answer 1

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

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

但是，您主要不满的是吸引力术语。基本上，您定义了可以克服任何排斥项的极强弹簧。结果，节点都聚集在一个点上。当 networkx returns 这些本质上随机的位置时，这些位置将重新缩放到 scale 和 center 参数隐含的边界框。

您的问题可以通过均值归一化权重得到一定程度的改善：

但是请注意，边 (1, 4) 的权重较小（即排斥力 > 1 和 4 之间的吸引力）会阻止节点 1 和 4 靠近节点 2，即使 (2, 4) 的权重) 和 (1, 2) 非常大。换句话说，最终的布局也受到三角不等式的约束，并且没有规范化可能会改变这一点。因此，spring_layout 通常无法反映所有权重（权重是实际几何距离的树和图形除外）。

#!/usr/bin/env python
"""

"""
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()

Spring_layout 不能正确处理权重

Spring_layout doesn't works properly with weights

python

graph

networkx