李 源，劉金生，趙會群，孫 晶

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

時序圖是一個隨時間不斷變化的圖結(jié)構(gòu)，其中邊上的時間戳代表該邊出現(xiàn)的時間。這一模型具有很多現(xiàn)實(shí)應(yīng)用。例如，社交網(wǎng)絡(luò)[1-2]、作家協(xié)作網(wǎng)絡(luò)[3]、生物信息網(wǎng)絡(luò)[4]等。稠密子圖挖掘問題（cohesive subgraph mining，CSM）作為圖計(jì)算的基礎(chǔ)研究問題之一，近幾年被越來越多的學(xué)者在時序圖上進(jìn)行深入研究。一般來講，CSM分為不考慮查詢節(jié)點(diǎn)的稠密子圖檢測問題（cohesive subgraph detection，CSD）和考慮查詢節(jié)點(diǎn)的稠密子圖搜索問題（cohesive subgraph search，CSS）兩類。時序圖上的CSD問題已經(jīng)被學(xué)者們廣泛研究。但是，當(dāng)時序圖規(guī)模過大時，發(fā)現(xiàn)時序圖中所有的稠密子圖將變得不切實(shí)際。為此，本文將主要研究在時序圖中長期被忽視的CSS問題。該問題的描述如下：給定一個特定的查詢節(jié)點(diǎn)，找到包含該查詢節(jié)點(diǎn)，且滿足一定時間和結(jié)構(gòu)約束條件的子圖。由于查詢節(jié)點(diǎn)的引入，這一問題將具有更強(qiáng)的現(xiàn)實(shí)意義。

在真實(shí)的時序網(wǎng)絡(luò)中找到在一段時間內(nèi)持續(xù)出現(xiàn)的稠密子圖通常是很有意義的[5]。為此，本研究采用(θ,τ)持續(xù)性k-核子圖模型。其中，參數(shù)θ表示判定持續(xù)性的最大間隔。即，將連續(xù)出現(xiàn)兩次時間間隔小于θ的子圖視為不間斷的。參數(shù)τ用于表示最短持續(xù)時間約束，即子圖不間斷的時間至少應(yīng)為τ。參數(shù)k用于結(jié)果子圖的結(jié)構(gòu)約束，即子圖中所有節(jié)點(diǎn)都至少有k個鄰居。從后文實(shí)驗(yàn)可以看出，參數(shù)θ和τ根據(jù)實(shí)際應(yīng)用場景而變化。當(dāng)時序圖變化較為頻繁時，θ應(yīng)取值較?。划?dāng)時序圖變化不頻繁時，θ取值可以適當(dāng)增大。τ值可以根據(jù)實(shí)際需要定義，一般來說，τ值較大時，問題的時間約束更加嚴(yán)格，查詢結(jié)果個數(shù)會更少。本文將研究大規(guī)模時序圖中，找到一個包含特定查詢節(jié)點(diǎn)且滿足該模型的時序子圖。例如，圖1中包含兩個（2，3）持續(xù)性3-核子圖，分別是H0={v0,v1,v2,v3}和H1={v0,v4,v5,v6}。

圖1 一個時序圖的實(shí)例Fig.1 Example of temporal graph

本研究首先證明了時序圖中查詢(θ,τ)持續(xù)性k-核子圖是NP-難問題。為解決這一問題，本文提出通過全局和局部兩種思路設(shè)計(jì)的算法，分別命名為S-Global和S-Center算法。其中S-Global算法從全局角度出發(fā)，不斷刪除不滿足條件的節(jié)點(diǎn)，最后得到一個極大的(θ,τ)持續(xù)性k-核圖。在此過程中，將通過提出的削減規(guī)則減少搜索空間。另一個算法S-Center從查詢節(jié)點(diǎn)出發(fā)，以查詢節(jié)點(diǎn)為中心將其他節(jié)點(diǎn)分層，不斷地在候選結(jié)果的鄰接點(diǎn)中找到正確的節(jié)點(diǎn)加入子圖，直到找到目標(biāo)結(jié)果。這種方式的優(yōu)點(diǎn)是無需遍歷整個時序圖。在四個真實(shí)世界網(wǎng)絡(luò)中的大量實(shí)驗(yàn)，驗(yàn)證了提出算法的高效性。其中S-Global算法更適用于時序圖較為稠密的場景，而S-Center算法則適用于稀疏圖場景。

1 相關(guān)工作

