动态社区发现算法综述

  前情回顾：上一篇关于社区发现算法的综述推文在这里。

  今天要跟大家分享的文章发表于2018年，是近几年动态网络社区发现领域比较全面的一个综述类的文章。

Rossetti G, Cazabet R. Community discovery in dynamic networks: a survey[J]. ACM Computing Surveys (CSUR), 2018, 51(2): 1-37.

背景介绍

  复杂网络（complex network）是一种的用来描述和分析现实世界中发生的交互现象的常用工具。例如社会关系的形成，经济交易，面对面的交流等事件通常是借用图论进行研究的。在研究这类事件时，需要解决的一个主要问题是识别隐藏在整个复杂系统中的有意义的子结构，将复杂网络划分为社区是一个有意义的研究问题。

  然而大多数关于社区发现（community discovery，CD）文献都是从一个非常严格的假设开始的，即现实世界的现象可以用静态网络来建模。不幸的是，这种简化的情景很少符合世界不断发展的本质。因此，过去十年中出现了一个全新的研究领域：动态网络分析。人们重新制定了在静态环境下定义的问题，并提出了能够解决这些问题的时间感知方法。

  其中，动态社区发现（dynamic community discovery，DCD） 是最具挑战性的问题之一。随着时间的推移，节点和边可以在一个动态网络中出现和消失。动态方法致力于跟踪这些局部拓扑及其转变。

  最后，作者指出本文的主要工作：根据识别时间感知的网络子结构的策略来设计DCD算法的分类，并讨论了每一类DCD算法的优点和缺点。此外，文章还提供了算法的基本原理的简要描述、DCD算法的评价、DCD的其他工作（如动态社区可视化方法）以及对现实问题的分析应用。

动态网络

网络模型

  时间在网络拓扑的形成中起着至关重要的作用。因此，在时间演化网络上解决的一个重要问题是与用来描述它们的数学形式主义有关。

  文章的图1显示了在网络建模过程中逐步引入时间维度的四种不同的方案。随着模型表达能力的提高，分析的复杂性也随之增加。文章重点介绍了时序网络（temporal networks，TNs）和网络快照（network snapshots，SNs）这两个最常使用的模型。

1. 时序网络

  时序网络是一个图，其中是一个三元组，是网络的一个节点， 分别对应该节点的出生和死亡时间戳，且；是一个四元组，是网络的节点，分别为对应边的出生和死亡时间戳，且。

1. 网络快照

  快照图是由有序集定义的，其中每个快照是由节点和边的集合单独识别。

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

  文章指出TNs和SNs之间的差异与模型施加的约束紧密相关：选择使用TNs而不是SNs（或反之）可能对数据存储和设计分析的处理部分产生重大影响。特别是：

  （1）如果原始数据已经描述了网络演化的精确状态（即每周/每月/每年对系统进行一次完整的抓取），那么采用快照模型显然是很自然的。然而如果有更精确的时间信息（例如，具有有限精度时间戳的电子邮件、朋友列表或电话数据集），则TNs和SNs都可以考虑。

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

网络记忆

  通常考虑两种主要场景：完美记忆网络（或累积增长场景）和有限记忆网络。在前一种情况下，节点和边只能加入网络，旧的节点和边不会消失（如发表论文的引文网络）。在后一种情况下，节点和边会随着时间的推移而消失。

  生存时间（time to live, TTL）是人为定义的一条边的持续时间。文章介绍了4种 TTL：Fixed-size static time window、Fixed-size sliding time window、Dynamic-size time window和(Global/local) decay function，具体含义可以参考文章的2.2节。

动态网络社区发现

问题的定义

  文章首先给出了社区（community）的定义：A community in a complex network is a set of entities that share some closely correlated sets of actions with the other entities of the community. We consider a direct connection as a particular and very important kind of action.

  接着，文章给出了动态社区发现（dynamic community discovery）的定义：Given a dynamic network , a dynamic community is defined as a set of distinct (node, periods) pairs: , with , with . aims to identify the set of all dynamic communities in . The partitions described by can be neat as well as overlapping.

  通过这种一般性的定义，两个主要的分析目标可以被确定，分别是 （1）能够有效地识别进化的每个瞬间的最佳分区；（2）构建描述社区生命周期的进化链。

1. 社区生命周期（community life cycle）

  大多数关注社区跟踪的工作都认同一组涉及动态网络实体的简单动作：节点/边出现和消失。事实上，这种操作会扰动网络的拓扑结构，从而影响CD算法产生的结果。文中图2展示了8种社区转变方式，分别是Birth、Death、Growth、Contraction、Merge、Split、Continue和Resurgence。

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

  文章还给出了社区生命周期（community life cycle）的定义：Given a community , its community life cycle (which univocally identifies ’s complete evolutive history) is composed of the directed acyclic graph (DAG) such that (i) the roots are birth events of , and of its potential predecessors if has been implicated in merge events; (ii) the leafs are death events, corresponding to deaths of and of its successors, if has been implicated in split events; and (iii) the central nodes are the remaining actions of , its successors, and predecessors. The edges of the tree represent transitions between subsequent actions in life.

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

社区不稳定和时间平滑

  动态社区发现方法遇到的主要问题之一是解决社区发现的不稳定性。这种类型的问题来自于社区的本质。我们不知道在网络上t时刻发现的社区与t + 1时刻发现的社区之间的差异是由于社区的演化还是算法的不稳定性造成的。人们提出了各种各样的解决方案来解决或减轻这种不稳定性问题。他们的共同目标是使社区的进化更加平稳。文章列举了4种主要方法，分别是smoothing by bootstrap、explicit smoothing、implicit smoothing和global smoothing。

