戴捷 李源 范曉林 孫晶

（北方工業(yè)大學信息學院 北京市 100144）

1 引言

在現(xiàn)實世界中，圖模型被廣泛用于表示實體之間的關系，比如社交網(wǎng)絡，交通網(wǎng)絡，作者協(xié)作網(wǎng)絡等。給定一個圖，集合中的頂點表示實體，邊表示關系，更進一步，可以設置帶權重的邊用來體現(xiàn)實體關系的聯(lián)系程度，比如交通網(wǎng)絡中頂點可以表示為城市，邊表示兩城市之間的路線，邊上的權重可以表示距離[1]。在信息時代，圖的規(guī)模變得巨大，圖模型所代表的數(shù)據(jù)中的價值也越來越重要。由于時序網(wǎng)絡中的信息是實時變化的，所以更值得的挖掘其中的信息。對于所有圖模型而言，內(nèi)聚子圖是圖中最密集的區(qū)域，也就含有重要的信息，它們可以表示社交網(wǎng)絡中的交際社區(qū)、商業(yè)合作網(wǎng)絡中的合作聯(lián)盟。因此，尋找圖中的內(nèi)聚子圖是一個重要且有意義的問題[3]-[7]。在時序網(wǎng)絡中，由于信息具有時間性，所以任何事件都有一個發(fā)生的過程。其中，有一類事件非常值得關注，它們的出現(xiàn)是突發(fā)的，就像是平靜的水面突然爆出水花一樣，這類事件可以稱為突發(fā)事件。這種突發(fā)事件往往帶有重要的信息。事件的屬性可以是好也可以是壞，若是一件壞事，隨著時間的發(fā)展，事件的擴大可能會給社會造成不良影響甚至是極大的損失。顯然，越早發(fā)現(xiàn)突發(fā)事件，就能更好地進行處理，如果早期就注意到該事件的出現(xiàn)，然后加以控制，就能夠避免損失，從另一方面說也給社會帶來了益處。在圖模型中，突發(fā)事件可以表示為突發(fā)內(nèi)聚子圖 (BCS)，也就是多個節(jié)點以最快的比例積聚其內(nèi)聚性，此時形成的子圖就是一個帶有突發(fā)性可以表示事件的BCS。但遺憾的是，目前對于時序網(wǎng)絡的研究普遍忽視了信息的突發(fā)，可喜的是，最新的工作提出了突發(fā)這一新概念[1][2]，同時Qin 等人[2]提出了突發(fā)內(nèi)聚子圖 (BCS) 模型并給出了搜索方法。然而，上述方法要求BCS 至少要持續(xù)一個給定的時間，這就忽略了時效性，避免了事件被提前發(fā)現(xiàn)。針對上述問題，我們首先通過整合拓撲信息和歷史時空信息，將具有邊緣權重的時空網(wǎng)絡轉(zhuǎn)化為節(jié)點加權的時空網(wǎng)絡。然后，我們基于著名的k-core 提出了早期突發(fā)內(nèi)聚子圖(EBCS)模型，即具有早期突發(fā)性和內(nèi)聚性的k-core。為了找到EBCS：

（1）我們提出了一種全局搜索算法，采用縮減策略，稱為GS-EBCS。

（2）為了提高效率，我們進一步提出了一種具有擴展-精簡思想的局部搜索算法，稱為LS-EBCS。

另外，在我們提出的兩種算法中：

1.我們使用用滑動窗口的方法來解決時間持續(xù)問題；

2.由于時空網(wǎng)絡中不斷出現(xiàn)突發(fā)信息，我們給出一個閾值φ 來過濾不重要的突發(fā)信息。

2 基本概念及相關定義

本節(jié)主要介紹一些基本概念及其符號表達，闡述了EBCS 的相關定義，并對要解決的主要問題給出具體定義。

2.1 基本概念

給定一組時間圖序列：, 其中V={v1,v2,v3…vn-1,vn}表示節(jié)點集合，|V|表示節(jié)點的數(shù)量。t∈{ti,ti+1,…,tj}表示時間戳。在時間戳t, e=(u,v)表示節(jié)點u,v∈V 之間的無向邊。|E|表示邊的數(shù)量, ew(u,v)≥0 表示節(jié)點u,v 之間的邊權重, 其中ew∈At, At是存放邊權重的n*n 矩陣。ew(u,v)=0 意味著節(jié)點u,v 之間沒有邊。同時本文用size(Gi)=|V|+|Ei|表示圖Gi的規(guī)模。

（1）它和所給時間圖序列有相同的節(jié)點集V。

最小度是常用的測量子圖內(nèi)聚性的方法。

由于邊權重可以表示兩節(jié)點之間的聯(lián)系程度所以sumu可以反映節(jié)點u 及其鄰居節(jié)點所構成的一個子圖的權重。在一個網(wǎng)絡中，這樣的子圖可以反映事件的聯(lián)系程度。

表1：統(tǒng)計數(shù)據(jù)集

基本概念闡述明白后，下面給出EBCS 的定義。

2.2 問題定義

接下來的章節(jié)，我們具體的闡述EBCS 的兩種發(fā)現(xiàn)算法。

3 EBCS發(fā)現(xiàn)算法

本節(jié)講述EBCS 的兩種發(fā)現(xiàn)算法。首先對時間圖序列進行預處理：指定sg 值后，將[ti,tj]時間段的時間圖依據(jù)sg 值轉(zhuǎn)換為帶有節(jié)點時間權重的聚合圖序列接下來，給出算法的詳細介紹。

