动态图可视化对复杂网络分析等能起到关键作用，但由于动态图数据的复杂性，其演变过程的可视化形式一直难以确定，整体而言一般分为动画(Animation)和时间线(Timeline)两类。这个工作提出了一种用持续同调(Persistent Homology)来衡量动态图结构变化特性的方法，在此基础上提取特征以时间线的形式进行可视化，揭示动态图的异常变化和整体演变过程[1]。持续同调是拓扑数据分析(Topological Data Analysis, TDA)的主要工具，是近年探索性数据分析和数据挖掘领域中逐渐活跃的方向，有深刻的代数几何背景，将其引入可视化的特征提取是一次全新的尝试。
TDA的基本流程(来源：维基百科)
对于经典的拓扑数据分析简介及理论，可查看[2]，[3]。这个工作在此基础上有流程如下：
- 定义度量空间，计算结点间的距离。
- 分别计算0维和1维持续同调表(Persistent Diagram)，将其转换为高维向量作为每个时间步上图(Graph Instance)的特征。
- 根据特征定义度量空间，计算全局的距离矩阵。以此进行多维缩放投影(Multidimensional Scaling, MDS)，得到主要视图，辅之以力导算法布局的交互。
- 聚类，提取动态图的周期性质。
在文中，结点距离实际使用的是最短路径距离(Shortest Path Distance)和基于图拉普拉斯矩阵(Graph Laplacian)的Commute Time Distance。而持续同调特征的距离使用的是Bottleneck Distance和Wasserstein Distance。
基于持续同调特征的动态图可视化形式。横轴代表时间，纵轴代表特征的1维MDS投影。
在案例分析中，作者使用了两个真实数据。第一个是高中交流数据集[4]，第二个是邮件记录数据集[5]。在前者中，通过查看时间轴和相应的图，能够看到一天内的基本模式，如特定时间点的表现。并且通过对比不同的星期，可以总结出各天交流的差异；而在后一个数据集中，通过聚类，可以得到各周的邮件往来基本情况和异常的周，理解数据的周期性模式。此外，还能直接观测到持续时间较短的剧烈变化事件如节假日等。利用这两个数据，作者也说明了0-，1-持续同调表作为特征的直观性以及Bottleneck和Wasserstein距离的特性。前者捕捉极端情况，后者侧重于全体的平均表现。
为了说明这套可视化方法的合理性与有效性，他们在小规模的动态图模拟数据上进行了一系列对比实验，验证了持续同调表作为特征具有以下性质，符合人的直觉与既有的动态图可视化准则。
- 敏感于图连通性的改变；
- 改变的边权值越高，前后差异性越大；
- 图越稀疏，边的改变带来的影响越大于稠密的图；
- 随机的变动带来的差异小于有定向的变动；
- 删除的结点越多，前后差异性越大；
- 稳健性：小型的扰动不会带来巨大差异；
总而言之，这个工作基于持续同调方法，为动态图可视化的特征提取提供了一种新颖且有效的思路，也为拓扑数据分析在可视化领域的应用开启了一扇窗口。
参考资料
[1] Mustafa Hajij, Bei Wang, Carlos Scheidegger, Paul Rosen. Visual Detection of Structural Changes in Time-Varying Graphs Using Persistent Homology. In Proceedings of IEEE Pacific Visualization Symposium (PacificVis 2018), Kobe, Japan, Apr. 10-13, 2018.
[2] 知乎专栏·澎湃科技·拓扑数据分析
[3] H. Edelsbrunner and J. Harer. Persistent homology – a survey. Contemporary Mathematics, 453:257–282, 2008.
[4] J. Fournet and A. Barrat. Contact patterns among high school students. PloS one, 9(9):e107878, 2014.
[5] Snap: mail-Eu-core network, http://snap.stanford.edu/data/email-Eu-core.html
评论关闭。