田朝霞 張 俊 陳 旭 曲賢菲

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

當(dāng)今，動態(tài)性已經(jīng)成為建模為圖和網(wǎng)絡(luò)的數(shù)據(jù)分析系統(tǒng)和應(yīng)用程序的明顯特征，如社交網(wǎng)絡(luò)分析、生物數(shù)據(jù)分析、推薦系統(tǒng)和路徑規(guī)劃[1]。因此，動態(tài)網(wǎng)絡(luò)引起了行業(yè)和學(xué)術(shù)界的重視，實(shí)際上，通常使用動態(tài)網(wǎng)絡(luò)的各種替代術(shù)語，如時態(tài)網(wǎng)絡(luò)、動態(tài)圖、演化網(wǎng)絡(luò)、時間依賴圖和圖流等[1-2]?，F(xiàn)實(shí)世界的網(wǎng)絡(luò)本質(zhì)上是動態(tài)變化的，實(shí)體(節(jié)點(diǎn))不斷建立新的關(guān)系(邊)，移除舊的關(guān)系。分析網(wǎng)絡(luò)的時間維度可以提供有關(guān)其結(jié)構(gòu)和功能的有價(jià)值的見解，例如，可以揭示時間模式、概念漂移、周期性和時間事件等[3]。

稠密子圖發(fā)現(xiàn)是一個基本的圖挖掘問題，已經(jīng)成為廣泛的數(shù)據(jù)分析任務(wù)中的原語，如社區(qū)檢測[4]、事件檢測[5]、鏈接垃圾郵件檢測[6]和計(jì)算生物學(xué)[7]等。在理論計(jì)算機(jī)科學(xué)中已經(jīng)廣泛研究了稠密子圖發(fā)現(xiàn)問題，由于該問題與實(shí)際應(yīng)用的相關(guān)性，在社區(qū)數(shù)據(jù)挖掘中引起了相當(dāng)大的關(guān)注。社交網(wǎng)絡(luò)中緊密連接的用戶可能對應(yīng)于社區(qū)，也就是有相似興趣或與同一組織(例如大學(xué)或公司)相關(guān)聯(lián)的用戶組。突然在推文中共同出現(xiàn)的城市、個人和公司名稱等實(shí)體可能表明涉及相應(yīng)實(shí)體的事件正在發(fā)生[2]。

在現(xiàn)實(shí)應(yīng)用中，圖數(shù)據(jù)會隨時間發(fā)生動態(tài)變化，也就是所謂的時態(tài)圖，時態(tài)圖有兩種變化形式：一種是圖的拓?fù)浣Y(jié)構(gòu)變化，圖中的節(jié)點(diǎn)和邊隨時間發(fā)生插入和刪除，從而導(dǎo)致圖的結(jié)構(gòu)發(fā)生變化；另一種是圖的內(nèi)容變化，圖中的節(jié)點(diǎn)和邊所表征的數(shù)據(jù)值或者對象內(nèi)容發(fā)生變化。本文更多關(guān)注時態(tài)圖的拓?fù)浣Y(jié)構(gòu)變化對稠密子圖發(fā)現(xiàn)結(jié)果的影響。當(dāng)處理時態(tài)網(wǎng)絡(luò)時，首先要確定如何處理時間維度，即識別哪段時間是可以發(fā)現(xiàn)稠密子圖的時間間隔。本文算法不是先驗(yàn)地定義這些間隔，而是研究自動識別稠密子圖的間隔的問題，因此能夠在時態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)一系列稠密子圖，捕獲網(wǎng)絡(luò)生命周期中發(fā)生的有趣事件的演變。

為了得到更具體的理解，請考慮以下幾種場景的事例：

(1) 許多不同機(jī)構(gòu)的一組研究人員正在合作開展一個大型項(xiàng)目，小組成員參加他們各自的日?；顒?，但每隔幾周或幾個月，在項(xiàng)目會議或可交付的截止日期之前，小組成員間會參與許多與項(xiàng)目有關(guān)的活動。

