论文：TimeCrunch: Interpretable Dynamic Graph Summarization
作者：Neil Shah, Danai Koutra, Tianmin Zou, Brian Gallagher, Christos Faloutsos
发表：ACM SIGKDD 2015
介绍
怎样描述一个很大的动态图，或者说我们怎么去找出现实中动态图的一些模式，我们怎么评估它们的重要性。这就是这篇文章要解决的问题。纵然有许多的图算法适用于各种情况，但是传统聚类和社团搜索的目标并不是我们现在要追求的。何况它们也不能给出输出的特性的描述。
基于此，本文提出了TIMECRUNCH的算法，把动态图按照有时序标志的静态图的组合，找出成本最小的表示，并从中找出想要找的模式和特殊结构。而且最终，作者应用TIMECRUNCH分析大的动态网络，找到了多种模式和异常状态，这些表明了现实图确实展现了时序结构。
与之前的一些常用方法相比较。TIMECRUNCH可处理多种形式的图。
相关工作
与之相关的工作，包括，静态图的挖掘，动态图的挖掘，以及图的压缩和摘要。
首先是本文的第一个要点，问题的公式化。作者首先把动态图的的摘要定义为了一个压缩的问题，用MDL方法。Minimum Description Length（MDL）的原理是成为柯氏复杂性即最小描述长度。把模型用M表示，也就是找出对于观测到的数据 D最优的模型M ，使得L(M)+L(D|M）最小，其中L(M)是描述M的编码长度， L(D|M）是用M描述D的编码长度。
对于一个时间步长为 t 的动态网络G，我们把它视作每个时间点的静态图的集合。
考虑时序组成 Φ=Δ×Ω，其中Δ代表了时间签名的集合， Ω代表静态结构标志的集合， × 代表了笛卡尔集乘法。作者选取了5种时间签名和6种常见的结构。因此 就是一个5×6的集合。
之后就是对于模型M的编码方法。把编码分为两个部分，模型的编码和误差的编码。模型的编码也分为两个部分的编码，一是连通性的编码，二是时序表示的编码。联通性的编码成本是对每个时间步上的子图的连通性的表示成本。时序表示的编码是对时序标志的集合 的五种标志的进行表示的成本。
同样的，误差也分为了两部分，一是连通性编码表示带来的误差，二是时序编码表示带来的误差。其中时序编码的误差是由编码重建的时序步与原始的时间步的差异造成的。
算法
接下来，就是作者提出的TIMECRUNCH的算法。
其中， Gi表示第i个时间步上的静态图。x表示 Ω中的一个标记，p是 Φ中的一个元素，是结构标记和时间签名的一个组合。
正如图中所示，该算法大致分为四个步骤
首先，是图的输入，它把每个静态的图用传统的静态图分解方式划分为一个个更小的子图。接下来根据之前的结构标志的分类对每个子图打上标签，并使它的表示成本最小。
之后，把各个时间步上静态图结合起来，并且选择适合的时序标志使得组成连贯连接的图，并加入到候选集中。最后，用不同的启发式方法，VANILLA, TOP-10, TOP-100和 STEPWISE比较不同的模型M，选择使得总的编码成本最小的模型M。
为了展示这一算法优秀，作者提供了几个不同的动态图的例子，如下
五种图有着不同的结构。
我们直接来看结果：
ORIGINAL代表表示原始图所用的比特，后面的四列分别代表不同的压缩规模。括号里的数字代表了找出的特殊结构。
上图是对于找出的一些特殊模式的展示。时间上，以DBLB为例，其运行时间随便的数目的增长近乎线性增加。
总结
总结一下，本文所提出的这种方法，对于图的压缩存放是有一定的作用的，当然更重要的是它还可以发现一些特殊的模式，而且对于各种结构的动态的适用性也不错。
✉️ zjuvis@cad.zju.edu.cn