一種大規(guī)模時(shí)序語(yǔ)義網(wǎng)絡(luò)中突發(fā)持續(xù)性事件搜索算法

孟天宇 李源 孫晶 劉金生

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

1 引言

真實(shí)世界中，社交網(wǎng)絡(luò)，生物網(wǎng)絡(luò)，交通網(wǎng)絡(luò)等都是高度動(dòng)態(tài)的,可以用圖模型表示[1]。給定一個(gè)圖G=(V,E,W,T), 其中頂點(diǎn)V 表示實(shí)體，E,W,T 是一個(gè)四元組（u,v,w,t）,u,v 表示兩個(gè)實(shí)體，w 是u,v相互作用的時(shí)邊上的權(quán)值,t 是u,v 相互作用的時(shí)間，涉及時(shí)間信息的圖通常被稱為時(shí)序圖[2]。在分析大規(guī)模的時(shí)序網(wǎng)絡(luò)中，事件的交互模式往往是突發(fā)的[3]，這里的突發(fā)表示事件在很短的時(shí)間發(fā)生。本文研究的是時(shí)序圖中的突發(fā)持續(xù)子圖，突發(fā)持續(xù)子圖表示的是一個(gè)稠密子圖在很短的時(shí)間出現(xiàn)，并且持續(xù)一段時(shí)間。換句話來(lái)說(shuō)，我們旨在時(shí)序圖中搜索出在很短時(shí)間內(nèi)發(fā)生且具有持續(xù)性的稠密連通子圖。在時(shí)序圖中搜索出突發(fā)持續(xù)子圖可以幫助我們應(yīng)對(duì)生活中許多實(shí)際問(wèn)題。例如，在緊急事件檢測(cè)方面，突發(fā)持續(xù)子圖可用于通信網(wǎng)絡(luò)中緊急事件檢測(cè)[4]，在商業(yè)協(xié)作方面，突發(fā)持續(xù)子圖可以找到在商業(yè)協(xié)作網(wǎng)絡(luò)中最親密的合作關(guān)系，幫助我們找到新的商業(yè)機(jī)會(huì)[5]。目前為止，時(shí)序圖中稠密子圖挖掘問(wèn)題[6,7,8,9]被研究者廣泛的研究，該問(wèn)題旨在找到時(shí)序圖中所有的目標(biāo)子圖，但是當(dāng)數(shù)據(jù)規(guī)模過(guò)大，這一問(wèn)題將變得復(fù)雜，且發(fā)現(xiàn)效率較低，針對(duì)以上問(wèn)題，本文提出了時(shí)序圖中的突發(fā)持續(xù)子圖（Burst Persistence Subgraph，BPS）模型。給定一個(gè)時(shí)序圖G(V,E,W,T)查詢點(diǎn)q 和正整數(shù)k，BPS 為時(shí)序圖中的子圖g，并且滿足如下兩個(gè)條件：

（1）圖g 中所有節(jié)點(diǎn)滿足其鄰接點(diǎn)的度數(shù)與邊上的權(quán)值的乘積之和在同一時(shí)間時(shí)刻增大，且乘積之和持續(xù)了一段相同的時(shí)間戳。

（2）圖g 是一個(gè)與查詢點(diǎn)q 連通的k-核圖。使用BPS 定義時(shí)序圖中的突發(fā)持續(xù)的稠密子圖有以下優(yōu)點(diǎn)：BPS 不僅找到在時(shí)間上具有突發(fā)持續(xù)性質(zhì)的稠密子圖，而且包含查詢點(diǎn)q 的k-核算法的搜索效率較高，可以擴(kuò)展到大圖計(jì)算。

2 基本概念及相關(guān)定義

本節(jié)主要介紹一些基本概念及其符號(hào)表達(dá)，闡述了時(shí)序圖的相關(guān)定義，并對(duì)要解決的主要問(wèn)題給出具體定義。

2.1 基本概念

