一种基于力导向布局的层次结构可视化方法

计算机仿真 2014-3
北京工商大学

在数据结构优化管理的研究中，传统的力导向方法应用于层次结构数据的展示时，会存在树形布局展示不清楚的问题。为解决上述问题，通过层次数据特征分析，提出了一种面向层次数据的力导向布局算法，将力导向布局中不同层次的边赋予不同初始弹簧长度，以解决层次数据中结构信息展示不清楚的问题，然后结合层次上下行、Overview+Detail等交互技术，通过与气泡图的协同，清晰展示层次数据的内容信息，从结构和内容角度对层次数据进行可视化和可视分析。实验表明，能够有效提高层次结构数据的展示能力，最后应用于农产品中农残检测结果数据的分析和观察，取得良好效果。

引言

层次数据的节点链接可视化方法主要包括双曲树(Hyperbolic Tree)和径向树(Radial Tree)等。

双曲树是一种fbcus+context技术来显示大型层次数据的可视化方法。该技术的本质是使用统一的算法将层次结构布局到双曲平面上，然后再将该双曲平面映射到圆形显示区域。

力导向算法是一种常用的绘制一般网状结构的方法。最初由PeterEades提出，它仿真物理力学的概念，对网络图中任意一个节点，都受到引力及斥力。引力是由与此节点有边相连接的每个邻居所提供的合力，其意义是节点与其邻居之间的距离不会太远；斥力是由整个网络图中除了本身以外的节点所提供，为了让任意两节点不会因距离太近而产生重叠的现象，也因此整个网络图不会太密集而影响视觉。

算法的终止通过给定节点的初始位置，放人此力导向的物理模型中，系统自动调整节点位置，直至达到稳定条件才结束。

对于簇状数据，出现了一种与力导向结合的方法，此方法是一种基于将一个图划分为多个子图的多级技术．开始先构建最小的子图，使用力导向布局调整节点的位置．然后在下一层级的子图划分中使用调整好后的结果。

但是，力导向算法应用于树型数据的研究还较少。本文将力导向算法应用于层次数据的布局，提出一种可变弹簧的力导向布局算法，能够较好展示结构信息，并结合气泡图展示其中的内容信息，设计完成了多视图协同可视分析系统.

向层次数据的力导向布局算法

传统力导向布局会产生边长度相对一致的情况，而这种情况对层次结构的展示是不明显的，尤其是在节点普遍具有较大出度的情况下，在布局中表现为中心节点即根节点处有节点混杂，在叶节点处子树的交叉遮挡现象严重．子树的成团效果不明显，因而影响对层次数据的观察。

本文考虑调整不同层次的边的长度以示区分，以不同的边长表现不同的层次，使得根节点处的边长较长而叶节点的边长较短。并依树形结构的结构特征达到一定的边长比值，从而实现中心节点处发散而叶节点处收敛的目的。

对于不同层次的边赋以不同的长度，以区别其向指父节点和其子节点的边。并使相邻层次满足边长比例为C，C为某常数,将此布局算法称为可变弹簧力导向布局算法VSFDP。

斥力计算：

引力计算：

确定不同层次弹簧长度的比值常数C
对于一棵规则的满n叉树来说，节点所处的层次越高，其子树包含的节点数目越多。这篇文章将N层节点与N+1层节点的比值定为常数n，则C=n，但是如果每层节点的度的比值不是常数，那么就使用数的平均度来作为常数C：

<< 更多精彩尽在『程序萌部落』>>
<< https://www.cxmoe.com >>

VSFDP算法步骤：

1. 将输入数据转化为树型结构存储
2. 计算树型结构的源数据：非叶子节点的度，树的平均度
3. 根据期望距离（默认长度）+比例常数C来规定每层的边长度
4. 建立模型，代入数据

交互方式

• 层次放大和层次缩小
• Overview+Detail
• 气泡图

系统设计

可视化流水线是将原始数据转换成计算机内存中数据结构。并用一种可视化方法将数据在屏幕上展现出来的过程，如图下图所示，在这个过程中包括用户的交互反馈以及各种工具方法等的使用。

实验结果

总结

这篇论文第一个创新点是对传统力导向算法的改进，加入了分层布局，使用整个图的平均度作为常数C，这样的结果就是度大的节点被分为一层，这里他们在布局时会被赋予较长的边距离，然后依次类推，下一层节点拥有较小的度，但是赋予的边的距离也同样变短。
另外，在交互手段上使用气泡图辅助，气泡图的圆心在当前层的节点位置，半径同样是按层间的比例，在将布局展示的同时通过气泡来辅助交互。