時序圖上的稠密子圖檢測問題已經(jīng)被學(xué)者們廣泛研究。吳歡歡等人提出了一種時序圖上的(k,h)-核模型，即子圖中每個頂點(diǎn)至少有k個鄰接點(diǎn)和h條時序邊[6]。馬帥等人提出一種算法，在加權(quán)時序圖中通過時間快照計(jì)算權(quán)值找到一個時間段內(nèi)的密集連接子圖[7]。瑟莫茲團(tuán)隊(duì)的工作是在時序圖的所有時間快照上找到一個持久的密集子圖[8]。黃欣等人基于k-truss模型，提出了一種基于TCP索引找到包含最大k的查詢頂點(diǎn)的k-truss的方法[9]。

在不同類型的圖結(jié)構(gòu)中，稠密子圖的搜索問題同樣已經(jīng)被深入研究。例如，基于靜態(tài)屬性圖中，文獻(xiàn)[10]提出了一種基于k-核的方法，以找到包含查詢節(jié)點(diǎn)的稠密子圖。在加權(quán)的屬性圖中，文獻(xiàn)[11]提出了一種方法來找到權(quán)值較高的內(nèi)聚子圖。在地理社交網(wǎng)絡(luò)中，文獻(xiàn)[12]提出了一種基于位置信息找到圖中稠密子圖的方法。然而，時序圖中稠密子圖搜索問題則尚未被充分研究。

2 問題定義及相關(guān)概念

本文用G(V,E)表示一個無向時序圖。其中，V和E分別代表節(jié)點(diǎn)集和邊集。用n=|V|和m=|E|分別表示節(jié)點(diǎn)數(shù)量和邊的數(shù)量。每一條時序邊e∈E是一個三元組(u,v,t)。其中u和v都是V中的節(jié)點(diǎn)，并在t時刻上產(chǎn)生聯(lián)系。這里假設(shè)所有時間都是整數(shù)。注意，若t i≠t j，(u,v,t i)和(u,v,t j)將會是兩條不同的時序邊。對于V的一個子集S，用G[S]表示它的誘導(dǎo)子圖，且E(S)={(u,v,t)|u,v∈S,(u,v,t)∈E}表示G[]S中的邊集。用N G(u)={(v,t)|(u,v,t)∈E}表示u在G中的時序鄰居集合。最后，用G′(V′,E′,T C)來表示一個時序圖G在一個時間段T C=[t i,t j]的靜態(tài)投影圖。例如圖2是圖1在時間段[4，6]上的靜態(tài)投影圖。

圖2 圖1在[4，6]上的靜態(tài)投影圖Fig.2 Static projection of Fig.1 in[4，6]

2.1 滑動窗口模型的使用

在靜態(tài)圖中，k-核圖通常是結(jié)構(gòu)內(nèi)聚的。其中，每個節(jié)點(diǎn)都至少有k個鄰居[13-15]。在時序圖中，這種內(nèi)聚子圖通常需要持續(xù)存在一段時間才是有意義的。本研究中用(θ,τ)持續(xù)性k-核圖定義時序圖中的一個持續(xù)出現(xiàn)的內(nèi)聚子圖，并用滑動窗口模型找到這種內(nèi)聚子圖。其中θ將作為滑動窗口的長度。τ將成為一個時序子圖通過滑動窗口計(jì)算的最小有效壽命，后文中會有詳細(xì)定義。接下來將給出在滑動窗口模型的基礎(chǔ)上一個節(jié)點(diǎn)的有效壽命定義。

定義1（節(jié)點(diǎn)有效壽命）給定一個時序圖G(V,E)，節(jié)點(diǎn)u∈V，參數(shù)θ，k。節(jié)點(diǎn)u的有效壽命被定義為：當(dāng)u的度數(shù)在θ長度的滑動窗口內(nèi)大于k時，滑動窗口的移動覆蓋區(qū)間。

例如，當(dāng)核數(shù)k=3，滑動窗口長度θ=2時，v3的在整個時序圖中有效壽命有三段，分別是[0，2]、[4，6]和[9，14]。即滑動窗口在這些時間區(qū)內(nèi)滑動時，v3在滑動窗口內(nèi)的度數(shù)都大于3。

由于在實(shí)際應(yīng)用中，相同時間長度的情況下，連續(xù)不斷的有效壽命比斷斷續(xù)續(xù)的有效壽命更加具有實(shí)際意義。所以在本研究中重新定義一個節(jié)點(diǎn)的有效壽命長度。

