一、项目背景

许多社交网络中都隐藏着社区结构，社区内的用户联系紧密，而社区之间的用户联系较为稀疏。然而，随着时间的推移，社交网络会发生变化，仅仅对社交网络进行静态社区划分已经不足以刻画其结构特性，因此出现了动态社区划分方法。

目前，常见的动态社区发现方法分为独立静态式划分、基于演化聚类的划分和增量式划分。增量式划分是一种高效的动态社区划分方法，该类方法认为，在社交网络变化过程中，大部分拓扑结构是稳定的，仅有小部分结构会出现变化，以前一个时间片的社区结构为基础，动态更新增量节点的社区归属，即可获得当前时间片的社区结构。增量式划分方法在增量更新过程中难免会出现社区划分错误，并且前一个时间片的错误可能会导致后一个时间片更多的错误出现，造成错误累积。传统增量式动态社区发现方法忽略错误累积现象，影响了动态社区发现的性能。

二、技术方案

一种错误累积敏感的增量式动态社区发现方法，包括以下步骤：

根据给定的动态社交网络，预估第一个时间片后所有时间片的错误累积，计算所述动态社交网络的错误累积最佳阈值；

在第一个时间片，采用静态方法对初始时间片进行社区划分，获得动态社交网络的初始社区结构；

从第二个时间片开始直到结束，判断当前时间片的错误累积预估值是否超过错误累积最佳阈值，否，则重新进行社区划分，获得当前时间片社区结构；是，则动态更新增量节点的社区归属，获得当前时间片的社区结构。

错误累积最佳阈值的计算方法包括：

预估第一个时间片后每个时间片的错误累积；

针对预设的动态社交网络的错误累积阈值序列，基于每个时间片的错误累积，分别计算社区划分准确性和时间消耗的杠杆值LOCT；选取LOCT最大值对应的错误累积阈值，为动态社交网络的错误累积最佳阈值。

错误累积的预估公式为：其中，IEAt表示预估的当前时间片t的错误累积，t0为最近一次采用静态方法划分社区的时间片，ΔNi表示从t0开始的第i个时间片的增量节点个数，Ni表示第i个时间片的节点总数。

杠杆值LOCT的计算公式为：

其中，t为当前时间片，T为总时间片数，CCt为第t个时间片和最近一次采用静态方法重新划分社区结构的时间片之间的相关系数，freq为采用静态方法重新划分社区结构的次数，ratio为比例系数；

相关系数CCt的计算公式为：

其中，t为当前时间片，t0为最近一次采用静态方法划分社区结构的时间片；Et代表第t个时间片的边集合，表示t0时间片的边集合；IEAt表示预估的当前时间片t的错误累积，threshod为错误累积阈值；

比例系数ratio的计算公式为：其中，ΔEi为i时间片的增量边数，Ei为i时间片的总边数。

进一步地，从第二个时间片开始直到结束，获得当前时间片的社区结构方法具体包括：

1)预估每个时间片的错误累积IEAt；

2)判断IEAt是否超过错误累积最佳阈值，否，则进入3)；是，则进入4)；

3)以前一个时间片的社区结构为基础，动态更新增量节点的社区归属，获得当前时间片的社区结构；

4)重新采用和第一个时间片相同的静态方法对当前时间片进行社区划分，获得当前时间片的社区结构。

一种错误累积敏感的增量式动态社区发现系统，包括：错误累积预估模块、错误累积最佳阈值计算模块、初始时间片社区划分模块和后续时间片社区划分模块；

错误累积预估模块，用于预估动态社交网络给定时间片的错误累积；

错误累积最佳阈值计算模块，用于根据错误累积预估模块输出的错误累积结果计算动态社交网络的错误累积最佳阈值；

初始时间片社区划分模块，用于采用静态方法划分动态社交网络的第一个时间片，获得动态社交网络的初始社区结构；

后续时间片社区划分模块，用于从第二个时间片开始直到结束，判断错误累积预估模块输出的当前时间片的错误累积是否超过错误累积最佳阈值计算模块输出的错误累积最佳阈值，是，则重新进行社区划分，获得当前时间片社区结构；否，则动态更新增量节点的社区归属，获得当前时间片的社区结构。

错误累积预估模块采用的错误累积的预估函数为：其中，IEAt表示预估的当前时间片t的错误累积，t0为最近一次采用静态方法划分社区结构的时间片，ΔNi表示从t0开始的第i个时间片的增量节点个数，Ni表示第i个时间片的节点总数。

错误累积最佳阈值计算模块针对预设的动态社交网络的错误累积阈值序列，分别计算社区划分准确性和时间消耗的杠杆值LOCT；选取LOCT最大值对应的错误累积阈值，为动态社交网络的错误累积最佳阈值。

错误累积最佳阈值计算模块中，杠杆值LOCT的计算公式为：

其中，t为当前时间片，T为总时间片数，CCt为t时间片和最近一次采用静态方法重新划分社区结构的时间片之间的相关系数，freq为采用静态方法重新划分社区结构的次数，ratio为比例系数；

相关系数CCt的计算公式为：

其中，t为当前时间片，t0为最近一次采用静态方法划分社区结构的时间片；Et代表t时间片的边集合，表示t0时间片的边集合；IEAt表示预估的当前时间片t的错误累积，threshod为错误累积阈值；

比例系数ratio的计算公式为：其中，ΔEi为i时间片的增量边数，Ei为i时间片的总边数。

进一步地，后续时间片社区划分模块包括当前时间片社区划分策略选择单元和当前时间片社区划分单元；

当前时间片社区划分策略选择单元，用于选取社区划分的策略，包括：如果错误累积预估模块预估的当前时间片的错误累积没有超过错误累积最佳阈值计算模块计算的错误累积最佳阈值，则当前时间片的社区划分采用增量更新策略，即以前一个时间片的社区结构为基础，动态更新增量节点的社区归属，获得当前时间片的社区结构；否则，当前时间片的社区划分采用重新划分策略，即重新采用和第一个时间片相同的静态方法对当前时间片进行社区划分；

当前时间片社区划分单元，用于按照当前时间片社区划分策略选择单元选取的策略完成当前时间片的社区划分。

三、技术方案

充分考虑了传统增量式动态社区发现中存在的错误累积现象，对每个时间片的错误累积进行了预估，并根据错误累积预估结果选择合适策略进行社区发现；在不改变原有的社区划分方法中的初始社区划分方法和增量更新策略的基础上，通过对每个时间片的错误累积进行预估，如果预估的错误累积大于设定的阈值，则当前时间片不是采用增量更新策略，而是采用和初始时间片一样的方法重新划分获得社区结构，在确保社区发现效率的基础上，提高了社区发现的准确性。