大规模时序网络中早期突发内聚子图发现算法研究

戴捷 李源 范晓林 孙晶

（北方工业大学信息学院 北京市 100144）

1 引言

在现实世界中，图模型被广泛用于表示实体之间的关系，比如社交网络，交通网络，作者协作网络等。给定一个图，集合中的顶点表示实体，边表示关系，更进一步，可以设置带权重的边用来体现实体关系的联系程度，比如交通网络中顶点可以表示为城市，边表示两城市之间的路线，边上的权重可以表示距离[1]。在信息时代，图的规模变得巨大，图模型所代表的数据中的价值也越来越重要。由于时序网络中的信息是实时变化的，所以更值得的挖掘其中的信息。对于所有图模型而言，内聚子图是图中最密集的区域，也就含有重要的信息，它们可以表示社交网络中的交际社区、商业合作网络中的合作联盟。因此，寻找图中的内聚子图是一个重要且有意义的问题[3]-[7]。在时序网络中，由于信息具有时间性，所以任何事件都有一个发生的过程。其中，有一类事件非常值得关注，它们的出现是突发的，就像是平静的水面突然爆出水花一样，这类事件可以称为突发事件。这种突发事件往往带有重要的信息。事件的属性可以是好也可以是坏，若是一件坏事，随着时间的发展，事件的扩大可能会给社会造成不良影响甚至是极大的损失。显然，越早发现突发事件，就能更好地进行处理，如果早期就注意到该事件的出现，然后加以控制，就能够避免损失，从另一方面说也给社会带来了益处。在图模型中，突发事件可以表示为突发内聚子图 (BCS)，也就是多个节点以最快的比例积聚其内聚性，此时形成的子图就是一个带有突发性可以表示事件的BCS。但遗憾的是，目前对于时序网络的研究普遍忽视了信息的突发，可喜的是，最新的工作提出了突发这一新概念[1][2]，同时Qin 等人[2]提出了突发内聚子图 (BCS) 模型并给出了搜索方法。然而，上述方法要求BCS 至少要持续一个给定的时间，这就忽略了时效性，避免了事件被提前发现。针对上述问题，我们首先通过整合拓扑信息和历史时空信息，将具有边缘权重的时空网络转化为节点加权的时空网络。然后，我们基于著名的k-core 提出了早期突发内聚子图(EBCS)模型，即具有早期突发性和内聚性的k-core。为了找到EBCS：

（1）我们提出了一种全局搜索算法，采用缩减策略，称为GS-EBCS。

（2）为了提高效率，我们进一步提出了一种具有扩展-精简思想的局部搜索算法，称为LS-EBCS。

另外，在我们提出的两种算法中：

1.我们使用用滑动窗口的方法来解决时间持续问题；

2.由于时空网络中不断出现突发信息，我们给出一个阈值φ 来过滤不重要的突发信息。

2 基本概念及相关定义

本节主要介绍一些基本概念及其符号表达，阐述了EBCS 的相关定义，并对要解决的主要问题给出具体定义。

2.1 基本概念

给定一组时间图序列：, 其中V={v1,v2,v3…vn-1,vn}表示节点集合，|V|表示节点的数量。t∈{ti,ti+1,…,tj}表示时间戳。在时间戳t, e=(u,v)表示节点u,v∈V 之间的无向边。|E|表示边的数量, ew(u,v)≥0 表示节点u,v 之间的边权重, 其中ew∈At, At是存放边权重的n*n 矩阵。ew(u,v)=0 意味着节点u,v 之间没有边。同时本文用size(Gi)=|V|+|Ei|表示图Gi的规模。

（1）它和所给时间图序列有相同的节点集V。

最小度是常用的测量子图内聚性的方法。

由于边权重可以表示两节点之间的联系程度所以sumu可以反映节点u 及其邻居节点所构成的一个子图的权重。在一个网络中，这样的子图可以反映事件的联系程度。

表1：统计数据集

基本概念阐述明白后，下面给出EBCS 的定义。

2.2 问题定义

接下来的章节，我们具体的阐述EBCS 的两种发现算法。

3 EBCS发现算法

本节讲述EBCS 的两种发现算法。首先对时间图序列进行预处理：指定sg 值后，将[ti,tj]时间段的时间图依据sg 值转换为带有节点时间权重的聚合图序列接下来，给出算法的详细介绍。

3.1 GS-EBCS算法