(2) 一群Twitter用戶對某一技術(shù)產(chǎn)品感興趣，他們積極地在博客評論并互相評論彼此的帖子，盡管這之間的相互聯(lián)系非常稀疏，但持續(xù)時間長，并且在新產(chǎn)品發(fā)布之后顯著增強(qiáng)。

(3) 在線社交媒體中的故事識別[8]通過實(shí)體之間的稠密子圖自動發(fā)現(xiàn)新興故事，了解故事如何隨時間的推移而演變。例如，當(dāng)一個故事消失另一個故事出現(xiàn)時，實(shí)體間的一個稠密子圖消失，另一個出現(xiàn)。通過將時態(tài)網(wǎng)絡(luò)的時間線分割成區(qū)間，并識別每個間隔中的稠密子圖，可以捕捉主要故事隨時間的演變。

對于時態(tài)網(wǎng)絡(luò)，只有很少的論文提出了發(fā)現(xiàn)時間上連續(xù)的最稠密子圖的方法。與本文工作最相似的是找到所有或k個快照中存在的重子圖[8]，另一個相關(guān)工作側(cè)重在時態(tài)網(wǎng)絡(luò)中找到由k個散亂區(qū)間覆蓋的稠密子圖[9]。然而這兩種方法都只發(fā)現(xiàn)了一個最稠密子圖。

本文的目標(biāo)是研究在滑動時間窗中發(fā)現(xiàn)稠密子圖的問題，為了實(shí)現(xiàn)這一目標(biāo)，采用動態(tài)稠密子圖的現(xiàn)有工作設(shè)計(jì)一個快速的近似算法，結(jié)合滑動時間窗將時態(tài)網(wǎng)絡(luò)劃分成k個非重疊的間隔，使得間隔內(nèi)能夠發(fā)現(xiàn)最大稠密子圖。

本文的主要思路如下：

(1) 研究了滑動時間窗中的最大稠密子圖問題，利用動態(tài)稠密子圖的現(xiàn)有工作，設(shè)計(jì)一個快速的動態(tài)近似算法。

(2) 結(jié)合時間窗大小將時態(tài)網(wǎng)絡(luò)的時間線分割成k個非重疊間隔，每個間隔內(nèi)能夠發(fā)現(xiàn)具有最大密度的子圖。

(3) 在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文方法的有效性，并解釋結(jié)果的合理性。

1 相關(guān)工作

在稠密子圖中對圖進(jìn)行分區(qū)是一個公認(rèn)的問題，現(xiàn)有研究大部分采用密度定義的平均度概念[10]，在此定義下，可以在多項(xiàng)式時間內(nèi)找到最稠密子圖[11]。另外，Charikar[12]開發(fā)了一個近似貪婪算法，它在圖大小的線性時間內(nèi)運(yùn)行。Epasto等[2]開發(fā)了在流式場景中維護(hù)平均度最稠密子圖的算法。其他密度定義通常難以通過有效的啟發(fā)式方法得到問題的近似解。

現(xiàn)有研究大都關(guān)注動態(tài)圖，建立節(jié)點(diǎn)和邊添加或刪除的模型，研究網(wǎng)絡(luò)演化的不同方面，包括稠密集群的演化[13]。另一種建模時態(tài)圖的經(jīng)典方法是圖快照，分別在每個快照中(或合并先前快照的信息)找到結(jié)構(gòu)，然后總結(jié)已發(fā)現(xiàn)結(jié)構(gòu)的歷史行為[14]。這些方法側(cè)重于快照中發(fā)現(xiàn)的稠密結(jié)構(gòu)的時間一致性，并假設(shè)已經(jīng)給出了快照。與此不同，本文工作是將瞬時交互聚合到任意長度的時間軸分區(qū)中。

