缩略“图”：一眼辨别图数据 (Graph Thumbnails: Identifying and Comparing Multiple Graphs at a Glance)

作者: 日期: 2018年12月8日

现有的图可视化技术难以在有限的空间有效揭示图数据的丰富内涵。本文[1]提出了一种叫做Graph Thumbnails的方法，它以缩略图的方式将图数据的层次化结构可视化，灵活支持small multiple（小多组图组），方便用户快速浏览图数据库，并具有如下优势：（1）线性时间复杂度；（2）同构不变性；（3）精确展示图的结构信息。通过两个用户研究，作者验证了Graph Thumbnails在标识化、对比和概览图数据这三项常见数据分析任务中的优越性。

研究背景

人们常用点线图和邻接矩阵来进行图可视化，其中，最为广为人知的就是力导向算法[2]。尽管这些方法能够提供关于数据的详尽信息，但当图的规模扩大至成千甚至上万的数量级时，这些方法的最终结果往往不便于解读，产生诸如“毛球”问题或难以对齐的问题（见图1）。实际上，一些应用领域并不用了解数据中的所有元素，它们仅仅需要对大图的整体结构有一个概览。动态图可视化以及网络分析领域对此问题有一定研究，但总体而言有可扩展性差或过于抽象的问题。基于此，作者将可视化的目标转为图的层次结构而非图的元素本身，希望以一种直观而高效的方式来为数据提供一个缩略的标识。

[图1] 大图可视化的常见问题。左：力导向点线图产生“毛球”；右：邻接矩阵栏目过窄，难以对齐。

设计过程

作者将Graph Thumbnails的设计目标提炼为：

  1. 整体算法具有线性时间复杂度以适应快速浏览的目的；
  2. 揭示图数据的层次化结构，在此基础上，保持语义的一致性，即结构相似的图对应的Graph Thumbnails具有相似性；而同构的图具有完全一样的Graph Thumbnails。

而在视觉设计的层面，Graph Thumbnails还具有以下五个设计要求：

  1. 成为一种大图数据标准的可视化方法之一；
  2. 在支持small-multiple对比的基础上尽可能多地提高可读性；
  3. 使各个层次结构内部的视觉元素保持清晰；
  4. 视觉元素的规模能够传递层次结构规模的信息；
  5. 适用于任意图数据。

图的层次化分解

详尽分析了各类图分解的途径后，作者选择采用线性时间复杂度的k-core-component clustering (KC³) 算法。简单来说，k>2时，对一个图G连续移除当前度小于k的结点，留下的的各连通分量称为G的k-cores；而当k=1,2时，k-cores定义为k-连通分量。此前也有类似的先分解后可视化点线图的工作[4, 5]，但由于他们不做抽象，往往线条交错，不利于small multiple的比较。在Graph Thumbnails中，所有的联系被隐去，只编码层次结构信息。

层次结构可视化

作者依据以上提出的五项设计要求，比对了三种常见层次数据可视化方法，最后选定线性时间复杂度的circle packing[7]作为Graph Thumbnails的最终表现形式。它的主体为circle packing下的布局，而边角为各层次结构在边、结点的分布信息以及结点度数分布信息。相对而言，这种表现形式的可扩展性更高，对空间的利用也比较好。

[图2] 三种层次数据可视化方法：(a) treemap 矩形树图； (b) icicle plot 冰柱图[6]；(c) circle packing 圆形填充[7]。

[图3] Graph Thumbnails的解读：(a) 中心为使用circle packing的多核布局，颜色对应图的分解层次；上部是结点度数的分布，下部左右分别是点和线在各层次的分布; (b) 颜色与分解层次的映射关系。

用户研究

作者先后进行了两个用户研究，通过一系列的任务与问卷调查，利用方差分析验证了Graph Thumbnails在暗示数据相似性、揭示拓扑结构信息的两个方面有不差于甚至更优于传统点线图或邻接矩阵图的性质。

使用实例

作者利用Graph Thumbnails对生物数据库DIP (Database of Interacting Proteins)2008至2017年的数据进行了可视化（见图4）。蛋白质交互数据是学者通过各种实验归纳而手动标记而成的，对于每一条边都会有相应的显著水平，每一年的数据都在不断完善。在Graph Thumbnails的可视化下，可以直接了解到每一年各种微生物研究的发展水平并分析不同微生物之间蛋白质交互方式的差异。

[图4] DIP数据库中七种微生物的蛋白质交互图从2008至2017年的演变。左边两列为2008年和2017年的所有数据，而其余列为每年具有最高可信度的核心数据。

小结

Graph Thumbnails可以较好地支持用户纵观大量大图数据并进行对比。在未来的工作中，如何利用Graph Thumbnails对图数据进行交互式的探索以便于深入分析具体网络性质是一个具有广泛应用前景的方向；此外，目前的circle packing布局还有待进一步探索，或能对最终可视化结果增添更多图的拓扑结构信息。

参考文献

[1]. Yoghourdjian, Vahan, et al. “Graph Thumbnails: Identifying and Comparing Multiple Graphs at a Glance.” IEEE Transactions on Visualization & Computer Graphics 1 (2018): 1-1.

[2]. Fruchterman, Thomas MJ, and Edward M. Reingold. “Graph drawing by force‐directed placement.” Software: Practice and experience21.11 (1991): 1129-1164.

[3]. Batagelj, Vladimir, and Matjaz Zaversnik. “An O (m) algorithm for cores decomposition of networks.” arXiv preprint cs/0310049 (2003).

[4].Alvarez-Hamelin, J. Ignacio, et al. “Large scale networks fingerprinting and visualization using the k-core decomposition.” Advances in neural information processing systems. 2006.

[5]. Archambault, Daniel, Tamara Munzner, and David Auber. “Topolayout: Multilevel graph layout by topological features.” IEEE Transactions on Visualization & Computer Graphics 2 (2007): 305-317.

[6]. Kruskal, Joseph B., and James M. Landwehr. “Icicle plots: Better displays for hierarchical clustering.” The American Statistician 37.2 (1983): 162-168.

[7]. Wang, Weixin, et al. “Visualization of large hierarchical data by circle packing.” Proceedings of the SIGCHI conference on Human Factors in computing systems. ACM, 2006.

论文报告, ,

评论关闭。