改进的动态图社区演化关系分析方法

罗香玉 ，李嘉楠 ，罗晓霞 ，王 佳

（1. 西安科技大学计算机科学与技术学院，西安710054； 2. 西安交通大学电子与信息工程学部，西安710049）

0 引言

随着网络技术的发展和用户对网络的访问增加，人们的社会关系从现实世界映射到了虚拟网络世界。许多社会关系和生物系统都可以表示为复杂网络［1］，其中节点表示实体，边用来模拟实体之间的交互［2］。复杂网络在各领域广泛存在，在研究复杂网络的过程中人们发现了社区结构属性。在社区结构中，网络节点以一个组的形式紧密地连接在一起，而组之间的连接特别松散。对于现实生活中的社交网络来说，网络中的成员和成员之间的关系和社区结构都会不断变化，社区结构动态特征的分析和预测引起了不少研究者的关注［3-4］。

社区结构是社交网络［5］中一个十分重要的基础结构，社区结构的动态演化对网络的变化有着很大的影响［6］。很多科研机构和研究者在这一领域展开了深入的研究。目前有大量的方法来分析和预测动态社区的演化。在追踪社区演化关系时，目前的主要方法是对相邻时间片内社区结构的关系进行比较分析。但这类方法中存在很多问题，如：1）数据质量会影响计算结果的有效性；2）时间窗口设定影响是否能在可接受的计算复杂度范围内捕捉全面的社区演化信息；3）对社区质量和社区的演化情况缺乏一个统一的标准来评判；4）网络是不断变化的，分析动态网络社区结构对计算性能带来了很大的挑战［7］；5）社区演化关系刻画的完备性问题。

本文通过实验证实，仅对相邻时间片内社区结构的关系进行分析，无法完备地刻画社区演化过程；现有的方法在描述社区演化过程中，会忽视一些不明显但真实存在的社区关系。针对这些问题，本文提出了一种改进的方法，可为描述社区演化关系提供更丰富的信息。

1 相关工作

目前解决追踪社区演化关系的社区检测和匹配方法是将静态社区检测方法［8］应用于动态案例。这类方法也被称为两阶段法，基本思想是独立地在每个时间片检测社区，然后基于社区之间的相似性将这些社区与它相邻的时间片中的社区进行比较。这类方法旨在通过动态网络生命周期中可能出现的关键事件来跟踪社区的演化［9］。

Hopcroft 等［10］使用静态网络时间片跟踪社区［11］随时间演变，提出了一种使用层次聚类来识别和跟踪稳定聚类的方法。Asur等［12］提出了一种基于匹配方法的简单直观的社区事件识别方法，该方法首先应用马尔可夫聚类算法［13］来发现社区，然后在连续时间片中比较每对社区的大小和是否重叠，并确定涉及这些社区的事件；但是它们并没有涵盖特定社区生命周期中可能发生的所有形式的事件。

Greene 等［14］提出了一个模型，该模型使用静态算法跟踪社区随时间的演化，以检测每个时间片上的社区，描述了一个加权的二分匹配来映射社区，然后用一系列事件来表征每个社区。然而，文章中并没有提供明确的公式来定义事件。模型引入了有效的社区匹配策略，用于在多个时间片中有效地识别和跟踪动态社区。Takaffoli 等［15］提供了一个基于事件的框架，以在两个连续时间片中捕捉社区之间的所有过渡。

Bródka 等［16］提出了一种社区进化发现方法，不仅使用社区成员的对等来匹配社区，还考虑到了节点的位置，及其在社区中的重要性，以便识别连续时间片中的社区演化。这种匹配方式既尊重了社区成员的数量，也尊重了社区成员的重要性。

Sun 等［17］提出了一种轻量级进化事件监测算法来寻找相邻时间片之间的社区进化模式，从统计学上来说，这可以显示整个网络的进化趋势，应用Louvain算法在每个时间片中找到社区，然后，建立了一个相关矩阵来描述时间步长t和t + 1中社区之间相对于时间片的关系，并根据该矩阵定义了检测进化事件的规则。Zhu 等［18］描述了一个事件重建框架，用于分析社区结构的动态特征；提出了社区属性的概念，并基于社区属性的观点重构了Asur等［12］提出的事件框架。