許多動態(tài)圖研究致力于事件檢測問題，Akoglu等[15]涵蓋了該主題的最新研究，大部分研究側(cè)重比較不同的圖快照，目的是檢測圖結(jié)構(gòu)發(fā)生重大變化的快照。與其他事件檢測問題相比，本文研究主要目標(biāo)是同時發(fā)現(xiàn)事件的子圖和相應(yīng)的時間間隔。與動態(tài)圖事件檢測類似，構(gòu)建一個包含時態(tài)信息的靜態(tài)圖(或一系列靜態(tài)圖)是動態(tài)圖研究的常用方法， Rosvall等[16]的動態(tài)聚類方法將時間數(shù)據(jù)嵌入到靜態(tài)圖中，使用歷史時態(tài)數(shù)據(jù)學(xué)習(xí)二跳路徑的概率以產(chǎn)生聚類。但發(fā)現(xiàn)的聚類在時間上是全局的，沒有檢測到相關(guān)的突發(fā)時間間隔，并且沒有時間約束。

與本文工作最相似的是Rozenshtein等[9]的研究，考慮了在時態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)最稠密子圖的問題，然而他們并不旨在創(chuàng)建時間分區(qū)，且他們發(fā)現(xiàn)的是邊出現(xiàn)在k個短間隔內(nèi)的單一的稠密子圖。本文工作是劃分間隔并僅考慮跨越連續(xù)間隔的圖。Semertzidis等[8]考慮一組圖快照，并搜索一個或多個間隔誘導(dǎo)的單個重子圖，探索持久性重子圖問題的不同公式，包括最大平均密度。Bogdanov等[17]提出了在時間演變網(wǎng)絡(luò)中挖掘重子圖的方法，但其仍然是基于網(wǎng)絡(luò)快照，因此對邊界量化效果很敏感，且發(fā)現(xiàn)的重子圖的概念基于邊權(quán)重而不是基于密度。

總之，與已有研究相比，本文希望能夠在時態(tài)網(wǎng)絡(luò)中發(fā)現(xiàn)一系列稠密子圖，捕獲網(wǎng)絡(luò)生命周期中發(fā)生的有趣事件的演變。

2 時態(tài)稠密子圖問題定義

(1)

(2)

下面介紹與稠密子圖相關(guān)的其他概念：圖核、核心分解和頂點(diǎn)的誘導(dǎo)核心子圖。

V=C0?C1?…?Cl??

(3)

其中每個Ci都是一個j-core。

另外，使用κH(v)表示由H誘導(dǎo)的子圖中頂點(diǎn)v的核數(shù)，G(H)=(H,E(H))的子圖的最大核(或主核)用Cl(H)表示，G的主核僅用Cl表示。

換言之，誘導(dǎo)子圖包含可從v到達(dá)并具有相同核數(shù)κ(v)的所有頂點(diǎn)。

本文在滑動時間窗邊流中處理圖，根據(jù)這個模型，問題的輸入是邊流形式，邊ei是流的第i個元素，即邊ei有時間戳i，滑動窗口Wt(x)定義為在時刻t長度為x的et-x+1和et間到達(dá)的所有邊的集合：

Wt(x)={ei,i∈[t-x+1,t]}

(4)

對于每條邊ei=(u,v)，u和v出現(xiàn)在時刻i，使用Vt(x)表示時刻t出現(xiàn)在長度為x的滑動窗口中的頂點(diǎn)集，在時刻t長度為x的滑動窗口中的圖定義為Gt(x)=(Vt(x),Wt(x))。

下面定義本文研究的問題，即以滑動時間窗進(jìn)行分割，在時態(tài)網(wǎng)絡(luò)中找到一系列稠密子圖。

3 時態(tài)稠密子圖發(fā)現(xiàn)算法

本文算法的目標(biāo)是在線更新稠密子圖，但動態(tài)流更新稠密子圖有兩個問題：① 如何減少稠密子圖的搜索空間；② 如何分割整個圖得到子圖。

為了解決上述問題，本文提出兩個假設(shè)性判斷。首先，由于稠密子圖由相對高度的頂點(diǎn)形成，可以通過僅跟蹤這些高度頂點(diǎn)找到稠密子圖；其次，這些子圖可以在圖更新時進(jìn)行局部更新，而不影響圖的其他部分。

基于這兩點(diǎn)，本文提出一種新算法，通過僅考慮高度節(jié)點(diǎn)減少搜索空間，并將整個圖劃分為更小的子圖，從每個子圖中找到稠密子圖。

