用于稠密有向图中的边压缩技术 (Edge Compression Techniques for Visualization of Dense Directed Graphs)

概况

在图绘制领域,由点和边的重叠、交叉而引起的视觉混乱是经常碰到的问题。在本篇文章中,作者对边压缩技术进行了总结,提出了基于约束编程的优化技术,并且通过实验逐层验证了边压缩在解决视觉混乱中所起的作用。

图一: 三种边压缩技术, (a)标准点边图,(b)近邻匹配结果,(c)模块分解结果,(d) 复杂图分析结果

当作者在Microsoft Visual Studio下开发软件依赖的可视化工具时,发现即使不显示子模块,顶级模块之间的复杂联系也会使得模块之间的依赖关系难以辨别,例如:如图二所示,在图二(a)很多模块都会依赖”Externals”模块,而这些依赖边造成很多的交叉从而使得其他边的走向不易观察。接着通过一种边压缩技术将指向”Externals”模块的边压缩成一条边可以得到图二(b),反复使用可以得到非常简洁的图二(c),在图二(c)中只剩下6条边,压缩了原始连接数的85%。从这个例子中可以看出,对于稠密的图,特别是有向图,进行信息的无损压缩是有必要的,它能够降低视觉复杂度。

图二: 将边压缩技术应用于IronPython代码上的结果,(a)具有39条边的IronPython模块依赖点边图,(b)将依赖”External”的边进行聚集,(c)反复使用边压缩技术,得到简洁的IronPython模块依赖关系

 三种边压缩技术

近邻匹配

近邻匹配是最简单的技术,当不同的节点具有相同的另一端相同的边连接时,可以对他们进行匹配,封装为一个模块,而他们的边也进行合并,这样可以减少边连接的数目且不减少信息表达量。另一种情况是,可以通过一个自反边将模块内部具有联系的边表达出来,如图三(d)所示。

图三: 近邻匹配,(a)的星型叶子节点合并成一个模块(b),(c)中的模块内的边用指向自己的弧表示

模块分解

模块分解比近邻匹配更近一步,在近邻匹配中模块内的边要么是没有、要么是全有,而这里模块内是可以存在边,如图一(c),只要外部边对于模块是不可区分即可。模块分解的过程是多项式复杂度的。

复杂图分析

复杂图分析相对于模块分解更进一步,复杂图分析不仅容许模块内有边,并且容许模块外和模块内节点的边,如如图一(d)。复杂图分析的算法复杂,存在不同的模块分解解,找到最优解是NP难问题。

实验1

为了检验边压缩技术的可读性,作者设计了一个15人参与的用户研究,分别使用三种不同复杂度的数据,以及“未压缩点边图”,“近邻匹配”和“模块分解”技术,然后以找出最短路径为任务进行测试。测试结果显示如下:

图三:实验一测试结果

图三:实验一测试结果

  • 在正确性上,三种技术表现相差不多,说明边压缩技术不会带来信息流失;
  • 在测试速度上,无论是简单数据还是复杂数据,“模块分解”后的图表现最好,使用时间最少;
  • 通过调查用户的主观喜好,发现用户普遍喜欢使用“近邻匹配”后的结果,原因是普通点边图有较多的边交叉重叠情况,而模块分解需要更多的脑力去解释聚集的边。

通过实验一的测试,可以说明边压缩技术能在信息无损的情况下,具有显著的优势,并且在训练用户时,用户都能在较短时间内掌握方法。然而,作者接下来思考在“复杂图分析”中,这种带有穿过边界边的图中,更多的边压缩是否同样会带来好处。

在进行实验二之前,作者首先对“复杂图分析”的复杂度(NP难)进行了简单分析,并且通过MiniZinc模型设计了一个包含约束和可调参的目标函数的模块分解计算模型。目标函数:minimize numbermodules + edgeweight * numberedges + crossingweight * numbercrossings。

实验2

实验二的实验目标是:为了验证穿过边界边对图的可读性的影响。此次实验中,用了“近邻匹配”,“模块分解”和“复杂图分析”的方法,数据方面使用实验一的复杂数据集和新增加的具有更多穿过边界边的数据,其他过程和实验一类似,任务依然是找到最短路径。测试结果显示如下,通过分析的得出:数据复杂度和穿过边界边的数目是对结果产生影响的两大因素。

图四:实验二结果

图四:实验二结果

  • 在正确性上,具有大量穿过边界边的图会导致错误率上升。
  • 在时间上,具有中等数目的穿过边界边表现良好,用户能在较短时间内完成任务;而当数据变的复杂时,穿过边界边的数目不在影响结果。
  • 通过收集用户反馈,发现用户一部分对模块的递归比较反感,另一部分对穿过边界边感到不适应。
图五

图五: (a)点边图具有140个点和406条边,(b)压缩后版本具有17个模块,边的数目减少到208条

通过以上两个实验,可以得出:用户能够快速掌握被压缩边的含义;边压缩能够帮助用户减少观察时间;另外具有中等规模的穿过边界边也能帮助用户提高观察速度。虽然在复杂图上没有做更多的实验,但是合理的压缩边仍然可以减轻视觉混乱的情况,如图五,边的数目从406减少减少到208,能够看到明显的聚类和依赖关系。

笔者认为边压缩技术实际上是结合了点聚类和布局的技术,和边捆绑技术的出发点不同,因为边捆绑技术常用于点不能移动的图中;另外一方面,边压缩技术的信息无损的性质对于边捆绑是一大优势;最后本文验证了边压缩对图的视觉效果的影响,对以后的工作具有很好的帮助作用。

[1] Tim Dwyer, Nathalie Henry Riche, Kim Marriott, Christopher Mears. Edge Compression Techniques for Visualization of Dense Directed Graphs.IEEE Trans. Vis. Comput. Graph. 19(12): 2596-2605 (2013)

评论关闭。