6.2.1 节点链接法
节点链接法
顾名思义,节点链接法是用顶点和它们之间链接的边来表示动态图单独时间布局。如图6.13所示,Time Arc Trees可视化中图的顶点排列在垂直线上,有向边用弧表示,其中每条边的权重决定弧的颜色,有向边顶点的顺序(自上而下或者自下而上)决定弧的位置(垂直轴的左边或者右边)。Time Arc Trees的优点是:垂直排列顶点获得紧凑性布局;优化顶点在垂直线上的排序降低可视复杂度;垂直轴两侧画出带颜色的弧避免边交叉。Time Radar Trees和Time Spider Trees利用辐射图方法,用分布在圆周上多个小圆环的扇形和中间大圆环的扇形相结合表示动态图中边随时间的变化,如图6.14和图6.15所示。Burch等人提出动态网络可视化的平行边Splatting算法,该方法从左到右表示随时间变化的动态图序列,每对平行边内部层次化组织的顶点在平行边上垂直排列,有向边从左向右连接平行边上的顶点,如图6.16所示。为了解决大规模图的边覆盖问题,该方法利用Splatting算法将边转换为基于像素的矢量域;为了支持数据探索,该方法在定义动态图的静态模式和动态模式基础上,提供聚集、过滤、刷新和选择数据缩放等交互操作。
图6.13 Time Arc Trees
图6.14 Time Radar Trees
图6.15 Time Spider Trees
图6.16 平行边Splatting
如上所述,单图像的时间线可视化技术占据较多的屏幕空间,因此适合较小规模动态图可视化。对于较大规模的动态图,可以采用其他方法关联时间序列的布局。如图6.17所示,堆叠顶点链接图是用一个水平层次表示一个时间步布局,而且每层中相同顶点垂直方向上整齐排列。该方法中顶点有相同位置,属于不同时间步层次的边还可以通过颜色和线条来分辨。堆叠节点链接图的最大问题是增加时间方向的Z轴使它变成三维图,这明显提高了覆盖引起的可视复杂度。因此该方法只用在层次比较离散的情况,通常使用2.5维的技术。Brandes等人将顶点描述为圆柱,但是增加透明平面帮助分辨堆叠的多层。Erten等人允许同样顶点在层中有不同位置,但通过调整力引导布局算法将相同顶点移动到多层之间比较相似的位置。
图6.17 堆叠顶点链接图
力引导布局方式是节点链接布局方法中的代表性布局方式。1984年,Eades首次提出了用弹力模型(spring-embedded model)实现图布局算法。弹力模型即力学中常用的虎克定律(Hook’S law):在弹性限度内,物体的形变跟引起形变的外力成正比。Eades将图中的边看成力学中的弹簧,利用弹力关系决定图点的布局。
一个弹簧有自然长度￡和当前长度d,自然长度￡是指是没有受外力情况下,弹簧应有的长度,当前长度d是指弹簧受到拉伸或压缩产生变形后的长度。
虎克定律规定了弹簧长度与其能量(由弹力产生)的关系:(https://www.daowen.com)
(1)如果￡=d,弹簧受力为0;
(2)如果d＞l,弹簧受到拉伸(吸引)力;
(3)如果d＜￡,弹簧受到压缩(排斥)力;
(4)吸引力和排斥力与|d-l|成比例;
(5)能量是由相对于|d-l|的力形成的。
Eades弹力模型的基本思想是将图看成节点为弹簧的端点,连接边为弹簧的物理系统,系统被赋予某个初始状态以后,弹簧弹力的作用会导致图中节点的移动,这种运动直到系统总能量减少到最小值时停止。
原先节点的位置作为图的初始布局,连续使用弹簧力移动节点,到达一个最小能量状态。
调整节点位置的方法有两种。首先,对邻接的节点(钢环)施加弹簧力,力的大小为:
C 1*lg(d/C 2)
其中,d为弹簧的长度,即两个节点之间的距离;C 1和C 2是常数,控制力的大小。
实验说明,如果使用力学中的虎克定律,当节点分离时,力太强,故使用了对数解决这个问题。当d=C 2时,即直接使用了弹簧力。
其次,对不相邻的节点互相使用斥力。力的大小为:
其中,d为两个节点之间的距离;C 3是常数,控制力的大小。
Eades弹力模型算法的伪代码为:
弹力模型算法易于理解和实现,并且能画出比较优美的图形布局,充分展现出图的整体结构及其自同构特征,成为最著名的一种图布局模型的基础,日后许多图布局模型的建立都是基于Eades弹力模型基础之上的。