3.1 存儲高度頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

提出一個增量數(shù)據(jù)結(jié)構(gòu)，存儲一個強(qiáng)連接的子圖，用D表示，子圖維護(hù)以下不變量：①D內(nèi)的每個頂點(diǎn)v∈D的核數(shù)κD(v)等于D的主核(Ce(D))；②D內(nèi)所有的頂點(diǎn)是連通的。這些不變量確保D中的所有頂點(diǎn)具有相同的核數(shù)，根據(jù)定義這是D的主核。在處理圖更新時，D會維護(hù)這些不變量。

圖1 存儲高度頂點(diǎn)的數(shù)據(jù)結(jié)構(gòu)圖

3.2 添加頂點(diǎn)/邊操作

1) 添加頂點(diǎn)操作。如第2節(jié)所述，更新以邊流的形式出現(xiàn)，定義了添加頂點(diǎn)算法，作為添加邊算法的子程序，當(dāng)添加邊中至少一個頂點(diǎn)是高度頂點(diǎn)時觸發(fā)此算法，需要考慮兩種情況：(1) 包已經(jīng)包含高度頂點(diǎn)；(2) 包不包含高度頂點(diǎn)。在這兩種情況下，目標(biāo)是將新頂點(diǎn)添加到一個D。

算法1描述了添加頂點(diǎn)的算法，對于第一種情況，算法掃描包找到包含頂點(diǎn)的D并返回它，對于第二種情況，算法首先識別候選D，然后將頂點(diǎn)分配給其中一個候選D，候選D具有小于或等于新頂點(diǎn)內(nèi)度的主核數(shù)(κu(D)≥Ce(D))，在候選D中新頂點(diǎn)被分配給具有最大內(nèi)度du(D)的D。

頂點(diǎn)加入到D中，D的核數(shù)可能會增加，需要刪除核數(shù)低于D的主核的頂點(diǎn)，通過類似bin排序的方法基于度對頂點(diǎn)進(jìn)行排序，可以在線性時間內(nèi)有效更新稠密子圖。

算法1添加頂點(diǎn)算法

1.H*←?;

2. forDi∈Bdo

/*識別候選D*/

3. ifu∈Dithen

/*找到包含頂點(diǎn)的D*/

4. returnDi;

5. if (dDi(u)≥Ce(Di) andρH*<ρDi)then

6.H*←Di;

/*候選D具有小于或等于新頂點(diǎn)內(nèi)度的主核數(shù)*/

7. ifH*=? then

8.H*←{u};

9. elseH*←H*∪{u}

10. returnH*;

2) 添加邊操作。在這種情況下，只有當(dāng)添加邊的至少一個頂點(diǎn)是高度頂點(diǎn)時，才會影響包的狀態(tài)， 需要考慮兩種情況：(1) 只有一個頂點(diǎn)是高度頂點(diǎn)；(2) 兩個頂點(diǎn)都是高度頂點(diǎn)。對于第一種情況，算法利用添加頂點(diǎn)的方法把頂點(diǎn)添加到D的包中；對于第二種情況，當(dāng)兩個頂點(diǎn)都添加到D的包中時，算法驗(yàn)證主核是否存在于包中，當(dāng)兩個頂點(diǎn)添加到同一個D時，算法將新邊添加到同一個D并確保不變量保持不變。相反，當(dāng)兩個頂點(diǎn)添加到不同的D時，算法驗(yàn)證頂點(diǎn)是否存在于彼此的誘導(dǎo)子圖中，并修復(fù)兩個頂點(diǎn)的主核。算法2描述了添加邊的過程。

算法2添加邊算法

2. return;

/*只有一個頂點(diǎn)是高度頂點(diǎn)*/

4.Du←AddToBag(u);

6.Dv←AddToBag(v);

7. else

/*兩個頂點(diǎn)都是高度頂點(diǎn)*/

8.Du←AddToBag(u);

9.Dv←AddToBag(v);

10. ifDu=Dvthen

11.Du←Du∪{u,v}

3.3 移除頂點(diǎn)/邊操作