令G(V,E,W,T)來(lái)表示一個(gè)時(shí)序圖，節(jié)點(diǎn)集V={ν1,ν2…νn},n=|V|,表示頂點(diǎn)的個(gè)數(shù)。m=|E|表示邊和其對(duì)應(yīng)權(quán)重的個(gè)數(shù),s=|T|為時(shí)間戳的個(gè)數(shù)。每條邊e?E 是一個(gè)四元組（u,v,w,t）,v,u 是V 中的節(jié)點(diǎn)，w 是u,v 相互作用的時(shí)邊上的權(quán)值，t 是u,v 相互作用的時(shí)間。W={w|（u,v,w,t）∈E},表示邊上權(quán)值的集合。T={ t|（u,v,w,t）∈E},為所有節(jié)點(diǎn)之間存在聯(lián)系時(shí)刻的集合。Nt(v)表示圖G 在t 時(shí)刻下中v 的鄰接點(diǎn)的集合，節(jié)點(diǎn)ν 在t 時(shí)刻下的度數(shù)為degt(v)，他對(duì)應(yīng)的值為degt(v)=|Nt(v) |。

表2：數(shù)據(jù)源的實(shí)驗(yàn)參數(shù)

突發(fā)持續(xù)子圖中節(jié)點(diǎn)有一些共同特征，這些節(jié)點(diǎn)的突發(fā)度較高且持續(xù)時(shí)間較長(zhǎng)，接下來(lái)給出具體的相關(guān)定義來(lái)描述其屬性。

定義1 (重要度)：圖G 中一個(gè)點(diǎn)的在某一時(shí)刻的重要度在用Bt(v)來(lái)表示，其中v∈V

在t 時(shí)刻下，Nt(vi)表示節(jié)點(diǎn)vi 的鄰接點(diǎn)集合，degt(νj)表示節(jié)點(diǎn)νj的度，w(νi, vj, w, t)表示νi, νj兩點(diǎn)間的權(quán)值，節(jié)點(diǎn)νi的重要度與其鄰接點(diǎn)的度數(shù)以及連接的邊的權(quán)重成正相關(guān)。

定義2(時(shí)序子圖)：給定時(shí)序圖G(V,E,W,T)，在連續(xù)的時(shí)間間隔內(nèi)，對(duì)于節(jié)點(diǎn)S?V 時(shí)序子圖可以用GS(T)=(S,ES(T),WS(T),TS(T))來(lái)表示。接下來(lái)給出突發(fā)持續(xù)序列（Burst Continuous Sequence，BCS）的定義。

定義3(BCS)：給定BCS(q)={ti}來(lái)表示節(jié)點(diǎn)q 的突發(fā)持續(xù)序列。突發(fā)度用λ，持續(xù)度用α，持續(xù)性用γ，節(jié)點(diǎn)滿足在某時(shí)刻重要度的增大的值大于等于λ，且在時(shí)間戳為γ內(nèi)重要度的變化范圍為[-α,∞]，則該節(jié)點(diǎn)在這一時(shí)刻滿足突發(fā)持續(xù)。突發(fā)持續(xù)序列為滿足突發(fā)持續(xù)的時(shí)間戳集合，在突發(fā)持續(xù)度序列定義的基礎(chǔ)上，提出了一個(gè)候選子圖（Candidate Subgraph,CS）的定義。

定義4（CS）：給定CS(q)表示包含查詢點(diǎn)q 的候選子圖。候選子圖是滿足時(shí)序圖在時(shí)間戳γ+1 下包含查詢點(diǎn)q 的靜態(tài)投影圖且圖所有的節(jié)點(diǎn)具有突發(fā)持續(xù)性。接下來(lái)給出時(shí)序圖中的突發(fā)持續(xù)子圖（Burst Persistence Subgraph，BPS）的定義。

定義5 (BPS)：給定候選子圖CS(q)，正整數(shù)k(k ≥3)以及一個(gè)查詢點(diǎn)q，那么g 稱為BPS,如果滿足如下條件：

（1）g 是CS(q)的子圖且是包含查詢點(diǎn)q 的k-核子圖；

（2）g 為滿足條件（1）（2）的極大子圖，也就是不存在g’∈G使得g?g’并且g’滿足條件（1）。

2.2 問(wèn)題定義

基于以上定義，本文給出了在時(shí)序網(wǎng)絡(luò)網(wǎng)絡(luò)中突發(fā)持續(xù)子圖搜索的問(wèn)題定義

問(wèn)題1：給定時(shí)序圖G(V,E,W,T)正整數(shù)k(k ≥3)和查詢點(diǎn)q，首先找到找到節(jié)點(diǎn)q 的突發(fā)持續(xù)性序列BCS(q)，然后根據(jù)查詢點(diǎn)的突發(fā)持續(xù)序列得到候選子圖CS(q)，最后從搜索出BPS 子圖結(jié)構(gòu)。