定義2（節(jié)點(diǎn)有效壽命長度）時序圖G中的一個節(jié)點(diǎn)u通過θ長度的滑動窗口得到的有效壽命后，其長度δG(u)的計(jì)算方式為：

其中，r表示節(jié)點(diǎn)u的有效壽命中不連續(xù)的極大有效壽命段的數(shù)量，t sp、t ep分別表示第p個極大有效壽命段的開始和結(jié)束時間。例如圖1中，當(dāng)k=3，θ=2時，v3在整個時序圖內(nèi)的有效壽命δG(v)3=(2-0)+(6-4)+(14-9)-2×2=5。

值得注意的是，當(dāng)時序圖結(jié)構(gòu)發(fā)生改變時，一個節(jié)點(diǎn)的有效壽命及壽命長度也要隨之改變。例如圖1中，若只考慮子圖H0={v0,v1,v2,v3}，則節(jié)點(diǎn)v3的壽命將變?yōu)閮啥?，分別是[0，2]和[9，14]。其有效壽命δH0(v)3=(2-0)+(14-9)-1×2=5。

2.2 問題定義及分析

接下來基于以上定義，將給出(θ,τ)持續(xù)性k-核圖模型的定義和本研究的問題定義。

定義3（(θ,τ)持續(xù)性k-核圖）給定一個時序圖G(V,E)，參數(shù)θ、τ、k。在θ長度的滑動窗口模型中，若對于?v∈V，δG(u)＞τ，則G是一個(θ,τ)持續(xù)性k-核圖。

定義4（(θ,τ)持續(xù)性k-核子圖搜索問題）給定一個時序圖G(V,E)，參數(shù)θ、τ、k和一個查詢節(jié)點(diǎn)q。找到一個G中的一個誘導(dǎo)子圖G[]S滿足如下條件：（1）q∈S。（2）G[]S是一個(θ,τ)持續(xù)性k-核圖。（3）G[S]不會被其他滿足條件（1）和（2）的誘導(dǎo)子圖完全包含。

接下來，定理1證明了(θ,τ)持續(xù)性k-核圖搜索問題為NP-難的。

定理1時序圖中包含查詢節(jié)點(diǎn)的(θ,τ)持續(xù)性k-核圖搜索問題是一個NP-難問題。

證明 此處可將(θ,τ)持續(xù)性k-核子圖搜索問題轉(zhuǎn)化為包含查詢節(jié)點(diǎn)的子圖檢測問題。在得到一個時序圖G之后，新建一個虛擬節(jié)點(diǎn)q作為查詢節(jié)點(diǎn)。令q與圖G中所有節(jié)點(diǎn)在G中出現(xiàn)的每一個時間戳上都有一條時序邊相連，將這個新構(gòu)造的虛擬圖(G∪q)記為G*。根據(jù)構(gòu)造條件，G*中的任何(θ,τ)持續(xù)性k-核子圖都包含q，因此G*上的搜索問題就轉(zhuǎn)化為G中(θ,τ)持續(xù)性k-核圖檢測問題，而這一問題已經(jīng)被證明是NP-難的[6]，所以本研究的問題同樣是NP-難的。

3 搜索算法

在搜索算法開始之前，需要對時序圖進(jìn)行預(yù)處理以對時序圖進(jìn)行初步削減，隨后在削減后的時序圖中進(jìn)行搜索算法找到目標(biāo)子圖。首先通過滑動窗口模型算法構(gòu)建一個θ長度的窗口，并令其在時序圖的時間戳范圍內(nèi)滑動，以窗口右端作為窗口的位置，記錄滑動窗口在每一個時間戳上，每一個節(jié)點(diǎn)在窗口內(nèi)的度數(shù)，以此構(gòu)成一個度數(shù)時序矩陣J。其中J[i][j]表示節(jié)點(diǎn)v i在滑動窗口走到時間戳t=j時的度數(shù)。在得到查詢節(jié)點(diǎn)q，參數(shù)k、θ、τ之后，可以通過矩陣J，得出所有節(jié)點(diǎn)的有效壽命，刪除那些與查詢節(jié)點(diǎn)的壽命交集小于τ的節(jié)點(diǎn)，將剩余節(jié)點(diǎn)計(jì)入候選節(jié)點(diǎn)集Ca，Ca中將可能包含一個(θ,τ)持續(xù)性k-核圖。接下來，本章中提出兩種基于枚舉的算法找到這個子圖。

3.1 S-Global算法

