6.3.2 图可视化的视觉效果
随着网络数据规模的不断扩大,人们逐渐发现,在使用传统方法绘制的结果中,节点和边经常出现互相遮挡,形成极高的视觉混杂(visual clutter),甚至会阻碍我们对真实数据的认知。因此,从21世纪初起,在信息可视化和图给制两个科学研究领域,分别涌现出大量的成果来解决这些问题。这些研究工作大致可以分为两种基本思路:一种思路是根据信息可视化的信息分级(level of detail)原则,对大规模图进行层次化简化;另一种思路是在尽量不减少原图信息量(包括边和节点的数目)的前提下,对图进行基于骨架的聚类。无论采取哪种思路,其目的都是应对大规模图对有限可视化空间的挑战,降低网络数据可视化的视觉混杂度,挖掘和展示数据背后隐藏的信息。
本节将从这两种思路入手,分别介绍图可视化领域的最新技术。
1.图的拓扑简化
图的拓扑结构由节点和边两个部分构成。与此对应,有两种方法对图的拓扑进行简化,即分别对节点和边进行层次化简化。具体介绍如下:
对于一个节点数为N的无向图,在不存在重复边的情况下,最多存在N(N-1)/2条边。对于某些N相对较小而边数较多的图,可以绘制其最小生成树从而对边进行简化。最小生成树的定义是:在一给定的无向图G=(V,E)中,(u,v)代表连接顶点u与顶点v的边,而w(u,v)代表此边的权重,若存在T为E的子集且为无循环图,使得w(T)最小,则此T为G的最小生成树。
图6.22展示了一个节点数为10、边数为21的无向图和它的一颗最小生成树(加粗表示)。在这个结果里,使用最小生成树展现了图的骨架特征,大大减少了绘制边的强度,这一优势在图的规模较大时更加明显,产生最小生成树的算法有很多,比较著名的有Kruskal算法和Prim算法等。
图6.22 利用最小生成树表达图的骨架结构
(1)Prim算法简述
①输入:一个加权连通图,其中顶点集合为V,边集合为E。
②初始化:V new={x},其中x为集合V中的任一节点(起始点),E new={},为空。
③重复下列操作,直到V new=V。
a.在集合E中选取权值最小的边＜u,v＞,其中u为集合V new中的元素,而v不在V new集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一)。
b.将v加入集合V new中,将＜u,v＞边加入集合E new中。
④输出:使用集合V new和E new来描述所得到的最小生成树。
(2)Kruskal算法简述
假设W N=(V,{E})是一个含有n个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根节点,则它是一个含有n棵树的一个森林。之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依此类推,直至森林中只有一棵树,也即子图中含有n-1条边为止。(https://www.daowen.com)
前面我们提到,除对边的提取外,还有一种图的简化算法:将强连通的节点进行聚类,并把聚类后的节点集作为一个新的超级节点绘制到可视化结果中,这里一个关键的问题是,如何对节点进行合理的聚类,使得每个聚合成的类内部具有强连通特性,而类与类之间的连接则相对稀松。这一问题在复杂网络的数据挖掘领域被称作社区发现(community detection)。如图6.23所示,社区发现算法将已有的网络数据划分为多个不同的社区。
图6.23 经典社区发现算法图例
2.图的边绑定
边绑定技术也被称为边聚集、边聚类,近年来,得到了来自国内外研究人员越来越多的重视。它不仅被用于图可视化,也被用于流图可视化与平行轴可视化等其他可视化领域。尽管依据不同的数据类型,边绑定都旨在聚集相似的边(或线段)形成边束,以显示数据潜在的整体模式。若干相关研究已经在国内外发表,为了方便和深入地讨论,我们依据算法使用的范式和思想,将这些成果大致分为三类。
第一类是所谓的基于几何的技术,包括层级绑定算法、几何结构绑定算法和歧义避免绑定算法等。基于几何结构的边绑定技术主要思路是依据边表现出来的几何结构,设置合适的控制点,并根据这些控制点来弯曲相关的边。每个控制点吸引一些边向其靠近,并使得这些相互靠近的边形成想要的边束。对于基于几何的技术,选择合适的算法和数据结构是十分重要的。
层级绑定算法使用额外的层级结构来进行控制点的定位,因此它要求处理的图数据集必须是复合图,即图中不仅包含一般的关系结构,还包含一个显性或者隐形的层级结构。具体地,层级绑定算法在层级结构形成的最小公共祖先路径上选取合适的位置摆放控制点,并使用B样条曲线绘制最终的绑定结果。由于层级结构优秀的稳定性和良好的组织性,层级绑定算法的可视结果也同样容易被识别和认知。然而大多数图数据并不天生包含这样一个额外的层级结构,或者并不容易从原始数据中形成这样的层级结构,这大大限制了层级绑定算法的应用范围。
几何结构绑定算法克服了HEB依赖特殊数据结构的弱点,提出了一种通用的计算流水线,可以应用于任意一般的数据集。几何结构绑定算法将展现空间均匀分割为相同尺寸的网格,通过计算格点的相似性将相似的格点聚类,形成更为大的区块,并使用Delaunay三角化技术将区块组织成一个控制网格,最终的控制点就位于mesh和边的交点上。
总体而言,基于几何结构的技术是直观的、有效果的,但是却依赖于特殊的应用场景。层次绑定算法需要额外的层次结构;歧义避免绑定算法要求足够的避让空间;几何结构绑定算法由于缺乏全局的统筹,往往形成十分强烈和频繁的弯曲边。
第二类是所谓的基于优化的技术,具体包括力导向算法、双向分离算法和多级凝聚算法等。
力导向算法中,边被模型化为带有弹性的弦,并且弦上“串”着带电荷的粒子,粒子之间存在相互吸引的引力和相互排斥的斥力,最后通过构建一个自组织的物理模型来模拟上述模型,使得系统演化并最终进入一个优化状态。需要指出的是由于初始状态是固定的,上述模拟过程是稳定的,即多次模拟结果是相同的。另外,其他相容性度量也被容纳到上述模型中,如角度相容性、位置相容性和可见相容性,以避免过度的绑定。
双向分离算法是力导向算法的延伸,它将力导向算法扩展到有向图中。它追加了一种新的相容性度量,称为连通相容性,并将边整合到模型中。通过这些努力,双向分离算法能够很好地帮助用户感知非对称的结构。
多级凝聚算法,相对而言,则更为直接地定义并使用优化模型来进行边绑定。它设定最小化“墨水”(和边在渲染后的长度相关)的使用量为优化目标,通过在不同级别上检验是否存在,通过共享路径可达到减少“墨水”的条件,从而迭代优化“墨水”的使用量。最终,模型在无法继续找到共享路径的“最优”条件下停止。
总体而言,基于优化的技术类型能够减少不必要的弯曲,并且能够揭露出数据背后潜在的模式,但由于所用模型的限制,该类技术往往具有非常高的计算复杂度,通常至少为平方阶或更高阶,这在一定程度上限制了该类算法适用的数据规模。
第三类方法将传统点线图渲染后的结果图片作为输入,并借用图像处理领域的成熟技术,引导边向某个合适的方向或位置移动,以达到聚集相似边的效果。这类方法被称为基于图像的方法。这类技术的典型代表有核密度估计算法与骨架提取算法。
核密度估计算法通过成熟的核密度估计方法获得像素位置的边密度,形成密度地图,之后让边向着密度地图上密度梯度增加最快的方向移动,即向偏导数向量的方向移动。基于骨架提取的算法则直接使用成熟的骨架提取算法,而不是间接地计算核密度。基于图像的方法可以较为容易地融合加速技术,如GPU硬件加速。另外,各种图像增强工具,如密度饱和、阴影、光晕效应等,被用来帮助用户区分交叠的边束。然而,该类方法生成的结果往往带有强烈的“主干-分支”形的特征,而这并不是数据本身所具有的特征,并且其结果往往存在过强的绑定,使得结果难以被识别和使用。
最后,值得独立讨论的边绑定方法还有被称为基于网格的边绑定技术,其中最具代表的是崎岖路径技术。虽然崎岖路径技术也使用到了前几类方法所用到的技术,但其最引人注意之处是它使用了在格点上求取最短路径作为曲线路径的范式。崎岖路径技术先通过四分树将展现空间分割成细粒度的规则格点,再通过Voronoi技术归并一些冗余的格点,这样做的目的是减小后续求取最短路径时的计算代价。之后该技术求取每个格点的权重,权重主要和穿过该格点的边的数量成负相关比例,由此形成了一个带权地图。通过求取任意两点在该带权地图上的最短路径,对每条边进行二次路径规划,确定最终的曲线绘制路径。需要指出的是,崎岖路径技术还使用了一系列平滑算法,如高斯滤波算法,来减少最终结果中普遍存在的细微抖动。
