动态聚类（ Dynamic clustering）

本节摘自2016年Santo发表在《PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS》上的一篇综述文章，目前在SCI数据库中引用量接近两百，被评为热点论文和高被引论文。

由于带有时间戳的网络数据的日益增长，目前分析时序网络[2012Holme]的方法有了很大的发展。尤其是动态社区检测（community）的问题引起了很多人的关注[2010Fortunato,2011Myra]。

应用在静态图上的聚类算法通常也可以用于动态网络，我们需要做的就是如何处理社团的进化。社团进化通常可以被描述为一系列的快照（snapshot） ，每一个快照对应着一个给定的时间窗口中图的配置[注1]。下面有两种策略：

[注1]图的配置包括在给定的时间窗口内**的一系列顶点和边，以及他们在该窗口内的交互强度（权重）和动力学的其他方面，如突发性，交互持续时间等。

A graph configuration consists of the sets of vertices and edges that are active within the given time frame, along with the intensity of their interactions in that frame (weights) and possibly other aspects of the dynamics, like burstiness , duration of the interactions, etc.
 

最简单的方法是将每一个快照看作一个静态图[2004Hopcroft,2007Asur,2007Palla]，在上面检测社区结构，然后将连续窗口上的社区关联起来。通常的流程是使用如Jaccard相似系数[Eq.(6)2007Palla]来发现在时间窗口t上的cluster在t+1上最相似的cluster。这样，每个社区在网络演化的每个阶段都有一个图像（Image），并且可以跟踪其动态。社区变化有很多种可能，可能在某一时间点消失，新的社区会出现，这两种情况分别会在顶点和边的删除（exclusion）或者新加入（introduction）时出现。除此之外，一个cluster可以分割的更小，或者与其他的合并。然而，由于快照是单独处理的，特别当数据集有噪音的时候，this strategy often produces significant variations between partitions close in time。

最好的方法是能有一个统一的框架，在这个框架中，社区是从当前图的结构和之前的社区结构推断出。（communities are inferred both from the current structure of the graph and from the knowledge of the community structure at previous times）这种策略的一个有趣的实现是evolutionary clustering[2006Chakrabarti]。该方法的目标是找到一个划分既能体现t时刻快照，又与t-1时刻快照的划分有联系。这里引入了一个成本函数，该函数的优化目标在这两个约束中进行平衡。在实践中做到这一点有很大的灵活性。许多用于静态图的聚类方法都可以在这个演化框架中重新制定（reformulated）。许多基于进化聚类的有趣算法被提出[2007Chi,2008Lin]。Mucha等人还提出了一种基于模块度的连接系统不同快照上的配置的方法[2010Mucha]。（Mucha et al. have also presented a method that couples the system’s configurations of different snapshots, within a modularity-based framework）在得到的质量函数（多层模块度），所有的配置被同时考虑，他们之间连接用一个可调参数表示。这个方法适用于多层网络[2014Boccaletti,2014Kivelä]，其中每层要么是顶点通过特定类型的边连接的网络（例如，在社交网络中，友谊、工作关系等），要么是顶点与其他网络/层的顶点有连接（交互、依赖）的网络。另一方面，由于这种方法基于模块度优化，因此存在分辨率问题。

一致性聚类（Consensus clustering）理所当然是一种通过组合多个快照来寻找稳定的动态社区的方法。我们假设一个时间范围从到，时间窗口w的大小为。为了稳定性起见，应考虑滑动窗口，即有重叠的时间间隔。这种方法连续的划分将建立在共享大量顶点和边的系统配置上，并且改变（通常）是平滑的。为了获得准确的w个窗口（frame），每一个窗口都要shift通过一个关于上一帧的时间间隔。我们获得时间窗口。每一个快照上的社区结构都可以通过任何一种可靠的静态聚类技术来发现。接下来，选择适当的r个快照，从r个连续快照中的聚类中得到一致性划分[2012Lancichinetti]。再次的，我们需要考虑滑动窗口：比如，第一个窗口由第一个r个快照组成，第二个窗口由2到r+1组成，以此类推直到最后r个快照的组合。在图1中，我们展示了这种方法在美国物理学会期刊论文引文网络中的应用。

另外一种发现动态社区的方法是使用一种概率模型来计算相邻时间间隔配置（configurations）之间的相关性[2005Sarkar,2009Yang,2015Tiago,2017Tiago]。

如果系统非常大，而且它的结构以流的方式更新，那么每当系统的配置因新信息（如添加新的顶点或边）而发生变化时，就可以在线检测集群，而不用处理快照[2005Aggarwal,2008Zanghi]。这种方法的一个优点是，系统的变化是由于网络结构的微小变化影响，因此可以通过调整前一个配置的划分来跟踪这些变化，这样处理速度就会更快。

图1.动态网络上的一致性聚类。美国期刊论文引文网络聚类的时间演化。选取论文标题中出现频率最高的15个词中，“Network(s)”的聚类。除了图的最右端的时间窗口，使用Infomap[2008Rosvall]在每个5年窗口的快照上检测社区：因为缺失2008年以后的数据，最后一个窗口必须以2008年为上限，因此将其大小缩小（2004-2008,2005-2008,2006-2008,2007-2008）。每一个竖条代表一个由成对的连续快照组成的一致性划分（consensus partition）。一个颜色唯一的标识一个社区，聚类之间的空白的长度与它们共有的论文数量成正比。Complex Networks领域的迅速发展显而易见，之后将其划分为多个子主题，如Community Structure，Epidemic Spreading，Robustness等等。

来源：[2012Lancichinetti]

没有直接全部翻译，只是翻译了大概。