Networkx弹簧布局边缘配重 [英] Networkx spring layout edge weights

问题描述

我想知道spring_layout如何考虑边缘重量.在Wikipedia中，

I was wondering how spring_layout takes edge weight into account. From wikipedia,

'另一种模型考虑了每对节点(i，j)的类似于弹簧的力，其中每个弹簧的理想长度\ delta_ {ij}与节点i和j之间的图论距离成比例，而没有使用单独的排斥力.最小化欧氏距离和节点之间的理想距离之间的差异(通常是平方差异)等效于度量多维缩放问题.'

'An alternative model considers a spring-like force for every pair of nodes (i,j) where the ideal length \delta_{ij} of each spring is proportional to the graph-theoretic distance between nodes i and j, without using a separate repulsive force. Minimizing the difference (usually the squared difference) between Euclidean and ideal distances between nodes is then equivalent to a metric multidimensional scaling problem.'

具体如何计算边缘权重?

How is edge weight factored in, specifically?

推荐答案

这不是一个很好的答案，但它提供了基本知识.可能真正了解Fruchterman-Reingold算法并可以描述它的人可能来自其他人.我根据代码中的内容给出了解释.

This isn't a great answer, but it gives the basics. Someone else may come by who actually knows the Fruchterman-Reingold algorithm and can describe it. I'm giving an explanation based on what I can find in the code.

从文档 ，

weight:字符串或无可选(默认值="weight")

weight : string or None optional (default=’weight’)

edge属性，其中包含用于边缘权重的数值.如果为None，则所有边缘权重均为1.

The edge attribute that holds the numerical value used for the edge weight. If None, then all edge weights are 1.

但这并不能告诉您重量是做什么的，这是您的问题.

But that doesn't tell you what it does with the weight, which is your question.

您可以找到源代码.如果您发送加权边，它将使用这些权重创建邻接矩阵A并将A传递给_fruchterman_reingold.

You can find the source code. If you send in weighted edges, it will create an adjacency matrix A with those weights and pass A to _fruchterman_reingold.

看那里的代码，它的内容就在这一行 displacement=np.transpose(np.transpose(delta)*\ (k*k/distance**2-A*distance/k))\ .sum(axis=1)

Looking at the code there, the meat of it is in this line displacement=np.transpose(np.transpose(delta)*\ (k*k/distance**2-A*distance/k))\ .sum(axis=1)

A*distance正在计算弹簧力作用在节点上的强度.相应的A项中的值较大，则意味着在这两个节点之间存在相对较强的吸引力(或者，如果它们非常靠近，则排斥力较小).然后，算法根据力的方向和强度移动节点.然后重复(默认为50次).有趣的是，如果您查看源代码，您会注意到t和dt.似乎在每次迭代中，力乘以越来越小的因子，因此步长变小.

The A*distance is calculating how strong of a spring force is acting on the node. A larger value in the corresponding A entry means that there is a relatively stronger attractive force between those two nodes (or if they are very close together, a weaker repulsive force). Then the algorithm moves the nodes according to the direction and strength of the forces. It then repeats (50 times by default). Interestingly, if you look at the source code you'll notice a t and dt. It appears that at each iteration, the force is multiplied by a smaller and smaller factor, so the steps get smaller.

此处是纸描述算法，很遗憾，该算法位于付费专区后面.这是指向作者网页上论文的链接

Here is a link to the paper describing the algorithm, which unfortunately is behind a paywall. Here is a link to the paper on the author's webpage

这篇关于Networkx弹簧布局边缘配重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！