Wavelet-based Visual Analysis of Dynamic Networks

  • 论文原文：Wavelet-based Visual Analysis of Dynamic Networks
  • 作者：Alcebiades Dal Col, Paola Valdivia, Fabiano Petronetto, Fabio Dias, Claudio T. Silva, Senior Member
  • 发表刊物/会议：2017 TVCG
  • ps: 语法错误这么多的文章不知道是怎么发出来的，大概是真的实力强劲

个人评述

作者主要提出了一种利用小波变换的结果，对动态图进行可视化的方法。有几点亮点：

  1. 动态图转化成静态图的方法：通过在时序上相邻的两个图之间增加时序边的方法，将一系列动态图组合成一整个图，再对该图进行小波变换
  2. 小波变换对突变的检测：利用小波变换的高频部分来检测动态图中存在的突变。
  3. 制定的四个目标，基本上包含了动态图可视化中所存在的任务：
    • 目标1：将网络当做整体来进行分析
    • 目标2：对每个节点的分析。
    • 目标3：重要节点的辨认。
    • 目标4：相似节点的辨认。
  4. 详尽的usage scenario，甚至可能可以当做模板

为了阅读这篇文章，我花了一段时间补习了傅里叶变换、小波变换、谱图理论的相关背景知识，但读这篇文章的理论部分还是有点困难，想了很久。

接下去说说它的不足：

  1. 可视化设计简单：其几个视图的设计都异常简洁（或许其简洁也是其亮点），可视化设计方面没有太大的创新
  2. 文章上下文背景知识的补充不足：经常出现不明所以的结论，没有任何铺垫，比如：为何小波变换后，高频部分比较突出的节点可以视作突变节点？
  3. Motivation的不足：可能多讲一些动态图可视化背景来引出4种目标会更好

启发：

  1. 图嵌入算法对于动态图可视化的帮助：很多向量化的方法事实上同时捕捉到了全局和局部的特征，比谱图理论（小波变换）更容易解释，反而对动态图可视化更有帮助
  2. 小波变换对于异常检测的意义：对突变的检测是否精准，有待验证。

介绍

动态网络介绍+谱图小波理论的优势（模式挖掘，噪声移除，信息压缩）

本文的工作：用图小波来对动态网络进行可视分析，特别是对局部特征变换的分析。

贡献：

  1. 基于小波变换的动态网络探索方法，识别动态网络中不规律的、微妙的以及突现的拓扑信号变化；
  2. 一个交互式的可视分析工具，引导用户了解动态网络中的模式和现象，并降低探索整体和局部间探索的隔阂
  3. usage scenario

这篇文章是上一篇做静态图的文章的引申。

谱图理论

这一部分，可以见我的另一篇博客，我将这部分做了单独的阐释：图的小波变换

图小波对动态图进行可视分析

主要涉及两个问题：

  1. 如何定义节点的信号
  2. 对一组时间序列内的小波分析结果进行了表示

动态图模型

作者将一系列的动态图相互串联（两个邻时刻同样的点之间，用临时的边进行链接，如图中的蓝边），以形成一整个图，从而应用图小波变换对其进行分析。

但并不是串联所有的动态图，作者在这里定义了一个时间窗口，在时间窗口内的图会被串联起来（比如5分钟）

image-20180624215039214

节点信号和边权重

节点信号的定义和边权重的定义都对分析有着重要影响。

比如：

  • 在对纽约市的出租车的场景分析中，节点表示了一个区域，而节点的信号则对应这个区域的出租车接客数量，网络中的边则是两个区域之间的乘客上下，边权重则是接送的乘客数量。
  • 而在另一个场景分析中，作者将人转换成节点，节点信号则是一段时间内这个人的人际交往数量，也就是该节点的度数。

总而言之，如果自己定义信号，用图小波变换进行可视分析则是对节点的某个特征在拓扑空间和时间上的分布进行的分析。如果没有定义，那么就是对这个节点的拓扑信息进行了分析。

还可以控制那些不同时间片段的图之间的连接边的权重，用来控制分析过程中时间的影响。

节点分类

每个节点都用一个特征向量（feature vector，并非eigenvector）来进行分类，这个特征向量事实上就是小波系数$FV_j=(S_f(j), W_f(s_r,j), \ldots, W_f(s_1, j))$。

减少噪声：每个时间片中的孤立节点会被分配为0类。

分类方法：机械扭矩。类似于将特征向量的各个值放在跷跷板上，看这个跷跷板往哪边偏，来判定这个特征向量主要是低频的还是高频的。

image-20180624223752644

分类的这种方法，比直接解释系数容易的多。一共分成五类：

[-1, -0.3), [0.3, -0.05], [-0.05, 0.05), [0.05, 0.3), [0.3, 1]，编码从深蓝到红色。image-20180624225101805

红色的节点，代表了信号的突变（时间和空间邻域上），但作者并未解释为什么高频代表了突变。

可视化

宗旨是为了能够发现动态网络中的pattern以及这些pattern是如何随时间演变的。

  • 目标1：将网络当做整体来进行分析
  • 目标2：对每个节点的分析。
  • 目标3：重要节点的辨认。
  • 目标4：相似节点的辨认。

四个界面：

image-20180625001348008

  • Netowok Analyzer：对网络整体变化的一个概览
  • Time Slice View: 对某个时间片段的详细分析
  • Node Ranking：识别某个时间片段的相关节点
  • Node Time Series：对某个节点进行详细分析

Network Analyzer

每个时间片段被编码成一个圆，圆的垂直位置由包含的节点的信号值总和给出，节点颜色则是最大类的颜色。需要明白的是，这里的最大类并不是说当前时间片段包含节点最多的类，而是相对于该类在其他时间包含的节点数而言最大。

Time Slice View

对某个给定的时间片的节点，做了力引导。之后花了篇幅讲解了这个视图的有效性。

image-20180625001408755

Node Ranking

对节点与该时间片段的相关性来排序。被标记为红色或者橙色的节点，才会认为这种节点和当前时间片会相关。

Node Time Series

展示了某个特定节点随着时间的变化。