可视化图布局算法简介

文章目录

Fruchterman Reingold (FR)

FR算法将所有的结点看做是电子，每个结点收到两个力的作用：

1. 其他结点的库伦力（斥力）

$f_{a}(d)=\frac{d^{2}}{k}$

2. 边对点的胡克力（引力）。

$f_{r}(d)=\frac{-k^{2}}{d}$

该算法遵循两个简单的原则：有边连接的节点应该互相靠近；节点间不能离得太近。FR算法建立在粒子物理理论的基础上，将图中的节点模拟成原子，通过模拟原子间的力场来计算节点间的位置关系。算法通过考虑原子间引力和斥力的互相作用，计算得到节点的速度和加速度。依照类似原子或者行星的运动规律，系统最终进入一种动态平衡状态。

OpenOrd

OpenOrd是一个面向大规模图布局的开源算法，来自论文OpenOrd:An Open-Source Toolbox for Large Graph Layout，这是一种力-导向的布局算法，专门用于处理非常大的图结构。

左边（a）显示的是瑞士卷Swiss roll数据集，由瑞士卷副本manifold随机抽取的2万个点组成19,30。
中间（b）显示的是一个由使用VxOrd的20个最近的邻居这种算法从瑞士卷中获得的力-导向布局。
只有节点被绘制了出来，图被着色以说明全局结构的纠缠tangling。
右边（c）中显示了正确绘制的图结构，使用OpenOrd的多级版本生成。