1) 移除頂點(diǎn)操作。與添加頂點(diǎn)操作類似，首先定義從D的包中移除頂點(diǎn)的過程，移除頂點(diǎn)的方法用作移除邊過程的子程序。只有當(dāng)頂點(diǎn)的度低于最大密度時才會從包中移除頂點(diǎn)，移除頂點(diǎn)不能是主核的一部分，算法從包中的D里移除頂點(diǎn)而不執(zhí)行其他操作。

2) 移除邊操作。利用包確保存在一個核數(shù)等于圖的主核的D,當(dāng)其中一個頂點(diǎn)是低度頂點(diǎn)或者兩個頂點(diǎn)屬于不同的D時，包不需要任何更新。因此考慮其中一個頂點(diǎn)位于高度頂點(diǎn)邊界的情況，移除邊將頂點(diǎn)從高度移到低度，在這種情況下，算法僅需要從包中移除頂點(diǎn)，而不執(zhí)行其他操作。如果移除邊的兩個頂點(diǎn)都是高度的并且屬于同一個D，算法從D中移除邊，此外，驗(yàn)證并更新影響的頂點(diǎn)的核數(shù)，移除邊可能會降低最大密度，因此需要向包中添加其度大于新最大密度的頂點(diǎn)。算法3描述了移除邊的過程。

算法3移除邊算法

/*其中一個頂點(diǎn)是高度頂點(diǎn)*/

2. return;

/*其中一個頂點(diǎn)位于高度頂點(diǎn)邊界*/

4. RemoveVertex(u);

5. return;

7. RemoveVertex(v);

8. return;

9. forDi∈Bdo

/*兩個頂點(diǎn)都是高度并且屬于同一個D*/

10. if (Di∩(u,v)≠?)then

11.Di←Di(u,v);

/*從Di中移除(u，v)這條邊*/

3.4 完整的時態(tài)稠密子圖發(fā)現(xiàn)算法

算法4TDSubgraph

輸出：H*。

2. Wait for update(Op,u,v),Op∈{Add,Remove};

/*選擇添加或者移除*/

3. if Op=Add then;

4. if Add=Vertex; 算法1;

5. else 算法2;

6.else 算法3;

7.returnH*;

下面給出本文算法的復(fù)雜度分析，設(shè)A為添加的邊數(shù)，即A包含初始圖的邊和添加的邊，R為移除的邊數(shù)，得到A+R=O(A)，本文將一系列操作的總開銷限制在移除邊的隨機(jī)選擇定義的概率空間中。本文算法的添加邊操作需要O(log(A)log2(n))的時間，移除邊操作需要O(log(A)log3(n))的時間，因此算法總的時間復(fù)雜度為O(Alog(A)log2(|V|)+Rlog(A)log3(|V|))，同時算法需要O(n2poly(A)logn)的空間。

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

為了評估本文算法TDSubgraph，使用社交網(wǎng)絡(luò)，檢查算法的運(yùn)行時間，分析發(fā)現(xiàn)稠密子圖的結(jié)構(gòu)特征。實(shí)驗(yàn)中使用的所有數(shù)據(jù)集都是公開可用的。

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

表1 數(shù)據(jù)集包含的信息

(1) Facebook。該數(shù)據(jù)集是新奧爾良地區(qū)社區(qū)中三個月Facebook活動的子集，包含匿名墻貼的列表，子集涵蓋2006年5月9日至2006年8月6日的時間段。

(2) Twitter。該數(shù)據(jù)集在2010年8月至2010年10月期間跟蹤赫爾辛基地區(qū)Twitter用戶的活動。由于用戶交互考慮了包含其他用戶評論的推文。

(3) Students。該數(shù)據(jù)集是加州大學(xué)歐文分校學(xué)生在線社區(qū)的活動日志。節(jié)點(diǎn)代表學(xué)生，邊代表消息。使用該數(shù)據(jù)集的一個子集，涵蓋時間范圍是2004年6月27日至2004年10月26日。

(4) Enron。該數(shù)據(jù)集包含從1980年開始超過20多年的大公司高級管理層的電子郵件通信信息。

