用于理解时变体数据的图挖掘 (Mining Graphs for Understanding Time-Varying Volumetric Data)

在科学可视化中,利用graph等抽象视图来展示数据是近年来一中比较流行的趋势。通过将数据和它们之间的关系映射到一个低维的空间,用户往往可以探索更复杂的数据关系,并且更好地理解数据的特性。但是,这些基于graph的方法大多数都缺乏足够的对用户探索的引导,导致用户常常只能够依赖于一些低级的视觉提示(例如结点和边的大小和密度等)和简单的刷选链接等交互,在使用的时候会感到费时费力。当面对规模比较大数据关系比较复杂的情况时,这些方法更是表现出了很大的不足。针对这些问题,这篇文章提出了一种图挖掘的方法,包含了图简化(graph simplification),社区检测(community detection)和视觉推荐(visual recommendation)等三种技术,能够自动提取时变数据的特征[1]。

由于该工作主要研究的是数据之间随时间的转移关系,因此数据的展示使用了之前的工作,TransGraph[2],也就是转移图。在转移图中,结点表示一组相似的并且时空上相邻的数据块,有向边表示结点之间的转移关系,使用转移概率作为权重。下面会依次介绍基于转移图的这三种图挖掘技术。

图1:图简化。(a)扇形; (b)连接体; (c)小集团。

图1: 图简化。(a)扇形; (b)连接体; (c)小集团。

图简化的目的是减小图中的结点个数以减轻遮挡问题,并且可以更清楚地展现重要的结构。其方式是使用三种符号代替图中的特征,分别是扇形(fan),连接体(connector)和小集团(clique)。如图1所示,扇形是一个中心结点和多个度为1的叶结点组成的结构,连接体是两个端结点中间连着多个度为2的中间结点,而小集团则表示的是多个结点的全连接。经过图简化操作后,转移图中结点的数量有了显著的减小。

图2:社区检测

图2:社区检测

社区是具有相似关系的一组结点的组合。如图2所示,通过检测图中的社区,用户可以更容易地了解图的结构和演化,减小探索负担。社区检测的算法由标签传播算法(label propagation algorithm)拓展而来,思想是每个结点向其邻居结点传播自己的标签,等到一定迭代程度后,具有相同标签的结点会被归为同一个社区。

结点推荐

图3: 结点推荐。(a)中红色为选择的结点,黄色为推荐的结点,(b)为红色结点对应体数据空间中的块,(c)和(d)分别为黄色结点在之后两个时间步体数据空间中对应的块。

视觉推荐包含两个方面。一个是结点推荐,如图3所示,目的是在用户选择一个结点或多个结点后高亮相似的结点。算法基础是结点的相似性,根据结点的入边或者出边及其权重计算而来(SimRank算法)。另一个是社区推荐,如图4所示,是在用户选择一个社区后高亮相似的社区。社区推荐的算法首先要将社区转化成无权重无方向的图,再将图转化成string,通过比较string的差异得到图的差异。

社区推荐

图4: 社区推荐。(a)中红色为选择的社区,黄色为推荐的社区,(b)和(c)分别为它们对应的体数据空间的块。

图挖掘技术可以产生更易于理解和探索的图形式,并且减小用户对科学数据探索和发现的负担。这些优点也得到了领域专家的认可。实际上,这个工作看起来更像是将图可视化中的一些方法引入到之前的工作,用于时变体数据的探索中。从这里也可以看出来,科学可视化已经越来越频繁地用到了信息可视化的技术,两者的联系越来越紧密,这也是之后可视化研究的一个趋势,也给我们做科学可视化的学者提供了一个新的思路。

Reference
[1] Yi Gu, Chaoli Wang, Tom Peterka, Robert Jacob, and Seung Hyun Kim. Mining Graphs for Understanding Time-Varying Volumetric Data. IEEE Trans. Vis. Comput. Graph., 22(1):965-974, 2016.
[2] Yi Gu and Chaoli Wang. TransGraph: Hierarchical Exploration of Transition Relationships in Time-Varying Volumetric Data. IEEE Trans. Vis. Comput. Graph., 17(12):2015-2024, 2011.

评论关闭。