转载

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

目前,动态图可视分析方法主要分为small multiples和animation两大类。Small multiples方法,将时间映射到空间上,用户需要同时观察若干个snapshot,相互比较来获取差异。由于屏幕空间有限,当时间步很多时,很难同时展示出所有时刻的网络,且用户难以分析获取动态网络的变化模式。Animation方法,将时间映射到时间维度,用户在每个时刻只能观察到一个时间步的网络,需要去记忆,理解时间步之间网络的变化情况,进而理解动态图的变化模式。

本文提出一种新颖的方法,来分析动态图的变化模式。他们将每个时间步的网络转换成高维向量,将这些高维向量投影到二维平面,用点表示。如图1所示,投影后得到的布局中,每个点表示一个时间步的snapshot, 每条边连接了两个相邻时刻的顶点。这个方法可以有效地帮助用户探索分析动态图的稳定状态、重现状态、异常状态以及状态与状态之间的转移过程。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图1 将左图的snapshot降维到二维平面的点,如右图所示

这个方法包括四个步骤(图2):

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图2 流程图

1)  离散化(Discretization):原始数据由一系列的事件组成,每个事件均发生在两个实体之间。为了将原始数据离散化,构造一系列的snapshot。他们采用滑动窗口在事件序列上滑动的方法,生成一系列的时间窗(为了最后投影结果的连续性,建议时间窗之间的重叠率为50%以上),然后将每个时间窗内的所有事件转换成一个等价的网络。网络中的顶点和边分别是这个时间窗内出现的顶点和边,其中边的权重表示该边在这个时间窗出现的次数。图3展示了,不同重叠率,对投影结果的影响。观察可发现,重叠率越高,越多有趣的模式会展示出来。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua... 将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图3 滑动窗口,不同重叠率对投影结果的影响。第一行,滑动窗口大小可变,每个窗口包含的顶点数恒定;第二行,滑动窗口大小恒定,每个窗口包含的顶点数可变。

2)  向量化和归一化(Vectorization and Normalization):为了进行投影,需要将每个snapshot转化成一个高维向量。具体的做法是,先用邻接矩阵表示每个时间步的网络,然后将n*n的矩阵,转化为1*n的高维向量,也可在高维向量中添加一些额外的属性,比如活跃顶点的个数等。文章讨论了二值化,Min-max scaling,z-score归一化方法对最后投影结果的影响。如图4所示,z-score归一化方法不会压抑网络中的异常现象,相较而言,是比较好的选择。但是否需要进行归一化,选择哪种归一化方法,还是需要根据具体的数据来定。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图4 未归一化和采用不同归一化方法,线性投影获得的结果

3)  投影(Dimensionality Reduction):将高维向量采用线性投影方法(PCA)或非线性投影方法(MDS 和t-SNE)进行投影,获取二维投影结果。文章讨论了不同的投影方法,不同的距离方法对结果的影响。他们认为没有一种标准来说明何种方法更好,具体的投影方法,用户需要根据具体的数据进行选择。

4)  可视化与设计(Visualization and Interaction):图5展示了系统的界面。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图5 系统界面。A,投影图 ( Projection View),每个点表示一个snapshot,颜色表示时间;B,图布局 (Network View),采用点边形式展示在A视图中选中的snapshot的细节;C, 时间轴 (Time Control);D,辅助视图 (Auxiliary View) ,展示在A视图中选择的snapshot的度的分布等信息。

文章介绍了他们方法在虚拟数据和真实数据上的使用情况。

Case1–虚拟数据(图6、图7):

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图6 线性PCA投影结果

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图7 (a) 选择时间维度为x轴,PCA降维的第一主成分为y轴,绘制的布局;(b) 采用非线性降维方法获得的结果

在这个例子中,作者们生成了一个包含100个顶点,9900条边和900个时间步的虚拟网络。图6、图7中,颜色由浅到深表示时间的推移。图6是采用PCA方法投影得到的布局,清晰的展现出四个稳定状态,一个重现状态和五个过渡状态。图7(a)展示的是将时间轴作为横轴的PCA投影结果,可以清晰的看到四个不同的稳定状态,且最下方的稳定状态出现了三次;图7(b)是采用非线性投影方法获取的结果,四个不同的稳定状态可以很好地被区分,但是,稳定态之间的转移过程没有展示出来。

Case2 – 真实数据(图8、图9、图10):

在这个例子中使用的数据,记录了一个学校五个不同班共180个学生为期7个工作日的面对面交流数据,一共有45047条记录。预处理后,得到的动态图网络中共有180个顶点,10104条边,2015个snapshot。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图8 非线性降维方法结果。不同的颜色表示不同的天,从浅到深,映射周一到下周二的时间信息。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图9 非线性降维结果。颜色表示不同的时间,从浅到深,映射早上6点到下午6点的时间。

图8、图9展示的是采用非线性投影方法获得的结果。两幅图的不同在于颜色编码方法不一样。图8编码的是从19日到27日;图9编码的是每天早上6点到晚上6点。从图8,我们可以发现每个工作日基本上都是连续的一条轨迹,其中每天都会在几个基本固定的时刻断开,作者们分析,这是因为上课,午休等导致的。从图9,可以发现周三下午有异常,当天点的分布不连续,这是因为周三下午有一场考试导致的。

将每个时间步的图降维为点:动态网络可视化探索分析方法 (Reducing Snapshots to Points: A Visua...

图10 横轴映射时间信息,从周一到下周二;纵轴是PCA降维的第一主成分;颜色映射了早上6点到下午6点的时间信息。

图10展示的是在PCA投影中,将横轴替换为时间轴的结果。从图10,可以看到七个工作日网络的规律性变化。早上开始逐渐变的活跃,中午活跃度降低,下午又开始活跃,直到晚上恢复完全的平静。而周六周日,因为没有数据,都处于平静状态。

这篇文章是2015 VIS 的 Best Paper。文章提出的想法以及采用的方法并不复杂,但效果很不错。

1)  将每个时间步的网络看成高维的顶点,将其投影到二维平面,进而分析每个时间步,网络的相似性。这个方法可以有效的帮助用户分析探索动态图中的稳定状态,重现状态,异常状态以及状态与状态之间的转移情况。

2)  文章的一个特色是,对方法中可能的情况进行了充分细致的讨论,比如离散化中时间窗重叠率,归一化中归一化方法对投影结果的影响,投影中不同投影方法,距离度量方法。

3)  在虚拟数据和真实数据上讨论说明方法的有效性。虚拟数据的结果更为漂亮,吸引人,从理论上说明了方法的可用性;真实数据上的分析,进一步证明了方法的实用性。

动态图的可视分析,因为时间步长,每个时间步顶点多,边密集,挑战较大。传统的Small Multiples 和Animation方法,都不能很好地协助用户分析网络的变化情况。将每个时间步的snapshot转化为二维平面的顶点,通过分析二维平面上,顶点之间的远近,来分析snapshot之间的相似程度,进而分析网络的变化模式。从宏观的角度分析大型网络的变化模式,是个很好的切入点。

正文到此结束
Loading...