Networkx最小生成树 - 精度问题？

我从222 x 222节点大小的加权邻接矩阵创建图。矩阵中给出的所有权重均为0.42757498546089029和1.6671726002927263之间的浮点数。 nx.minimum_spanning_tree(G, weight = "weight")方法给了我下面的第一张图片，同时如果我乘以所有矩阵值100.0同样的方法给了我第二张图片。在与igraph一样绘图时不会发生这种情况。 Networkx的文档没有提到精确性问题。你知道它为什么会发生吗？ Networkx最小生成树 - 精度问题？

networkx代码：

G=nx.from_numpy_matrix(M) 
G1=nx.minimum_spanning_tree(G, weight = "weight") 

labels = {i : node_names[i][1] for i in G1.nodes()} 
colors = {i : node_attributes[labels[i]] for i in G1.nodes()} 
for i in G1.nodes(): 
    G1.node[i]["color"] = 'white' 
    G1.node[i]["style"] = "filled"  
    G1.node[i]["fillcolor"] = colors[i] 
color=nx.get_node_attributes(G1,'color') 
fillcolor=nx.get_node_attributes(G1,'fillcolor') 
H=nx.relabel_nodes(G1,labels) 
nx.draw(H, scale=30, nodelist=H.nodes(), linewidths=0, with_labels = True, node_size=500,font_size=8)

的igraph代码：

g = igraph.Graph.Weighted_Adjacency(M.tolist()) 
    for i, v in enumerate(g.vs): 
     v["color"] = colors[i] 
     v["label"] = labels[i] 
     v["frame_color"] = colors[i] 
     v["label_size"] = 10 
     v["size"] = 26 
    G = g.spanning_tree(weights='weight', return_tree=True) 
    G.to_undirected() 
    igraph.plot(G, labels=False, bbox = (900, 900), margin=40, loops=False 

)

来源

2017-04-02 Leukonoe

这些算法使用Python浮点数并继承这些操作的精度（根据https://docs.python.org/3/tutorial/floatingpoint.html，浮点数为53位） – Aric

也许你可以发表一个例子所以我们可以看到问题是什么？ – Aric

你确定树木不同吗？我相信只有布局不同，但拓扑结构是相同的，至少乍一看。 – DyZ

-1

你看到的是预期的行为，而不是一个精确的问题都没有。顾名思义，弹簧布局“模拟”节点之间弹簧的作用到其位置上。节点位置在一个圆上初始化，然后将弹簧的力施加到您的节点进行一定次数的迭代（默认为50）。由于连接权重较弱，节点或多或少会保留在圆圈上（第一种情况），强大的节点会将节点吸引到中心（第二种情况）。

在igraph中，默认情况下，未加权图用于计算布局，并且需要明确给绘图例程权重。我怀疑你可能没有指定“权重”参数而绘制了图表。

来源

2017-04-03 09:10:22 Paul

为什么你怀疑我为igraph绘制了没有重量的图？ networkx的答案是正确的，可以看到networkx使用spring作为默认布局。但igraph默认情况下不使用弹簧。 – Leukonoe

关于权重参数的设置：只是一个猜测。关于默认布局：igraph默认使用Kamada-Kawei作为小图，而Fruchterman-Reingold（又名春天布局）用于更大的图。 IIRC，截止约1000个节点。 – Paul

好的，所以igraph使用spring布局，并且权重被指定为'G = g.spanning_tree（weights ='weight'，return_tree = True）'所以我认为我给了igraph MST的权重。虽然为什么然后'G.is_weighted（）'返回'False'？是否有可能确实没有考虑权数？ – Leukonoe

Networkx最小生成树 - 精度问题？

回答

相关问题