3.1 GS-EBCS算法

本小節(jié)的GS-EBCS 算法，是基于全局搜索的策略。給定閾值φ 和正整數(shù)k，如果聚合圖中最大的節(jié)點時間權重小于φ，說明聚合圖中表示的突發(fā)信息不重要，所以不對聚合圖處理。反之，將聚合圖修剪成k-core，然后不斷的從該k-core 中移除節(jié)點時間權重最小的節(jié)點，直到再移除一個節(jié)點時間權重最小節(jié)點后，k-core不存在，此時停止移除節(jié)點。由剩余節(jié)點誘導得到的子圖就是EBCS。

算法1.GS-EBCS.

圖1：不同參數(shù)下算法發(fā)現(xiàn)的EBCS 的數(shù)量

圖2：sg=4 時，不同k 和φ 下算法運行時間

圖3：sg=7 時，不同k 和φ 下算法運行時間

3.2 LS-EBCS算法

本節(jié)對上一小節(jié)的算法進行改進，提出了一種基于局部搜索策略的LS-EBCS 算法。該算法從節(jié)點時間權重最大的節(jié)點開始，按照節(jié)點時間權重從大到小的順序不斷選中節(jié)點，直到由選中節(jié)點誘導得到的子圖包含k-core。后續(xù)操作與上述算法相同。

算法3.LS-EBCS.

該算法采取了一種二倍擴展的方法（行7）。當t+sg[C]不包含k-core 時，就繼續(xù)選中k+1 之后的節(jié)點，直到t+sg[C]的規(guī)模變?yōu)樵?guī)模的兩倍，若達不到兩倍，t+sg[C]就是t+sg。只采取二倍擴展的原因詳見文獻[8]。

4 實驗結果與分析

圖4：算法在單個聚合圖上運行時間的比較

圖5：不同k 值下的EBCS 直徑

為了有效的評估提出的算法，本實驗用真實的微博數(shù)據(jù)集進行評估，數(shù)據(jù)集的詳細統(tǒng)計信息匯總在表1 中，其中|V|表示頂點個數(shù)、|E|表示時序邊數(shù)、k_max 表示數(shù)據(jù)集最大核數(shù)、表示規(guī)模最大的單個聚合圖中的最大核數(shù)、|T|表示時間圖的數(shù)量，| |表示聚合圖的數(shù)量。該數(shù)據(jù)集是時序語義網(wǎng)絡，時間圖中的每一條邊表示詞v 和詞u 在一句話中同時出現(xiàn)，邊的權重是出現(xiàn)的次數(shù)占所有邊次數(shù)和的比值。本文收集了從2019年 12月 1日到 2020年 4月 3 里128 家媒體發(fā)布的信息。時間戳單位是日。

4.1 算法高效性分析

本節(jié)分析LS-EBCS 算法和GS-EBCS 算法在不同參數(shù)下的高效性。參數(shù)包括聚合閾值sg，閾值φ 以及表示核數(shù)的正整數(shù)k。

從圖1 可以看出，通過調(diào)整φ 可以有效地對聚合圖進行過濾。從圖2 和圖3 中可以看出，當k 值較小時，LS-EBCS 算法的運行效率遠高于GS-EBCS 算法；當k 值較大時，GS-EBCS 算法的運行效率高于LS-EBCS 算法。這是因為，在140 個時間圖中，有些時間圖的規(guī)模很小，所以形成的聚合圖的規(guī)模也很小。當k 的值較小時，只要0 到1 次增加子圖大小，LS-EBCS 就可以找到包含k-core的子圖。但是，當k 的值很大時，算法要多次增加子圖大小。在最壞的情況下，子圖就是聚合圖。這時LS-EBCS 算法就變成了GSEBCS 算法，加上前期增加子圖大小的時間后，LS-EBCS 算法的運行使間會比GS-EBCS 算法長。

為了在微博數(shù)據(jù)集上更明顯地比較兩種算法，我們將實驗設置在一個最大27 核的單個聚合圖上。在圖4 中，可以清楚地看到，隨著k 值和聚合圖規(guī)模的增加，兩種算法的運行時間的變化。明顯看出LS-EBCS 算法優(yōu)于GS-EBCS 算法。

4.2 算法有效性分析

本節(jié)使用圖直徑度量方法來測試我們提出的算法所發(fā)現(xiàn)的EBCS 子圖的有效性。

圖5.a 給出了在sg 值為7 和4 的條件下，改變k 值，在包含139 個聚合圖的微博數(shù)據(jù)集中發(fā)現(xiàn)的EBCS 的平均直徑，圖5.b 給出了上述單個聚合圖在sg 值為7 和4 的條件下，改變k 值時EBCS的直徑。從實驗結果可以清楚地看出LS-EBCS 算法和GS-EBCS 算法的有效性?？傊?，從總的實驗結果可以看出，兩種算法都有各自的優(yōu)勢，但總的來說，LS-EBCS 算法優(yōu)于GS-EBCS 算法。

5 結束語

本文旨在發(fā)現(xiàn)在時序網(wǎng)絡中用已有的BCS 圖模型表示的突發(fā)事件。為了更早地發(fā)現(xiàn)突發(fā)事件，我們結合圖模型的設計和實際環(huán)境的需求，提出了EBCS 模型。接下來，我們分別提出了基于全局搜索的GS-EBCS 算法和基于局部搜索的LS-EBCS 算法。最后，我們在四個大型真實數(shù)據(jù)集上進行了大量的實驗，以證明我們提出的算法的效率和效果。