动态网络社区发现算法

  在该文章中，作者将动态网络发现算法分为了三大类，分别对应不同的动态社区定义。如下图所示，分别是即时最优算法、时间权衡算法以及跨时间算法，其中每一大类中又分为多个小类。针对每一个算法，该文章讨论了其优缺点。

即时最优算法（Instant Optimal）

  第一类方法即时最优算法认为t时刻网络中存在的社区结构仅取决于t时刻网络的状态。在进行社区匹配时，或许会考虑到之前时刻识别出的社区结构。但是在t时刻识别的社区结构是基于t时刻网络拓扑结构的最优选择，因此该方法是非时间平滑的。

  该类方法直接源自将静态网络社区发现方法应用于动态情况。针对网络演化的不同步骤分别进行识别，为每个步骤确定一个最佳分区，如图 5 所示。然后连接不同演化步骤中发现的拓扑结构，识别出社区的动态演化过程。

1. 步骤：

Step 1：识别：在演化的每一个步骤识别静态社区

Step 2：匹配：将在t时刻识别出的社区与在t-1时刻识别出的社区对齐。

1. 优点：该方法建立在现有静态网络社区发现相关工作的基础上，针对每一个演化步骤可以采用常用的静态网络社区发现算法确定网络结构。社区匹配过程也有既有文献可寻。最后，该方法很容易实现并行化。

2. 缺点：该方法的主要问题在于社区发现算法的不稳定性，同一算法在同一网络上也会识别出不同的社区结构。目前通过研究社区最稳定的部分来规避这一弱点。

3. 子分类：该过程的第一步，即在每个演化步骤识别相关社区，通常可以使用任何静态网络社区发现算法来完成。但是，用于匹配在不同演化步骤发现的社区的方法有所不同。文章确定了三个子类，分别是基于迭代相似性（Iterative Similarity-Based Approaches），基于迭代核心节点（Iterative Core Nodes–Based Approaches）以及多步匹配（Multistep Matching）。

时间权衡算法（Temporal Trade-Off）

  第二类方法时间权衡算法认为t时刻网络中存在的社区结构不仅仅取决于网络当前的拓扑结构，还与拓扑结构的演变以及过去时刻的识别出的社区结构有关。因此，t 时刻的网络社区结构由t时刻的网络拓扑结构和已知过去的信息决定，其不依赖于未来的信息，该方法是时间逐步平滑的。

  该类方法通过迭代的方式确定社区结构，其考虑了在上一个演化步骤中找到的网络和社区结构，以识别当前步骤中的社区，如图6所示。

1. 步骤：

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

Step 2：更新：对于每一个演化步骤，使用步骤t时网络的拓扑结构和过去的信息在步骤 t 处识别社区。

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

2. 缺点：首先，无法简单进行并行操作。并且由于在每次迭代中，识别出的社区取决于之前的社区结构，因此时间权衡方法面临雪崩效应的风险，可能会出现社区漂移的问题。

3. 子分类：该方法确定了四个时间权衡算法的分类，分别是全局优化更新算法（Update by Global Optimization）、依规则更新算法（Update by a Set of Rules）、多目标优化算法（Informed CD by Multiobjective Optimization）、网络平滑算法（Informed CD by Network Smoothing）。前两个算法通过全局优化更新或通过一组规则更新，包括使用全局或局部方法更新在上一步找到的社区结构。最后两个算法通过多目标优化以及网络平滑方法，从头开始对每个快照进行社区检测，同时考虑来自先前演化步骤的信息。

跨时间算法（Cross-Time）

  第三类方法跨时间算法在研究网络演化时，不单独考虑网络演化的不同步骤，直接为整个网络识别社区结构。在t时刻的社区结构取决于过去的信息和未来的演变。该方法是完全时间平滑的。

  跨时间算法不单独考虑网络演进的不同步骤。相反，动态网络社区发现算法在单个过程中完成，同时考虑网络的所有状态。此类方法如图7所示。

  该类方法有多种不同实现步骤，比如基于网络转换的方法，基于张量分解的方法等等，文章中提出了一个基于网络转换的例子：

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

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

Step 2：社区检测：在这个横向网络上运行静态社区发现算法，识别的社区包含属于不同时间步骤的节点，可解释为动态社区。

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

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

3. 子分类：该文章将其分为四类：分别是固定成员资格、固定属性（fixed memberships, fixed properties）；固定成员资格，不断演化的属性（fixed memberships, evolving properties）；不断演化的成员资格、固定属性（evolving memberships, fixed properties）；不断演化的成员资格，不断演化的属性（evolving memberships, evolving properties）。

指标评价

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

动态网络社区发现算法的应用

现实世界中常见的动态网络

  文章介绍了现实世界中常见的动态网络，比如：合作网络（Collaboration networks）、在线社交网络（Online/offline social networks）、通信网络（Communication networks）以及技术网络（Technological networks）。表1-表4提供了上述网络的相关研究。

网络可视化

  动态网络可视化是一个值得注意的问题，该文章将网络可视化分为两大类，分别是动态可视化（图9）以及总结整个网络/社区演变的静态图（图10）。文章还提供了几个经典网络可视化的例子（图11-12）。

未来展望

  文章最后总结了社区发现算法面临的主要问题：（1）动态网络社区发现算法存在的悖论：在不同网络演化步骤中发现的“最佳”分区并不是总能形成一个连贯的动态结构；（2）缺乏评估和比较不同方法的基准数据；（3）缺乏系统评估方法；（4）很少有人提出动态网络发现算法在具体问题上的应用。

- END -