可视化图布局算法简介

傷城~ 2023-07-03 03:24 27阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]

# Fruchterman Reingold (FR) #

FR算法将所有的结点看做是电子，每个结点收到两个力的作用：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 1]

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

f a ( d ) = d 2 k f\_\{a\}(d)=\\frac\{d^\{2\}\}\{k\} fa(d)=kd2

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

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

# OpenOrd #

OpenOrd是一个面向大规模图布局的开源算法，来自论文OpenOrd:An Open-Source Toolbox for Large Graph Layout  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 2]

这是一种力-导向的布局算法，专门用于处理非常大的图结构

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

具体可以参考[OpenOrd论文中文版][OpenOrd]

# Yifan Hu #

Yifan Hu为胡一凡布局,适用于非常大的图形，特点是粗化图形，减少计算量，运行速度比较快。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 3]

[Yifan Hu的主页][Yifan Hu]

# 参考 #

[北京大学图可视化][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200201170117578.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200201170031429.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200201170046802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2,size_16,color_FFFFFF,t_70
[20200201170046574.png]: https://img-blog.csdnimg.cn/20200201170046574.png
[OpenOrd]: https://cloud.tencent.com/developer/article/1483027
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200201170108282.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h5aXN2,size_16,color_FFFFFF,t_70
[Yifan Hu]: http://www.yifanhu.net/index.html
[Link 1]: http://vis.pku.edu.cn/graphvis/zh-cn/index.html
[omegaxyz.com]: https://www.omegaxyz.com