在預(yù)處理部分得到候選節(jié)點(diǎn)集Ca之后，本算法從全局的角度出發(fā)，即從所有候選節(jié)點(diǎn)與查詢節(jié)點(diǎn)構(gòu)成的子圖開始，在每一次的枚舉中找出一個待刪除的節(jié)點(diǎn)集合，然后判斷剩余的節(jié)點(diǎn)集合能否構(gòu)成一個符合要求的結(jié)果。

算法1是本算法的詳細(xì)細(xì)節(jié)。其中R是最終要找到的極大結(jié)果子圖集合，De是每次枚舉過程中要刪除的節(jié)點(diǎn)集合，Safe是安全節(jié)點(diǎn)集合（第1行）。當(dāng)?shù)玫揭粋€候選節(jié)點(diǎn)集之后首先將Ca中的所有節(jié)點(diǎn)按其靜態(tài)投影度數(shù)排序（第2行）。在第一次遞歸中需要判斷Ca是否滿足(θ,τ)持續(xù)性k-核圖的條件，若滿足，則Ca構(gòu)成的誘導(dǎo)子圖就是圖G中的極大結(jié)果（第3行）。若不滿足，則進(jìn)入之后的遞歸操作。每一次按照順序?qū)⒁粋€節(jié)點(diǎn)u加入進(jìn)De準(zhǔn)備刪除（第5行），對于剩余的子圖，先判斷其有效壽命是否大于τ（第6行），若大于τ，則這個子圖中的極大k-核圖就是一個極大結(jié)果，將其代入R并停止遞歸（第12行）。否則，繼續(xù)向后按順序?qū)之后的節(jié)點(diǎn)進(jìn)行遞歸判斷（第17行）。當(dāng)一個節(jié)點(diǎn)完成遞歸之后，保留這個節(jié)點(diǎn)作為安全節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)集Safe（第18行）。注意，每次更新子圖時都要對度數(shù)時序矩陣J進(jìn)行更新（第11和19行）所有遞歸判斷完成后，將R內(nèi)的所有子圖輸出作為結(jié)果（第4行）。

為了減少枚舉，也就是遞歸判斷的次數(shù)，本算法中使用了三個枚舉約簡規(guī)則：

規(guī)則1當(dāng)枚舉到一個節(jié)點(diǎn)u時，若剩余子圖的有效壽命已經(jīng)大于τ，則無需枚舉u之后的節(jié)點(diǎn)。

規(guī)則2當(dāng)枚舉到一個節(jié)點(diǎn)u時，如果存在某個Safe中的節(jié)點(diǎn)不滿足k-核條件，則本次枚舉失效。

規(guī)則3在枚舉一個節(jié)點(diǎn)u之前，若Safe集合構(gòu)成的子圖壽命小于τ，則u及u之后的節(jié)點(diǎn)都無需枚舉。

以圖1為例，假設(shè)q=v0，θ=2，τ=5，k=3，最初Safe={v0}，Ca={v2,v3,v6,v1,v4,v5}。顯然q與Ca內(nèi)的節(jié)點(diǎn)不能直接構(gòu)成一個(θ,τ)持續(xù)性k-核圖。將v2加入De。此時由于G[Ca/De]的有效壽命小于τ，根據(jù)枚舉約簡規(guī)則1繼續(xù)將Ca內(nèi)v2后面的節(jié)點(diǎn)加入De中，直到De={v6,v4,v5}，Ca/De={v2,v3,v1}。此時G[Ca/De]的有效壽命為[0,2]∪[9,14]，有效壽命長度是6，大于τ，與此同時，G[(Ca/De)∪q]的靜態(tài)投影是一個k-核圖，則將這個子圖保存至R中。當(dāng)所有枚舉操作完成后，得到本例的唯一結(jié)果子圖{v2,v3,v1,v0}。

由于本算法涉及到枚舉操作，枚舉Ca中節(jié)點(diǎn)的所有組合，所以本算法的時間復(fù)雜度為O(2nCa)，n Ca是Ca中的節(jié)點(diǎn)個數(shù)。但由于枚舉約簡規(guī)則的存在，算法的實(shí)際運(yùn)行時間將遠(yuǎn)遠(yuǎn)小于2n Ca。

3.2 S-Center算法