Liu 等［19］提出了一种动态社交网络中基于引力关系和社区结构的追踪社区演化方法，通过构造基本节点来初始化社区，其他节点迭代搜索划分到相应的社区，分析社区进化。Wang等［20］提出了一种基于拓扑势场中的影响范围分析，增量更新动态社区结构，根据拓扑势场中核心节点的变化来跟踪社区演化事件。徐兵等［21］提出了一种基于关联群演化相似度的社区追踪算法，通过对社区、核心成员的相似度进行加权，引入多部图来分析社区演化序列。

目前的研究工作主要针对连续相邻时间片之间的社区关系进行分析，忽视了不相邻时间片之间社区的关系。本文在现有研究的基础之上，利用社区演化中可能会发生的事件来追踪社区的演化，考虑任意不相同时间片之间社区的演化关系，从而收集更多的社区演化关系，以更完整地描述社区的演化过程。

2 定义

在说明社区演化关系之前，需要描述一些与社交网络有关的一般概念，如时间社交网络、社区定义和社区演化。

2.1 时间社交网络

时间社交网络G 是时间片Ti的集合，每个时间片实际上是一个单一的社交网络Ni(V，E)，其中：V 是一组顶点，E 是一组有向边。

2.2 社区的定义

随着人们对网络研究的深入，根据网络的物理性质和数学特性，人们发现了真实网络中的一个共同的性质，即网络中都存在一种结构——社区结构。社区结构是指：在社区内部节点之间的连接比较紧密，社区之间的连接相对稀疏。网络可以用若干个社区的组合来表示。在网络中可以通过算法来确定社区，在本文中可以使用任何社区挖掘算法来提取社区。

经过近些年的研究，研究人员已从各种不同的角度提出了很多社区挖掘算法。其中K-团渗透法（Cluster Percolation Method，CPM）［22］和 标 签 传 播 算 法（Label Propagation Algorithm，LPA）［23］是两个比较经典的社区挖掘算法。

1）K-团渗透法。

K-团渗透法是第一个能够发现重叠社区的社区挖掘算法，重叠社区是指节点可以同时属于多个社区。重叠社区在现实生活是很有意义的，因为每个人都有着多种的社交关系。

团是指：团中任意两个节点之间都有边连接，并且该团不被其他的团所包含。K-团渗透法的思想是首先找出网络中所有大小至少为K的团，然后构建一个团图，每个最大团都是团图中的一个节点，如果两个团的节点集合C1与C2共享Min(C1，C2)- 1个邻居的话，它们在新图中的节点之间就存在边。最后团图中的每一个连通单元就是一个节点的社区，而它可能是重叠的。

2）标签传播算法。

标签传播算法是不重叠社区挖掘的经典算法之一。各个社区节点的集合没有交集的被称为非重叠社区。

LPA 的过程：初始时，给每一个节点一个唯一的标签；每个节点使用其邻居节点的标签中最多的标签来更新自身的标签；反复执行，直到每个节点标签不再发生变化为止。标签相同的节点在同一个社区。

2.3 社区演化

社区演化是一系列社区事件的变化，它们在社交网络中的连续时间片内彼此连续。社区事件的定义是描述社区演化的基础。

2.3.1 社区事件

研究社区演化的目的是分析和预测社区网络结构的动态特性，通常考虑和使用元素是社交网络的节点和边缘［13］。社区事件是指社区在演化过程中经历的变化。在追踪社区演化时，可以根据它的节点的情况，依据社区间的公共节点数量关系来表示社区事件。

2.3.2 社区事件分类

本文将社区事件分类为7 种事件，它们代表在两个不同时刻的时间片中社区的变化状态，如图1。令S表示社区节点的集合，用社区节点集合之间的关系来表示不同的社区事件。

1）社区继承（continuing）：两个社区相同，或者两个社区仅有少数节点不同但大小保持不变。

2）社区缩小（shrinking）：社区中的部分节点离开，使得社区规模比先前小。

如果和中部分节点相同，且的规模小于的规模，则称是的缩小。社区缩小可以表示某一个事物的热度降低等。

3）社区扩大（growing）：社区中加入新的节点，使得社区规模比先前大。

如果和中部分节点相同，且的规模大于的规模，则称是的扩大。社区扩大可以表示某一个事物 +y受到的关注越来越多等。