(5) FacebookL。該數(shù)據(jù)集由Facebook數(shù)據(jù)集順序連接生成，包含1 000萬條記錄。

(6) TwitterL。該數(shù)據(jù)集由Twitter數(shù)據(jù)集連接生成，包含1 000萬條記錄。

4.2 實(shí)驗(yàn)設(shè)置

評估本文算法TDSubgraph的性能和效率，主要包括：通過算法發(fā)現(xiàn)的稠密子圖密度評估性能，運(yùn)行時間評估算法的效率。其中運(yùn)行時間是移動滑動窗口所需的平均時間，包括添加新的邊、移除舊的邊、更新稠密子圖。

本文實(shí)驗(yàn)的硬件配置是Intel(R) Core(TM) i5-4590 3.30 GHz處理器和8.00 GB內(nèi)存，所有的算法都用Java實(shí)現(xiàn)，每次運(yùn)行使用的內(nèi)存不到可用主內(nèi)存的10%。

本文考慮了兩種常用的流排序方案。

(1) BFS。排序是從隨機(jī)頂點(diǎn)開始的廣度優(yōu)先搜索的結(jié)果。

(2) DFS。排序是從隨機(jī)頂點(diǎn)開始的深度優(yōu)先搜索的結(jié)果。

4.3 最優(yōu)基線

算法的自然基線Optimal[18]結(jié)合了精確的動態(tài)編程，并為每個候選區(qū)間找到最佳稠密子圖。由于Optimal的時間復(fù)雜度很高，生成一個包含60個時間戳的小數(shù)據(jù)集，其中每個時間戳包含一個帶有3～6個頂點(diǎn)和隨機(jī)密度的隨機(jī)圖。改變區(qū)間數(shù)k的值，圖2給出算法結(jié)果和運(yùn)行時間。在這個小數(shù)據(jù)集上，本文算法能夠找到接近最佳的稠密子圖，同時明顯快于Optimal。

圖2 最優(yōu)和近似算法的比較

4.4 真實(shí)數(shù)據(jù)集上的結(jié)果

由于基線算法Optimal在真實(shí)數(shù)據(jù)集上沒有很好的可擴(kuò)展性，本文將算法TDSubgraph與基線kGoptDP[2]和kGoptDS[11]進(jìn)行比較。kGoptDP算法執(zhí)行精確的動態(tài)編程，但使用近似增量算法搜索稠密子圖；kGoptDS算法執(zhí)行近似動態(tài)編程，同時為每個候選區(qū)間計(jì)算稠密子圖。kGoptDP具有2(1+εDP)2近似保證，kGoptDS具有(1+εDS)近似保證。然而這兩個算法實(shí)際運(yùn)行也非常慢，本文使用Students和Enron數(shù)據(jù)集的1 000條記錄的子集進(jìn)行比較。

為了確保公平性，本文給出算法發(fā)現(xiàn)的區(qū)間內(nèi)最佳稠密子圖的總密度。

本文用近似稠密子圖搜索(εDP)和近似動態(tài)編程(εDS)的不同參數(shù)進(jìn)行實(shí)驗(yàn)。表2給出算法TDSubgraph、kGoptDP和kGoptDS和發(fā)現(xiàn)的稠密子圖的密度及算法的運(yùn)行時間。對于這兩個數(shù)據(jù)集，kGoptDS發(fā)現(xiàn)了最佳稠密子圖，因?yàn)樵撍惴ň哂凶罴呀埔蜃?。此外，kGoptDS算法的運(yùn)行時間最長，隨著參數(shù)εDS的增大，算法運(yùn)行時間減少，即使是最大的參數(shù)值(εDS=2)，運(yùn)行時間仍能達(dá)到一個多小時。kGoptDP算法發(fā)現(xiàn)了第二好的稠密子圖，只是略微優(yōu)于本文算法(例如εDP=0.1)，從表2看出，隨著εDP的增大，得到的稠密子圖的密度減小。對于這三個算法，隨著近似參數(shù)增大，發(fā)現(xiàn)稠密子圖的密度減小，然而密度減小并非像最壞情況表明得那樣明顯，使用這樣的近似參數(shù)加快運(yùn)行時間，TDSubgraph為近似參數(shù)提供最快的高性能估計(jì)，從表2可以看出，本文算法對參數(shù)εDP影響的稠密子圖密度的變化更敏感。