在S-Global算法中，由于需要遍歷整個Ca構(gòu)成的子圖，當(dāng)Ca內(nèi)節(jié)點(diǎn)數(shù)量較多時，這一枚舉算法將產(chǎn)生較大的時間開銷。本節(jié)中提出的S-Center算法將從查詢節(jié)點(diǎn)出發(fā)，每次枚舉其鄰域中的一個節(jié)點(diǎn)進(jìn)入子圖，直到找到一個極大的(θ,τ)持續(xù)性k-核圖。在進(jìn)行該算法之前，首先要將Ca中的所有節(jié)點(diǎn)進(jìn)行分層，令查詢節(jié)點(diǎn)在第0層，其余所有節(jié)點(diǎn)的層數(shù)是其到查詢節(jié)點(diǎn)的最短距離。隨后在算法中，與S-Global中的枚舉方式類似，在對Ca中的節(jié)點(diǎn)排序之后，每一次枚舉一個節(jié)點(diǎn)進(jìn)入待查子圖中，但不同的是，在一個節(jié)點(diǎn)進(jìn)入子圖后，隨后枚舉的節(jié)點(diǎn)只有這個節(jié)點(diǎn)下一層的節(jié)點(diǎn)與同層該節(jié)點(diǎn)之后的其他節(jié)點(diǎn)。

算法2描述了S-Center算法的詳細(xì)過程。此處用到的兩個集合分別是結(jié)果子圖集合R和當(dāng)前的待查子圖節(jié)點(diǎn)集Sub（第1行）。在得到候選節(jié)點(diǎn)集Ca后，為節(jié)點(diǎn)分層并排序，同時記錄每一層中節(jié)點(diǎn)個數(shù)（第2~4行），然后開始在q的鄰域中進(jìn)行枚舉（第5、6行）。在每一次枚舉操作中，如果當(dāng)前枚舉的節(jié)點(diǎn)u加入子圖后子圖的有效壽命仍然大于τ，則這個節(jié)點(diǎn)可以加入Sub中（第8、9行）。此時若G[Sub]的靜態(tài)投影是一個k-核圖，則說明G[ ]Sub是一個(θ,τ)持續(xù)性k-核圖。更新R中的結(jié)果以維護(hù)極大結(jié)果集合（第10~13行）。然后繼續(xù)進(jìn)行枚舉操作（第14~20行）。

在枚舉過程中，同樣有3個枚舉約簡規(guī)則來減少枚舉操作的次數(shù)：

規(guī)則4當(dāng)枚舉到一個節(jié)點(diǎn)u時，若這個節(jié)點(diǎn)進(jìn)入待查子圖后子圖的有效壽命小于τ，則節(jié)點(diǎn)u無需加入子圖。

規(guī)則5當(dāng)一個節(jié)點(diǎn)v加入待查子圖后，如果子圖中存在一個與v隔層的節(jié)點(diǎn)度數(shù)仍然小于k，則本次枚舉失效。

規(guī)則6當(dāng)枚舉到一個節(jié)點(diǎn)v時，記m′為當(dāng)前子圖中v上一層節(jié)點(diǎn)的最小度數(shù)，n′為與v同層節(jié)點(diǎn)中未進(jìn)入子圖的數(shù)量。若m′+n′

同樣，以圖1為例，假設(shè)q=v0,θ=2,τ=5,k=3，由于圖中所有節(jié)點(diǎn)都在同一層中，所以Ca={v2,v3,v6,v1,v4,v5}。最初待查子圖內(nèi)只有v0，壽命為[0,7]∪[9,14]。然后將v2加入子圖，壽命為[0,3]∪[7,14]。下一次將v3加入子圖，此時壽命為[0,3]∪[9,14]，下一次枚舉的節(jié)點(diǎn)v6加入子圖之后壽命長度小于5。根據(jù)枚舉約簡規(guī)則4，v6節(jié)點(diǎn)無需進(jìn)入子圖。然后將下一個節(jié)點(diǎn)v1加入子圖。此時子圖內(nèi)的節(jié)點(diǎn){v2,v3,v1,v0}。能構(gòu)成一個（2，5）持續(xù)性3-核圖，將其記錄進(jìn)入R。當(dāng)所有枚舉操作完成后，得出唯一的極大結(jié)果{v2,v3,v1,v0}。

由于S-Center同樣是一個基于枚舉的算法，所以這個算法的時間復(fù)雜度依然是O(2nCa)，但由于三個枚舉約簡規(guī)則的存在，這個算法的實(shí)際運(yùn)行時間同樣遠(yuǎn)遠(yuǎn)小于2nCa。而且S-Center無需全局遍歷Ca中的所有節(jié)點(diǎn)，這進(jìn)一步的提高了效率。

