可视分析动态图中数据的波动模式，是个很有挑战性的问题。一般情况下，我们会选择small multiples形式或动画形式，来分析动态图中的变化模式。本文提出了新的可视化展示方式，TimeArcs，来分析动态图中的波动模式。
small multiples形式（如图1），将时间信息映射到空间上。用户需要同时分析若干个图布局，分析其内部之间的差异。当时间步较长时，用户需要耗费大量的精力来理解每个时间步的图布局，进而分析动态图的波动模式。
图1 采用small multiples，展示2010到2014年，在vis会议发表文章数前50的作者之间的合作关系
动画形式，是将时间信息映射到时间上，用户通过观察分析动画，来分析动态图的波动模式。这就要求用户，尽可能的记住每个时间步的图结构及时间步之间的差异，进而分析动态图的波动模式。
在论文[1]中，作者提出一种新的可视化展示形式，TimeArcs，来可视展示、分析动态图中的波动模式。图2展示的是TimeArcs在图1数据上的应用。在TimeArcs中，每一行表示一个实体，曲线表示相应的两个实体在对应时间上的关联关系。每列展示的是一个时间步上，图的结构信息。
图2 采用TimeArcs，展示2010到2014，在vis会议发表文章数前50的作者之间的合作关系
在介绍TimeArcs详细信息之前，我将介绍三个最相关的工作。
TimeArcsTree[2]（图3）常用来展示动态的、带权重的有向图。在图3中，每个小矩形块表示一个实体，处于同一行的所有矩形块，表示同个实体。每列展示了一个时间步的图信息。实体与实体之间的连边信息，根据其方向，分别放置在实体的左侧和右侧，以此来减少边之间的交叉。边的颜色映射了边的权重。
TimeArcsTree相比于small multiples，能够在更小的空间里，将动态图的整体信息展示出来。但是，TimeArcsTree存在一个不足，就是实体与实体之间的关系是由数据内部的层次结构确定的。因此，不能采用对实体重排列的方式，进一步减少边之间的交叉。
图3 采用TimeArcsTree，展示IP地址之间的访问情况
Parallel edge spatting[3]（图4），与TimeArcsTree相比，可以展示实体数更多，时间步更长，边更加密集的动态图。在图4（3）中，每个条带表示单个时间步图的结构信息。为尽可能减少空间的占用，实体用每个时间步条柱上特定位置表示。同时，采用edge splatting形式，展示实体与实体之间的关系。Parallel edge spatting在构建过程中，同TimeArcsTree，实体在条柱上的位置，由数据内部的层次信息决定。
图4 Parallel edge splatting的创建过程
Storyline也可用来展示动态图中实体关联关系的变化。在Storyline中，线条表示实体，线条之间的相对距离，表示实体之间的关联关系。图5展示了Storyline在展示家庭成员关系上的应用。在这里，红色的线条表示女人，蓝色线条表示男人，线条的长度映射生命的长短。两个线条的靠近，表示相应实体之间的结婚关系。Storyline可以直观的将家庭中成员的关联关系展示出来。但是，它并不能用于展示在一个时间步中，实体之间存在复杂关联关系的数据。比如，研究者可能在一年中，与多个不同的研究者发表多篇文章。这种关联关系，Storyline并不能直观地展示出来。
图5 采用Storyline在展示家庭成员关系[4]
在本文中，作者提出TimeArcs来展示动态图中实体关联关系的变化模式。TimeArcs遵循以下三个设计原则：
1）时间轴水平放置
2）每个实体采用直线表示。直线有利于用户分析实体属性随时间的演变情况。
3）采用曲线表示实体与实体之间的关联关系。
TimeArcs的构建，主要可以分为四个步骤（图6）：
1）计算实体的演变过程
a) 计算实体的出现频率
b) 计算实体突然受关注程度（sudden attention score）来分析实体的演变过程。
如果，实体在每个时间步的频率用(F1, F2 … Fn)表示，那么每个时间步，实体的突然受关注程度可以根据来计算。
2）计算实体之间的关联关系
根据实体在每个时间步出现的频率或突然受关注程度，給所有的实体进行排序。在文中，作者只计算前N个实体之间的关联关系。
3）根据实体之间的关联程度，选择与其它实体关联关系紧密的实体，进行可视分析。
4）可视化阶段
a) 采用力导向布局算法计算每个时间步的图布局
b) 将多个时间步的图布局融合成一个可视化布局
i. 每个时间步，表示同一实体的点处于同一水平线
ii. 根据同一实体在不同时间步的位置，计算竖直方向上的平均值，作为该实体在竖直方向上的位置
c) TimeAarcs支持多中过滤操作。用户可以根据边的权重，时间来过滤数据。同时，用户可以选择特定的实体进行分析。
图6 TimeArcs的构建流程
接下来，我将介绍TimeAarcs在真实数据上的应用。文章作者收集了2005到2015年90811条与政治相关的新闻。他们从数据中提取了四大类实体，分别是人名（绿色），地名（红色），组织（蓝色）和其它（黄色）。图7展示了采用TimeArcs，根据突然受关注分数排在前100的实体之间的关联关系。观察图7（请点击查看大图），我们发现Petraeus在A和B中都出现了。A中，Petraeus和Baghdad（巴格达，伊拉克首都）相关。因为在2007年，他以主将身份参与到伊拉克战争。在B中，Petraeus与Benghazi（班加西）冲突相关联。在C中，我们发现Edward Snowden和NSA突然受到很大的关注，且二者之间存在较长时间的关联。这是因为Snowden在2013年6月被怀疑泄露了美国国家安全局的机密信息。NSA对其进行了调查。
图7 采用TimeArcs展示2005到2015，突然受关注程度前100的实体之间的关联关系。图中涉及的实体有人名（绿色），地名（红色），组织（蓝色）和其它（黄色）。
总的来说，这篇文章提出新的可视化展示方式，TimeArcs，来协助用户分析动态图网络中的波动模式。在TimeArcs构建过程中，他们根据实体的权重（频率或突然受关注程度）和实体与实体之间的关联强度，过滤出重要的实体和实体之间的关联关系；之后，在力导向布局算法中添加限制，对剩余的实体及其关联关系进行布局。在可视化阶段，采用直线表示实体，采用曲线连接两个具有关联关系的实体。
在可视分析动态图随时间的波动模式时，根据某种规则过滤出重要的实体以及实体之间的关联关系，可以展示出动态图的大致变化过程，但同时也会遗失细节信息。如何在展示动态图总体变化模式的同时，展示细节信息，是一个具有挑战性的问题。
参考文章：
[1]T. Dang, N. Pendar, and A. G. Forbes. TimeArcs: Visualizing fluctuations in dynamic networks. Computer Graphics Forum (Proc. EuroVis), 35(3), June 2016.
[2] Greilich M, Burch M, Diehl S. Visualizing the evolution of compound digraphs with TimeArcTrees[C] //Computer Graphics Forum. Blackwell Publishing Ltd, 2009, 28(3): 975-982.
[3] Burch M, Vehlow C, Beck F, et al. Parallel edge splatting for scalable dynamic graph visualization[J]. Visualization and Computer Graphics, IEEE Transactions on, 2011, 17(12): 2344-2353.
[4] Kim N W, Card S K, Heer J. Tracing genealogical data with timenets[C]//Proceedings of the International Conference on Advanced Visual Interfaces. ACM, 2010: 241-248.
评论关闭。