Force-directed graph-力导引图

二维码

首先上一个Wikipedia上的定义：

Force-directed graph drawing algorithms are a class of algorithms for drawing graphs in an aesthetically-pleasing way. Their purpose is to position the nodes of a graph in two-dimensional or three-dimensional space so that all the edges are of more or less equal length and there are as few crossing edges as possible, by assigning forces among the set of edges and the set of nodes, based on their relative positions, and then using these forces either to simulate the motion of the edges and nodes or to minimize their energy.

有边相连的节点之间通过基于胡克定律的弹簧式引力彼此吸引（Edge attraction），而基于库仑定律的带电粒子的斥力用于分离所有节点对（Vertex repulsion）。
迭代到系统平衡状态，在这个力系统的平衡态中，边的长度趋于一致（因为弹簧的力），没有边连接的节点趋向于进一步拉开（因为电排斥）。需要注意的是，引力和斥力可以用不基于弹簧和粒子物理行为的函数来定义，例如，弹簧的吸引力可以是对数的，而不是线性的。
另一种模型认为，对于每一对节点 (i, j) ，弹簧的理想长度 \delta_{i,j} 与节点之间的graph-theoretic distance（不知道怎么翻译好）成正比，而不使用单独的斥力。最小化欧几里得距离与理想节点距离之间的差值（通常是平方差）相当于一个metric multidimensional scaling problem（度量多维尺度问题？？）.

一些改进，类似于重力的力可以用于将顶点拉向绘图空间的不动点。这可以用来把一个分离得图形中的不同的连通分量拉到一起，否则由于斥力的作用，这些部件可能会彼此分离；也可以以更大的中心性（centrality，图论术语）绘制节点，还可能影响连通分量内部的顶点间距。
磁场的类似物可以用来描述有向图。为了避免在最终绘图中出现重叠或接近重叠，也可以在边上放置斥力。在绘制圆弧或样条曲线的时候，还可以在这些曲线的控制点施加力，以提高其角度的分辨率。

一旦定义了图中节点和边上的力，就可以将图看做一个物理系统，重复迭代直到处于机械平衡状态（从一个迭代到另一个迭代，它们的相对位置不再改变），此时节点的位置被用来生成绘图。
其他的方法包括使用stress majorization（一种在MDS中使用的优化策略）和使用直接搜索能量极小值的机制，而不是与物理模拟结合使用，这些机制一般是全局优化方法的例子，包括模拟退火和遗传算法。

力导引图的优点：

• 高质量的结果
  
• 灵活
  
• 直观
  
• 简单
  
• 交互性
  
• 强大的理论基础
  

力导引图的缺点：

• 时间复杂度高
  
• 容易陷入局部极小值
  

d3-force
This module implements a velocity Verlet numerical integrator for simulating physical forces on particles. The simulation is simplified: it assumes a constant unit step \Delta t=1 for each step, and a constant unit mass m=1 for all particles. As a result, a force F acting on a particle is equivalent to a constant acceleration a over the time interval \Delta t , and can be simulated simply by adding to the particle's velocity, which is then added to the particle's position.

参考文献：


原文地址：https://zhuanlan.zhihu.com/p/48354020