本小节的GS-EBCS 算法，是基于全局搜索的策略。给定阈值φ 和正整数k，如果聚合图中最大的节点时间权重小于φ，说明聚合图中表示的突发信息不重要，所以不对聚合图处理。反之，将聚合图修剪成k-core，然后不断的从该k-core 中移除节点时间权重最小的节点，直到再移除一个节点时间权重最小节点后，k-core不存在，此时停止移除节点。由剩余节点诱导得到的子图就是EBCS。

算法1.GS-EBCS.

图1：不同参数下算法发现的EBCS 的数量

图2：sg=4 时，不同k 和φ 下算法运行时间

图3：sg=7 时，不同k 和φ 下算法运行时间

3.2 LS-EBCS算法

本节对上一小节的算法进行改进，提出了一种基于局部搜索策略的LS-EBCS 算法。该算法从节点时间权重最大的节点开始，按照节点时间权重从大到小的顺序不断选中节点，直到由选中节点诱导得到的子图包含k-core。后续操作与上述算法相同。

算法3.LS-EBCS.

该算法采取了一种二倍扩展的方法（行7）。当t+sg[C]不包含k-core 时，就继续选中k+1 之后的节点，直到t+sg[C]的规模变为原规模的两倍，若达不到两倍，t+sg[C]就是t+sg。只采取二倍扩展的原因详见文献[8]。

4 实验结果与分析

图4：算法在单个聚合图上运行时间的比较

图5：不同k 值下的EBCS 直径

为了有效的评估提出的算法，本实验用真实的微博数据集进行评估，数据集的详细统计信息汇总在表1 中，其中|V|表示顶点个数、|E|表示时序边数、k_max 表示数据集最大核数、表示规模最大的单个聚合图中的最大核数、|T|表示时间图的数量，| |表示聚合图的数量。该数据集是时序语义网络，时间图中的每一条边表示词v 和词u 在一句话中同时出现，边的权重是出现的次数占所有边次数和的比值。本文收集了从2019年 12月 1日到 2020年 4月 3 里128 家媒体发布的信息。时间戳单位是日。

4.1 算法高效性分析

本节分析LS-EBCS 算法和GS-EBCS 算法在不同参数下的高效性。参数包括聚合阈值sg，阈值φ 以及表示核数的正整数k。

从图1 可以看出，通过调整φ 可以有效地对聚合图进行过滤。从图2 和图3 中可以看出，当k 值较小时，LS-EBCS 算法的运行效率远高于GS-EBCS 算法；当k 值较大时，GS-EBCS 算法的运行效率高于LS-EBCS 算法。这是因为，在140 个时间图中，有些时间图的规模很小，所以形成的聚合图的规模也很小。当k 的值较小时，只要0 到1 次增加子图大小，LS-EBCS 就可以找到包含k-core的子图。但是，当k 的值很大时，算法要多次增加子图大小。在最坏的情况下，子图就是聚合图。这时LS-EBCS 算法就变成了GSEBCS 算法，加上前期增加子图大小的时间后，LS-EBCS 算法的运行使间会比GS-EBCS 算法长。

为了在微博数据集上更明显地比较两种算法，我们将实验设置在一个最大27 核的单个聚合图上。在图4 中，可以清楚地看到，随着k 值和聚合图规模的增加，两种算法的运行时间的变化。明显看出LS-EBCS 算法优于GS-EBCS 算法。

4.2 算法有效性分析

本节使用图直径度量方法来测试我们提出的算法所发现的EBCS 子图的有效性。

图5.a 给出了在sg 值为7 和4 的条件下，改变k 值，在包含139 个聚合图的微博数据集中发现的EBCS 的平均直径，图5.b 给出了上述单个聚合图在sg 值为7 和4 的条件下，改变k 值时EBCS的直径。从实验结果可以清楚地看出LS-EBCS 算法和GS-EBCS 算法的有效性。总之，从总的实验结果可以看出，两种算法都有各自的优势，但总的来说，LS-EBCS 算法优于GS-EBCS 算法。

5 结束语

本文旨在发现在时序网络中用已有的BCS 图模型表示的突发事件。为了更早地发现突发事件，我们结合图模型的设计和实际环境的需求，提出了EBCS 模型。接下来，我们分别提出了基于全局搜索的GS-EBCS 算法和基于局部搜索的LS-EBCS 算法。最后，我们在四个大型真实数据集上进行了大量的实验，以证明我们提出的算法的效率和效果。