接下來(lái)的章節(jié)，我們具體的闡述BPS 的搜索算法。

3 BPS搜索算法

本節(jié)講述時(shí)序圖中突發(fā)持續(xù)子圖搜索問(wèn)題，給定包含查詢點(diǎn)q的時(shí)序圖，從中搜索所有的BPS 子圖。在搜索算法開(kāi)始前，對(duì)時(shí)序圖進(jìn)行預(yù)處理，首先根據(jù)第二節(jié)的重要度定義得到查詢點(diǎn)的重要度，其次確定參數(shù)λ，α，γ 后，得到查詢點(diǎn)的突發(fā)持續(xù)序列 BCS(q)。接下來(lái)詳細(xì)的介紹兩種搜索算法。

3.1 QS-BPS算法

本小節(jié)的QS-BPS 算法，是基于普通事物隊(duì)列的基礎(chǔ)策略。首先計(jì)算候選子圖CS(q),將CS(q)中節(jié)點(diǎn)度數(shù)小于k 的節(jié)點(diǎn)入隊(duì)，其次將隊(duì)列中節(jié)點(diǎn)出隊(duì)，刪除鄰接點(diǎn)及相關(guān)邊并更新節(jié)點(diǎn)度數(shù),將節(jié)點(diǎn)度數(shù)小于k 的入隊(duì)，直至隊(duì)列為空，然后廣度優(yōu)先搜索找到與查詢點(diǎn)q 連通的子圖添加到結(jié)果集中，最后返回BPS 子圖結(jié)構(gòu)集C，結(jié)構(gòu)集C 中包含所有可能的BPS 子圖。

算法1：QS-BPS.

算法2：SP 算法.

3.2 KS-BPS算法

本節(jié)對(duì)上一小節(jié)的算法進(jìn)行改進(jìn)，提出了一種優(yōu)化策略下的KS-BPS算法，首先計(jì)算候選子圖CS(q)，其次對(duì)CS(q)進(jìn)行求核分解,得到節(jié)點(diǎn)的核數(shù)，然后廣度優(yōu)先搜索找到節(jié)點(diǎn)核數(shù)大于k 且查詢點(diǎn)q 連通的子圖添加到結(jié)果集中，最后返回BPS 子圖結(jié)構(gòu)集C，結(jié)構(gòu)集C 中包含所有可能的BPS 子圖。

圖1：不同參數(shù)λ 下的指標(biāo)對(duì)比

圖2：不同參數(shù)α 下的指標(biāo)對(duì)比

圖3：不同參數(shù)γ 下的指標(biāo)對(duì)比

圖4：不同參數(shù)k 下的指標(biāo)對(duì)比

算法3：KS-BPS.

通過(guò)對(duì)CS(q)進(jìn)行k-核分解，可以獲取每個(gè)頂點(diǎn)的核數(shù)，為尋找k-核圖做準(zhǔn)備，core-number 算法的具體過(guò)程參見(jiàn)文獻(xiàn)[10]。

4 實(shí)驗(yàn)結(jié)果與分析

為了有效的評(píng)估提出的算法，本實(shí)驗(yàn)用真實(shí)的微博數(shù)據(jù)集進(jìn)行評(píng)估，數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)信息匯總在表1 中，其中|V|表示頂點(diǎn)個(gè)數(shù)、|E|表示時(shí)序邊數(shù)、|E’|表示靜態(tài)投影邊數(shù)、kmax節(jié)點(diǎn)最大核數(shù)、|T|表示時(shí)間快照的數(shù)量。WEIBO 是從微博上爬取的2019年12月1日到2020年4月17日的語(yǔ)義網(wǎng)絡(luò)。時(shí)間戳單位是日。

4.1 實(shí)驗(yàn)參數(shù)設(shè)定

本文中的兩個(gè)算法都涉及到了四個(gè)參數(shù)λ,α,γ,k。其中λ,α 作為時(shí)序參數(shù)用于確定節(jié)點(diǎn)的重要度的變化范圍，γ 用于確定子圖的最短持續(xù)時(shí)間，k 用于確定子圖的結(jié)構(gòu)內(nèi)聚性，實(shí)驗(yàn)部分將各個(gè)數(shù)據(jù)源的需要的四個(gè)參數(shù)分別取三個(gè)值。數(shù)據(jù)源參數(shù)的取值信息如表2所示。

