孟天宇 李源 孫晶 劉金生

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

1 引言

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

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

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

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

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

2.1 基本概念

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

表2：數(shù)據(jù)源的實驗參數(shù)

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

定義1 (重要度)：圖G 中一個點的在某一時刻的重要度在用Bt(v)來表示，其中v∈V

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

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

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

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

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

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

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

2.2 問題定義

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

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

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

3 BPS搜索算法

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

3.1 QS-BPS算法

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

算法1：QS-BPS.

算法2：SP 算法.

3.2 KS-BPS算法

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

圖1：不同參數(shù)λ 下的指標對比

圖2：不同參數(shù)α 下的指標對比

圖3：不同參數(shù)γ 下的指標對比

圖4：不同參數(shù)k 下的指標對比

算法3：KS-BPS.

通過對CS(q)進行k-核分解，可以獲取每個頂點的核數(shù)，為尋找k-核圖做準備，core-number 算法的具體過程參見文獻[10]。

4 實驗結(jié)果與分析

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

4.1 實驗參數(shù)設(shè)定

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

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

由于不同的初始參數(shù)對算法的有效性和高效有影響，本節(jié)將進行不同參數(shù)下算法性能的對比實驗，選用運行時間和graph density兩個指標對算法的高效性和有效性進行評價，兩個指標的具體概念如下：

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

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

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

圖2 顯示了隨著α 逐漸增大，算法的運行時間逐漸增大，這主要是因為當α 的值逐漸增大時，滿足持續(xù)性的節(jié)點逐漸增多。圖2也展示了α 的增大對graph density 沒有很大的影響。

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

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

5 結(jié)束語

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