大規(guī)模時(shí)序圖中持續(xù)性稠密子圖搜索算法研究

李 源，劉金生，趙會(huì)群，孫 晶

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

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

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

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

本研究首先證明了時(shí)序圖中查詢(θ,τ)持續(xù)性k-核子圖是NP-難問(wèn)題。為解決這一問(wèn)題，本文提出通過(guò)全局和局部?jī)煞N思路設(shè)計(jì)的算法，分別命名為S-Global和S-Center算法。其中S-Global算法從全局角度出發(fā)，不斷刪除不滿足條件的節(jié)點(diǎn)，最后得到一個(gè)極大的(θ,τ)持續(xù)性k-核圖。在此過(guò)程中，將通過(guò)提出的削減規(guī)則減少搜索空間。另一個(gè)算法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)是無(wú)需遍歷整個(gè)時(shí)序圖。在四個(gè)真實(shí)世界網(wǎng)絡(luò)中的大量實(shí)驗(yàn)，驗(yàn)證了提出算法的高效性。其中S-Global算法更適用于時(shí)序圖較為稠密的場(chǎng)景，而S-Center算法則適用于稀疏圖場(chǎng)景。

1 相關(guān)工作

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

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

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

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

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

2.1 滑動(dòng)窗口模型的使用

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

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

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

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

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

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

值得注意的是，當(dāng)時(shí)序圖結(jié)構(gòu)發(fā)生改變時(shí)，一個(gè)節(jié)點(diǎn)的有效壽命及壽命長(zhǎng)度也要隨之改變。例如圖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 問(wèn)題定義及分析

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

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

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

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

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

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

3 搜索算法

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

3.1 S-Global算法

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

算法1是本算法的詳細(xì)細(xì)節(jié)。其中R是最終要找到的極大結(jié)果子圖集合，De是每次枚舉過(guò)程中要?jiǎng)h除的節(jié)點(diǎn)集合，Safe是安全節(jié)點(diǎn)集合（第1行）。當(dāng)?shù)玫揭粋€(gè)候選節(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ū)⒁粋€(gè)節(jié)點(diǎn)u加入進(jìn)De準(zhǔn)備刪除（第5行），對(duì)于剩余的子圖，先判斷其有效壽命是否大于τ（第6行），若大于τ，則這個(gè)子圖中的極大k-核圖就是一個(gè)極大結(jié)果，將其代入R并停止遞歸（第12行）。否則，繼續(xù)向后按順序?qū)之后的節(jié)點(diǎn)進(jìn)行遞歸判斷（第17行）。當(dāng)一個(gè)節(jié)點(diǎn)完成遞歸之后，保留這個(gè)節(jié)點(diǎn)作為安全節(jié)點(diǎn)進(jìn)入節(jié)點(diǎn)集Safe（第18行）。注意，每次更新子圖時(shí)都要對(duì)度數(shù)時(shí)序矩陣J進(jìn)行更新（第11和19行）所有遞歸判斷完成后，將R內(nèi)的所有子圖輸出作為結(jié)果（第4行）。

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

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

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

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

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

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

3.2 S-Center算法

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

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

在枚舉過(guò)程中，同樣有3個(gè)枚舉約簡(jiǎn)規(guī)則來(lái)減少枚舉操作的次數(shù)：

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

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

規(guī)則6當(dāng)枚舉到一個(gè)節(jié)點(diǎn)v時(shí)，記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加入子圖，此時(shí)壽命為[0,3]∪[9,14]，下一次枚舉的節(jié)點(diǎn)v6加入子圖之后壽命長(zhǎng)度小于5。根據(jù)枚舉約簡(jiǎn)規(guī)則4，v6節(jié)點(diǎn)無(wú)需進(jìn)入子圖。然后將下一個(gè)節(jié)點(diǎn)v1加入子圖。此時(shí)子圖內(nèi)的節(jié)點(diǎn){v2,v3,v1,v0}。能構(gòu)成一個(gè)（2，5）持續(xù)性3-核圖，將其記錄進(jìn)入R。當(dāng)所有枚舉操作完成后，得出唯一的極大結(jié)果{v2,v3,v1,v0}。

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

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

3.3 兩種搜索算法的比較

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

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

本章中通過(guò)一些真實(shí)的數(shù)據(jù)源驗(yàn)證算法的有效性及運(yùn)行效率，并通過(guò)一些對(duì)比實(shí)驗(yàn)說(shuō)明參數(shù)對(duì)算法性能的影響。兩種算法都由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個(gè)不同的真實(shí)世界的時(shí)序圖數(shù)據(jù)源進(jìn)行研究。數(shù)據(jù)源的詳細(xì)情況見(jiàn)表1。其中，|V|、|E|、|E′|、|T|和dmax分別是時(shí)序圖中的節(jié)點(diǎn)數(shù)，時(shí)序邊數(shù)，靜態(tài)投影邊數(shù)，時(shí)間戳范圍和節(jié)點(diǎn)的最大靜態(tài)投影度數(shù)。HS2013是從sociopatterns網(wǎng)站上下載的面對(duì)面交互網(wǎng)絡(luò)，時(shí)間戳單位為h。LKML和ENRON是從konect網(wǎng)站上下載的時(shí)序社交網(wǎng)絡(luò)，單位是月。DBLP是DBLP計(jì)算機(jī)科學(xué)文獻(xiàn)庫(kù)中的作家協(xié)作網(wǎng)絡(luò)，單位是年。

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

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

本文中的兩個(gè)算法都涉及到了三個(gè)參數(shù)θ、τ、k。其中θ、τ作為時(shí)序參數(shù)用于確定滑動(dòng)窗口的長(zhǎng)度和子圖的最短持續(xù)時(shí)間，k用于確定子圖的結(jié)構(gòu)內(nèi)聚性。本文中的實(shí)驗(yàn)部分將每個(gè)數(shù)據(jù)源需要的3個(gè)參數(shù)各變化3次，且每一組參數(shù)都取5個(gè)不同的查詢節(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 時(shí)間約束對(duì)算法性能的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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