代码之家 › 专栏 › 技术社区 › Felipe Augusto Ak S

Spring_layout不能正确处理权重

networkx graph python

Felipe Augusto Ak S · 技术社区 · 3 年前

我试图使用权重来定义节点之间的距离,但它不起作用。我甚至试图使用归一化值,但都没有成功。

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

这是我得到的结果,正如你所看到的,即使值非常不同,节点也非常接近:

0 回复 | 直到 3 年前

Paul Brodersen 3 年前

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