图1 社区事件示例Fig. 1 Community event examples

4）社区分裂（splitting）：一个社区中的一些节点或边消失，使社区分裂成多个部分。

如果和的并集与中部分节点相同，且和的规模小于的规模，则称和由分裂而来。社区分裂可以表示在一个大的研究领域中，不同的人对这个研究领域下的某一个更细致的研究领域更感兴趣。

5）社区合并（merging）：多个社区合并成一个社区。

如果和的并集与中部分节点相同，且和的规模大于的规模，社区合并可以表示不同种类的群组，为了完成某一个任务，而合并在一起共同合作。

6）社区消失（dissolving）：一个社区从网络中消失，该社区原本包含的节点不再属于该社区。t+y时刻中没有Sit+y使得

和中没有足够多的相同节点，则称在t+y时刻消失。社区消失可以表示一个临时的工作群组在工作完成之后，各自又回到原来的工作岗位等。

7）社区形成（forming）：出现了在先前时刻不存在的社区。t时刻中没有使得

和中没有足够的相同节点，则称在t+y时 刻形成。社区的形成通常意味着新事物、新话题或新团体的起源，“形成”事件有助于分析和把握网络的发展。

每一种社区事件的定义在现实中都有它独特且实际的意义，对应动态图可以很好地对社区的演化进行描述，从而分析动态图的发展。

3 问题描述

先前的研究将社区事件分类为多种类型，但只将它们用来描述连续相邻时间片之间一个社区或者多个社区的状态。虽然可以刻画出社区的演化过程，但这种刻画是不完备的，仅根据连续时间片之间的社区事件，无法推算出一些社区之间的关系。现举例进行说明。

以3 个相邻时间片和“扩大”“缩小”事件为例。图2 是3个相邻时间片中的某一个社区演化过程，箭头表示它们之间发生的社区事件。

图2 社区演化关系Fig. 2 Community evolution relationships

图2 （a）中，社区A 到社区B 经历了“缩小”事件，社区B 到社区C经历了“缩小”事件。根据社区点集之间的关系可以推导出，社区C是由社区A“缩小”之后得来。

图2（b）中，社区A 到社区B 经历了“扩大”事件，社区B 到社区C经历了“扩大”事件。根据社区点集之间的关系可以推导出，社区C是由社区A“扩大”之后得来。

图2（c）中，社区A 到社区B 经历了“缩小”事件，社区B 到社区C经历了“扩大”事件。如果仅根据点集之间的关系来推导社区A 和社区C 之间的关系，则会如图3 有三种情况：①社区C 与社区A 相同；②社区C 与社区A 是同一个社区，但社区C规模大于社区A；③社区C与社区A是同一个社区，但社区C规模小于社区A。此时已经无法仅根据它们之间的点集关系推导出来社区A与社区C之间的关系。

图2（d）中，社区A 到社区B 经历了“扩大”事件，社区B 到社区C 经历了“缩小”事件。社区A 与社区C 的关系同样无法仅由推导得出。如图4所示，也有三种情况。

传统方法获得的社区演化关系，可以描绘出动态社区的演化过程，但描绘不够全面。若遇到如图3 与图4 的情况，无法仅由推导得出社区之间的关系，而需要重新计算来确定两个社区之间的关系。社区演化过程描述得越详细完整，在分析社区演化时可利用的信息就越多，社区演化关系是分析社区演化的基础，所以在分析社区演化关系时要考虑到社区之间存在的各种关系。

图3 社区C与社区A的演化关系（a）Fig. 3 Evolution relationships（a）between community C and A

图4 社区C与社区A的演化关系（b）Fig. 4 Evolution relationships（b）between community C and A

4 改进的社区演化分析方法

在传统方法中，首先需要对动态社区进行社区挖掘，本文则将静态社区检测方法用于动态网络，然后比较相邻时间片之间社区的状态来确定一个社区事件。本文在传统方法的基础之上也考虑了不相邻时间片内社区之间的关系。

1）将网络的演化用时间片的集合来表示，将动态网络离散化为n个连续的时间片，每一个时间片都代表动态网络在某一个时刻的状态。

2）使用已有的静态社区挖掘算法对每一个时间片进行社区挖掘，本文中使用的静态社区挖掘算法为K-团渗透法。