在本算法中，每次遞歸都從待查子圖的鄰域中枚舉一個節(jié)點(diǎn)，并且找到一個查詢結(jié)果后，算法不會停止，而是繼續(xù)進(jìn)行遞歸操作找到一個極大結(jié)果。因此在不考慮約簡規(guī)則的情況下，這一算法始終可以找到一個精確的極大結(jié)果。而約簡規(guī)則只會刪除那些一定不在查詢結(jié)果的枚舉集合。所以S-Center算法在查詢節(jié)點(diǎn)有效時，始終可以找到一個精確的極大結(jié)果。

3.3 兩種搜索算法的比較

本節(jié)中給出兩種算法的時間復(fù)雜度。兩種算法都采用了枚舉的思路，對于S-Global算法來說，每次枚舉的節(jié)點(diǎn)是要刪除的節(jié)點(diǎn)集合，而候選節(jié)點(diǎn)中剩余的節(jié)點(diǎn)作為待查子圖。那么當(dāng)待查子圖內(nèi)節(jié)點(diǎn)數(shù)小于k+1時，這個子圖一定不會是查詢結(jié)果，則這一算法的實(shí)際運(yùn)行時間復(fù)雜度為：顯然，當(dāng)候選子圖G[ ]Ca與結(jié)果子圖相差不多時，這一算法將更快地得到結(jié)果。該種情況一般在查詢節(jié)點(diǎn)有效壽命較長，時序圖更加稠密時發(fā)生。對于S-Center算法來說，算法中枚舉的節(jié)點(diǎn)集的誘導(dǎo)子圖本身就是待查子圖。顯然，這一算法的時間復(fù)雜度與G[Ca]內(nèi)節(jié)點(diǎn)的層數(shù)有關(guān)。當(dāng)G[Ca]內(nèi)所有節(jié)點(diǎn)的層數(shù)相同時，枚舉算法將會遍歷候選字圖中的所有節(jié)點(diǎn)，其最壞時間復(fù)雜度為O(2nCa)。當(dāng)節(jié)點(diǎn)分層較多時，由于枚舉到某一節(jié)點(diǎn)時，隔層以上的節(jié)點(diǎn)將不會被枚舉。假設(shè)候選節(jié)點(diǎn)集共分為s層，則此時算法的實(shí)際時間復(fù)雜度為。其中N i是G[Ca]第i層節(jié)點(diǎn)的數(shù)量。顯然，當(dāng)G[Ca]分層較多時，這一算法將更快得到結(jié)果。該種情況一般出現(xiàn)于查詢節(jié)點(diǎn)有效壽命較短，時序圖較為稀疏的條件下。

4 實(shí)驗(yàn)

本章中通過一些真實(shí)的數(shù)據(jù)源驗(yàn)證算法的有效性及運(yùn)行效率，并通過一些對比實(shí)驗(yàn)說明參數(shù)對算法性能的影響。兩種算法都由C++編寫，運(yùn)行環(huán)境為Windows Server 2012 R2操作系統(tǒng)，Inter?Xeon?Platinum 8163，2.49 GHz CPU和16 GB內(nèi)存。

4.1 數(shù)據(jù)集

本文中取4個不同的真實(shí)世界的時序圖數(shù)據(jù)源進(jìn)行研究。數(shù)據(jù)源的詳細(xì)情況見表1。其中，|V|、|E|、|E′|、|T|和dmax分別是時序圖中的節(jié)點(diǎn)數(shù)，時序邊數(shù)，靜態(tài)投影邊數(shù)，時間戳范圍和節(jié)點(diǎn)的最大靜態(tài)投影度數(shù)。HS2013是從sociopatterns網(wǎng)站上下載的面對面交互網(wǎng)絡(luò)，時間戳單位為h。LKML和ENRON是從konect網(wǎng)站上下載的時序社交網(wǎng)絡(luò)，單位是月。DBLP是DBLP計(jì)算機(jī)科學(xué)文獻(xiàn)庫中的作家協(xié)作網(wǎng)絡(luò)，單位是年。

表1 時序圖數(shù)據(jù)集的參數(shù)Table 1 Parameters of temporal graph datasets

4.2 參數(shù)設(shè)定

本文中的兩個算法都涉及到了三個參數(shù)θ、τ、k。其中θ、τ作為時序參數(shù)用于確定滑動窗口的長度和子圖的最短持續(xù)時間，k用于確定子圖的結(jié)構(gòu)內(nèi)聚性。本文中的實(shí)驗(yàn)部分將每個數(shù)據(jù)源需要的3個參數(shù)各變化3次，且每一組參數(shù)都取5個不同的查詢節(jié)點(diǎn)進(jìn)行5次實(shí)驗(yàn)，并記錄其運(yùn)行結(jié)果的平均值作為實(shí)驗(yàn)結(jié)果。具體的取值情況如表2所示。

