可视化图布局算法简介

本文共886个字,预计阅读时间需要3分钟。

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的多级版本生成。

具体可以参考https://cloud.tencent.com/developer/article/1483027

Yifan Hu

Yifan Hu为胡一凡布局,适用于非常大的图形,特点是粗化图形,减少计算量,运行速度比较快。

Yifan Hu的主页:http://www.yifanhu.net/index.html

参考

  • 北京大学图可视化:http://vis.pku.edu.cn/graphvis/zh-cn/index.html
  • Gephi实战教程:https://blog.csdn.net/meifannao789456/article/details/94581967

 

1 位极客 “可视化图布局算法简介

评论