动态社区发现算法综述

RossettiG,CazabetR.Communitydiscoveryindynamicnetworks:asurvey[J].ACMComputingSurveys(CSUR),2018,51(2):1-37.

背景介绍

动态网络网络模型

时序网络

网络快照

时序网络和网络快照的对比

（2）与TNs不同，SNs是由聚合的数据组成的，因此一个SN上处理的典型复杂性取决于所选择的聚合级别和生成快照的大小（节点/边的数量）。例如，SNs上的DCD方法通常需要在每个快照上运行一个社区发现。在t+1时运行CD算法的成本通常不依赖于在t和t+1时SNs之间的变化数量。然而在TNs上运行社区发现通常主要依赖于网络变化的数量，而不是粒度或节点总数。

网络记忆

动态网络社区发现问题的定义

社区生命周期（communitylifecycle）

并非所有转变都必须由一个一般性的DCD算法处理。其中，merge,split和resurgence通常有特定的相似度和阈值函数，以及社区转换策略。例如，当选择合并两个社区时，可以遵循Absorption和Replacement两种策略。

文中图3展示了一个社区生命周期的例子。

动态网络社区发现算法

即时最优算法（InstantOptimal）

步骤：

Step1：初始化：为网络的初始状态确定社区结构。

优点：该方法能够处理即时最优算法造成的不稳定问题。此类的大多数方法能够利用t-1时刻的现有社区结构来加速t时刻的社区检测。

步骤（网络转换方法示例）：

Step1：网络转换：将连边分为两种属性，同一时刻的连边和相邻时刻的连边。

优点：这类算法不会遇到社区不稳定和社区漂移问题。从理论上讲，这类方法更有利于处理局部异常和社区演化缓慢的问题。

缺点：该方法受到需要限制，比如需要固定社区数量以及缺乏社区的合并或拆分等操作。

社区发现算法的主要问题之一在于缺乏对社区的定义，每个学者都遵循自己的策略，将其算法获得的结果与其他最先进方法产生的结果进行比较。通常，在具有相似特征的方法之间进行比较：优化相同质量函数（modularity,conductance,density等）。本文在第5.1节中，描述了如何使用合成网络生成器来设计受控实验。在该章节介绍了基于它们的两类基准：静态和动态基准。在5.2节中讨论了评估社区质量的两类方法：内部评估和外部评估。