表2 不同數(shù)據(jù)源上的實(shí)驗(yàn)參數(shù)Table 2 Experimental parameters in different datasets

4.3 時間約束對算法性能的影響

本節(jié)中固定每組數(shù)據(jù)源的參數(shù)k，然后分別固定參數(shù)θ和τ并改變另一個參數(shù)，以確定這兩個參數(shù)對算法性能的影響。圖3中的4幅圖為變化參數(shù)θ時兩種算法及預(yù)處理過程在4個數(shù)據(jù)源上的運(yùn)行時間。通過這4幅圖可以得出，當(dāng)θ越大時，算法的運(yùn)行時間越長。這是因?yàn)楫?dāng)θ變大時，同一條時序邊會計(jì)入更多的滑動窗口中。圖4的4幅圖為變化參數(shù)τ時兩種算法在4個數(shù)據(jù)源上的運(yùn)行時間。由于當(dāng)τ變大時，更多的時序邊不滿足有效壽命的約束條件，所以算法的運(yùn)行時間會變短。值得一提的是，S-global算法有時會出現(xiàn)運(yùn)行速度過小的情況，例如圖3（d）、圖4（b）和圖4（d）。這是因?yàn)橛行r候G[Ca]本身就能構(gòu)成一個(θ,τ)持續(xù)性k-核圖，在S-Global算法中無需進(jìn)行更多的枚舉操作，這大大降低了算法的運(yùn)行時間。

圖3 變化參數(shù)θ時的運(yùn)行時間Fig.3 Run time when varyingθ

圖4 變化參數(shù)τ時的運(yùn)行時間Fig.4 Run time when varyingτ

4.4 結(jié)構(gòu)約束對算法性能的影響

本實(shí)驗(yàn)中將固定θ、τ，改變參數(shù)k并觀察其對算法運(yùn)行時間的影響。圖5顯示了本實(shí)驗(yàn)的結(jié)果。實(shí)驗(yàn)結(jié)果表明，k值變大時，兩個算法的運(yùn)行時間都變短。這是因?yàn)?，?dāng)k值變大時，滿足結(jié)構(gòu)約束的節(jié)點(diǎn)變得更少，也就是說，候選節(jié)點(diǎn)集Ca中的節(jié)點(diǎn)邊更少。同時實(shí)驗(yàn)中發(fā)現(xiàn)，算法的運(yùn)行時間與Ca的規(guī)模與結(jié)果子圖規(guī)模的關(guān)系密切相關(guān)，當(dāng)Ca規(guī)模與結(jié)果子圖規(guī)模相差較大時，S-Center的運(yùn)行速度較快，反之，S-Global的運(yùn)行速度較快。

圖5 變化參數(shù)k時程序的運(yùn)行時間Fig.5 Run time when varying k

4.5 枚舉削減規(guī)則對運(yùn)行效率的影響

本實(shí)驗(yàn)記錄了兩種算法在運(yùn)行過程中枚舉操作的執(zhí)行次數(shù)，同時記錄了不同參數(shù)下每組實(shí)驗(yàn)的候選節(jié)點(diǎn)集Ca的情況，以此可以估算出不考慮枚舉削減規(guī)則時的預(yù)計(jì)枚舉次數(shù)。表3展示了本次實(shí)驗(yàn)的詳細(xì)結(jié)果。其中n Ca表示候選節(jié)點(diǎn)集Ca的節(jié)點(diǎn)個數(shù)，l Ca表示候選節(jié)點(diǎn)集的分層數(shù)，PGlobal、PCenter分別表示S-Global算法和S-Center算法運(yùn)行時的枚舉次數(shù)。從表中可以看出，兩種算法中的枚舉削減規(guī)則都能夠極大地減少枚舉次數(shù)。在Ca與查詢結(jié)果非常接近時，S-Global算法的枚舉次數(shù)將大幅減少，反之，Ca與查詢結(jié)果相差較大時，S-Center算法更具優(yōu)勢。

表3 枚舉次數(shù)統(tǒng)計(jì)Table 3 Statistics of enumeration times

4.6 算法的內(nèi)存開銷