表2 TDSubgraph、kGoptDP和kGoptDS的比較結(jié)果

實(shí)驗(yàn)使用邊流的BFS和DFS兩種排序方案，評估不同方案對算法運(yùn)行時間的影響，設(shè)置滑動窗口的大小為x=100k。圖3給出算法采用不同流排序方案的運(yùn)行時間，可以看出，本文算法采用這兩種排序方案處理所有數(shù)據(jù)集時，BFS略優(yōu)于DFS，因?yàn)镈FS策略占內(nèi)存少但速度較慢，BFS策略占內(nèi)存多但速度較快，整體比較運(yùn)行時間仍然都優(yōu)于其他兩個算法。

圖3 不同流排序方案對算法的影響

4.5 運(yùn)行時間與可擴(kuò)展性

圖4給出近似參數(shù)εDS和εDP的改變對TDSubgraph運(yùn)行時間的影響。圖中結(jié)果表明參數(shù)εDP對運(yùn)行時間有重大影響，同時參數(shù)εDS在這兩個數(shù)據(jù)集上有很好的擴(kuò)展性。

圖4 不同近似參數(shù)對算法的影響

實(shí)驗(yàn)還使用不同大小的滑動時間窗執(zhí)行算法，即x=10k,100k,1M,10M，實(shí)驗(yàn)中設(shè)置k=10，評估滑動時間窗大小對算法的影響，使用具有DFS排序的FacebookL和TwitterL數(shù)據(jù)集。表3給出不同大小滑動時間窗的運(yùn)行時間。增大滑動時間窗不會顯著地影響算法運(yùn)行時間，這一結(jié)果表明大多數(shù)的更新都是子圖局部更新，并不需要遍歷整個圖。

表3 不同大小的滑動時間窗對算法運(yùn)行時間的影響 ms

圖5是在Facebook和Twitter數(shù)據(jù)集中增加交互次數(shù)，運(yùn)行時間的變化顯示出算法的可擴(kuò)展性。實(shí)際上，運(yùn)行時間在前1 000次交互中快速增長，然后飽和到線性依賴，因?yàn)榫W(wǎng)絡(luò)初期頂點(diǎn)數(shù)量增長比較快，而且可能出現(xiàn)比之前更稠密的子圖，必須頻繁計(jì)算近似稠密子圖。圖5表明區(qū)間k的數(shù)量對算法的運(yùn)行時間也有影響，隨著k的增加運(yùn)行時間增加。

圖5 算法的可擴(kuò)展性

5 結(jié) 語

本文研究了在時態(tài)網(wǎng)絡(luò)中基于滑動時間窗找到一系列稠密子圖的問題，并提出一種有效的動態(tài)算法。現(xiàn)有算法在圖更新時迭代整個圖，本文算法僅影響圖的有限區(qū)域，因此只需要局部更新稠密子圖。結(jié)合滑動時間窗將網(wǎng)絡(luò)時間線分割為k個非重疊間隔，使得間隔內(nèi)能夠發(fā)現(xiàn)具有最大密度的子圖。結(jié)合理論分析，并驗(yàn)證該算法比文獻(xiàn)[3]的算法更快。真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證本文算法是有效的，且可以得到高質(zhì)量的結(jié)果。

今后的研究中，將考慮子圖的頻率、子圖的統(tǒng)計(jì)非隨機(jī)性對網(wǎng)絡(luò)進(jìn)行分割，另一種擴(kuò)展是每個間隔內(nèi)發(fā)現(xiàn)多個稠密子圖可能是更有意義的。還可以考慮是否有可能在高度頂點(diǎn)的閾值上實(shí)現(xiàn)更強(qiáng)的界限，是否有可能為問題實(shí)現(xiàn)更好的近似保證，進(jìn)一步改進(jìn)算法，使其成為許多實(shí)際應(yīng)用的有用工具。