社区挖掘结束后，根据社区事件类型的定义，匹配两个相应时间片内社区之间发生的事件。算法步骤如下：

步骤1 将时间社交网络G用若n个时间片T进行表示，时间片表示动态社交网络某一时刻的状态。时间窗口需要根据社交网络的结构特征和用户期望来划分，保证时间片之间能够获取重要的变化信息，同时尽可能减少计算复杂度。

步骤2 将步骤1 中划分的时间片按照其时间戳的先后顺序排列，记为G=｛T1，T2，…，Tn｝。

步骤3 使用静态社区挖掘算法对划分的每一个时间片进行社区挖掘，挖掘出各个时间片中所有的社区结构。

步骤4 获取每个时间片内的社区结构C，用社区集合的形式表示对应的时间片，记为T=｛C1，C2，…，Ck｝，其中C为社区结构内节点的集合。

步骤7 根据记录信息，描绘社区演化关系图。

5 实验与分析

5.1 实验数据

为验证本文方法的有效性，利用两种数据集对传统方法和本文方法进行比较。数据集描述如下：

第一组数据集为Contacts in a workplace［24］，该数据集为法国一栋办公楼中测得的个人之间的接触网络。该网络共88个节点，9 827条边，将数据集按时间戳的先后顺序划分为5个时间片，每个时间片代表24 h内个人之间的交流情况。

第二组数据集为2009 年法国会议数据集［25］，该数据集以社交网络的形式描述了405 位参与者2009 年6 月4 日到5 日在法国尼斯举行会议的面对面互动情况。该社交网络共405个点，70 216 条边，将数据集按时间戳的先后顺序划分为4 个时间片，每个时间片代表5 h内参与者的互动情况。

5.2 实验方法

首先，针对两个数据集，分别使用K-团渗透算法来挖掘每个时间片内的社区结构。表1为使用K-团渗透算法在每个时间片中挖掘出的社区数量。

表1 社区挖掘结果Tab. 1 Community mining results

然后分别使用传统方法及本文方法来分析社区的演化关系，实验结果如图5～8所示，其中：图5、6为采用数据集1时的结果；图7、8为采用数据集2时的结果。图中每个节点并非代表原始数据集里的节点，而是代表某个时间片里所挖掘出的一个社区。节点由其所属时间片和该时间片内社区的序号共同标识。例如2#0041，表示该节点为时间片2 中编号为41 的社区。节点之间的有向边代表两个社区之间所发生的社区事件；若节点没有边连接，则说明该社区只存在于某一时间片内。

按照事件类型，对上述社区演化关系图中发生的社区事件数量分别进行统计，结果如表2、3所示。

5.3 实验结论

由两个社区演化图比较得出，传统方法对社区演化关系的描述不够全面，而本文方法在描绘社区演化关系时提供了更多的信息。对于数据集1，本文方法的社区事件总数是传统方法的2.56倍；对于数据集2，本文方法中社区事件总数是传统方法的2.04倍。

图5 传统方法获得的数据集1的社区演化关系图Fig. 5 Community evolution relationship graph of dataset 1 detected by traditional method

图6 本文方法获得的数据集1的社区演化关系图Fig. 6 Community evolution relationship graph of dataset 1 detected by proposed method

图7 传统方法获得的数据集2的社区演化关系图Fig. 7 Community evolution relationship graph of dataset 2 detected by traditional method

图8 本文方法获得的数据集2的社区演化关系图Fig. 8 Community evolution relationship graph of dataset 2 detected by proposed method

表2 传统方法时间片间社区事件数Tab. 2 Number of community events in time slices detected by traditional method

表3 本文方法时间片间社区事件数Tab. 3 Number of community events in time slices obtained by proposed method

6 结语

动态图社区演化关系是分析动态图演化规律的一个重要环节。目前已经有大量的算法来分析动态图社区演化关系，但仅考虑相邻时间片社区之间的关系。这对于刻画动态社区的演化过程是不全面的，会遗漏一些比较重要的社区演化信息。本文针对这一问题提出了一种改进的社区演化关系分析方法，考虑任意不同时间片间社区演化关系。实验结果表明，本文方法可捕捉更多的社区演化关系，使社区的演化过程展现得更全面，也使一些不明确的社区关系明确，从而为更加准确地分析和预测动态图社区演化规律奠定了基础。