本實(shí)驗(yàn)考察了兩種算法在4個數(shù)據(jù)集上的內(nèi)存開銷情況。表4記錄了本實(shí)驗(yàn)中不同數(shù)據(jù)源在不同參數(shù)情況下的平均內(nèi)存開銷。表內(nèi)的第一列為數(shù)據(jù)源本身占用的內(nèi)存大小。從結(jié)果中可以看出，兩種算法的內(nèi)存開銷幾乎相同，原因是兩種算法均采用了基于深度優(yōu)先包含枚舉的策略。同時，發(fā)現(xiàn)兩種算法參數(shù)變化對內(nèi)存開銷影響較小，原因是（1）在不同參數(shù)下，經(jīng)過預(yù)處理后得到的候選節(jié)點(diǎn)集Ca的規(guī)模通常很小，該結(jié)論能夠通過表3中的n Ca數(shù)量得到驗(yàn)證。（2）由于兩種算法均采用基于深度優(yōu)先的枚舉策略，在搜索過程中只需保存枚舉中當(dāng)前搜索分支的中間結(jié)果，而且由于兩種算法均采用了削減規(guī)則，樹中搜索分支不會過深。為此，即使n Ca大小有所不同，內(nèi)存開銷影響也不大。因此從理論上證明兩種算法參數(shù)變化幾乎不影響內(nèi)存開銷。多次不同的實(shí)驗(yàn)也驗(yàn)證了該結(jié)論。此外，ENORN數(shù)據(jù)源上的內(nèi)存開銷遠(yuǎn)遠(yuǎn)大于其數(shù)據(jù)源，因?yàn)镋NORN數(shù)據(jù)源的時間戳范圍跨度很大。

表4 不同數(shù)據(jù)源上的內(nèi)存開銷Table 4 Memory overhead on different datasets MB

4.7 時間約束對結(jié)果質(zhì)量的影響

本實(shí)驗(yàn)中將固定每組數(shù)據(jù)源的k值，然后分別固定參數(shù)θ和τ并改變另一個參數(shù)，以記錄時間約束對結(jié)果質(zhì)量的影響。對于每一組實(shí)驗(yàn)得到的結(jié)果子圖，用一個系數(shù)表示子圖的稠密程度。其中m′表示子圖內(nèi)的靜態(tài)邊數(shù)，n表示子圖內(nèi)的節(jié)點(diǎn)數(shù)。顯然D值越大，結(jié)果子圖越稠密。表5中的4張表展示了參數(shù)θ對查詢結(jié)果的影響?？梢钥闯觯鹊拇笮∨c結(jié)果內(nèi)子圖的節(jié)點(diǎn)數(shù)量和邊數(shù)量都呈正相關(guān)，因?yàn)橥粭l邊會被包含在更多的滑動窗口中，節(jié)點(diǎn)的有效壽命會變長。但當(dāng)子圖內(nèi)節(jié)點(diǎn)數(shù)量突然增多時，子圖的密度會有所降低。因?yàn)閮煞N算法都旨在找到數(shù)據(jù)源中的極大結(jié)果，且k值是固定的。表6中的4張子表展示了參數(shù)τ對查詢結(jié)果的影響。顯然，τ的大小與結(jié)果內(nèi)子圖的節(jié)點(diǎn)數(shù)量和邊數(shù)量都呈負(fù)相關(guān)，且與表4結(jié)論類似，子圖內(nèi)節(jié)點(diǎn)數(shù)量突然減少時，子圖的密度會有所增加。

表5 參數(shù)θ對查詢結(jié)果的影響Table 5 Effect of parameterθon query results

表6 參數(shù)τ對查詢結(jié)果的影響Table 6 Effect of parameterτon query results

5 結(jié)語

本文研究了時序圖中的稠密子圖搜索這一新穎的問題。本研究利用(θ,τ)持續(xù)性k-核子圖這一模型定義了時序圖中的一種稠密子圖概念，在去除干擾節(jié)點(diǎn)后的候選節(jié)點(diǎn)集，也就是削減后的時序圖中，設(shè)計(jì)了兩種算法，從兩種不同的角度枚舉這個時序圖中的節(jié)點(diǎn)集合，來找出能夠組成一個(θ,τ)持續(xù)性k-核圖的極大節(jié)點(diǎn)集作為搜索結(jié)果。在枚舉過程中，通過一些高效的削減規(guī)則來大幅度減少枚舉的執(zhí)行次數(shù)增強(qiáng)算法的效率。最后，本文通過實(shí)驗(yàn)在四個時序圖中驗(yàn)證了提出算法的高效性和有效性，并給出了兩種算法應(yīng)用于不同場景的建議。