4.2 不同參數(shù)下算法有效性分析

由于不同的初始參數(shù)對(duì)算法的有效性和高效有影響，本節(jié)將進(jìn)行不同參數(shù)下算法性能的對(duì)比實(shí)驗(yàn)，選用運(yùn)行時(shí)間和graph density兩個(gè)指標(biāo)對(duì)算法的高效性和有效性進(jìn)行評(píng)價(jià)，兩個(gè)指標(biāo)的具體概念如下：

（1）運(yùn)行時(shí)間：本文提出的兩個(gè)算法加上預(yù)處理的運(yùn)行時(shí)間

（2）圖密度graph density：用實(shí)際邊數(shù)除以最大可能邊數(shù)，即為圖密度，當(dāng)圖密度越大時(shí)表示圖中節(jié)點(diǎn)連接越緊密。graph density=|E|*2/(|V|*(|V|-1)),這里的E 指的是邊數(shù)，V 是節(jié)點(diǎn)個(gè)數(shù)，|V|*(|V|-1) 表示最多的連接邊數(shù),|E|*2 為實(shí)際邊數(shù)。另外，由于兩個(gè)算法本質(zhì)上求出的是k-核圖，因此兩個(gè)算法的graph density 一致。

圖1 展示了變化參數(shù)λ 時(shí)KS-BPS 算法和QS-BPS 算法及預(yù)處理過(guò)程的運(yùn)行時(shí)間和graph density 兩個(gè)指標(biāo)的對(duì)比。通過(guò)圖1 可以看出λ值越大，算法的運(yùn)行時(shí)間越短。這主要是因?yàn)楫?dāng)λ的值增大時(shí)，需要考慮的節(jié)點(diǎn)個(gè)數(shù)逐漸減少，另外，graph density 值也逐漸減小，這主要是由于當(dāng)λ 的值增大時(shí)，滿足條件的節(jié)點(diǎn)和邊的個(gè)數(shù)減少。

圖2 顯示了隨著α 逐漸增大，算法的運(yùn)行時(shí)間逐漸增大，這主要是因?yàn)楫?dāng)α 的值逐漸增大時(shí)，滿足持續(xù)性的節(jié)點(diǎn)逐漸增多。圖2也展示了α 的增大對(duì)graph density 沒(méi)有很大的影響。

圖3 展示了隨著參數(shù)γ 的逐漸增大，兩個(gè)算法的運(yùn)行時(shí)間和graph density 逐漸增大，這主要是因?yàn)殡S著γ 的增大，會(huì)有更多的時(shí)序邊添加到候選子圖中。

在圖4 中，隨著k 值的逐漸增大，QS-BPS 算法的運(yùn)行時(shí)間逐漸增加,這是因?yàn)殡S著k 值的逐漸增大，所檢測(cè)的圖必須包含更大的k-核,需要花費(fèi)更多的時(shí)間。但是KS-BPS 運(yùn)行時(shí)間幾乎沒(méi)有影響，僅稍微降低，這是因?yàn)镵S-BPS 算法對(duì)于不同的k 值都要求先求出節(jié)點(diǎn)的核數(shù)，所以變化k 值對(duì)算法的影響較小。圖4 還顯示了，隨著k 值的逐漸增大，兩個(gè)算法的graph density 逐漸增大。它的主要原因是k 值設(shè)置越大，找到的圖越密集。

5 結(jié)束語(yǔ)

本文研究了時(shí)序圖中突發(fā)持續(xù)子圖搜索問(wèn)題，即搜索出在以最快的速度聚集其密度且持續(xù)一段時(shí)間的稠密連通子圖。首先考慮查詢點(diǎn)的鄰接點(diǎn)度數(shù)和邊上權(quán)值計(jì)算出查詢點(diǎn)的重要度，其次由查詢點(diǎn)的重要度和突發(fā)持續(xù)性得到突發(fā)持續(xù)序列，然后根據(jù)查詢點(diǎn)的突發(fā)持續(xù)序列提出了兩種不同策略下的突發(fā)持續(xù)子圖搜索算法。最后，通過(guò)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出算法的高效性和有效性。