基于滑動(dòng)時(shí)間窗的稠密子圖發(fā)現(xiàn)算法研究

田朝霞 張 俊 陳 旭 曲賢菲

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

0 引 言

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

稠密子圖發(fā)現(xiàn)是一個(gè)基本的圖挖掘問題，已經(jīng)成為廣泛的數(shù)據(jù)分析任務(wù)中的原語，如社區(qū)檢測(cè)[4]、事件檢測(cè)[5]、鏈接垃圾郵件檢測(cè)[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ò)中緊密連接的用戶可能對(duì)應(yīng)于社區(qū)，也就是有相似興趣或與同一組織(例如大學(xué)或公司)相關(guān)聯(lián)的用戶組。突然在推文中共同出現(xiàn)的城市、個(gè)人和公司名稱等實(shí)體可能表明涉及相應(yīng)實(shí)體的事件正在發(fā)生[2]。

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

為了得到更具體的理解，請(qǐng)考慮以下幾種場(chǎng)景的事例：

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

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

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

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

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

本文的主要思路如下：

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

(1)

(2)

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

V=C0?C1?…?Cl??

(3)

其中每個(gè)Ci都是一個(gè)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)。

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

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

(4)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.H*←?;

2. forDi∈Bdo

/*識(shí)別候選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)添加邊的至少一個(gè)頂點(diǎn)是高度頂點(diǎn)時(shí)，才會(huì)影響包的狀態(tài)， 需要考慮兩種情況：(1) 只有一個(gè)頂點(diǎn)是高度頂點(diǎn)；(2) 兩個(gè)頂點(diǎn)都是高度頂點(diǎn)。對(duì)于第一種情況，算法利用添加頂點(diǎn)的方法把頂點(diǎn)添加到D的包中；對(duì)于第二種情況，當(dāng)兩個(gè)頂點(diǎn)都添加到D的包中時(shí)，算法驗(yàn)證主核是否存在于包中，當(dāng)兩個(gè)頂點(diǎn)添加到同一個(gè)D時(shí)，算法將新邊添加到同一個(gè)D并確保不變量保持不變。相反，當(dāng)兩個(gè)頂點(diǎn)添加到不同的D時(shí)，算法驗(yàn)證頂點(diǎn)是否存在于彼此的誘導(dǎo)子圖中，并修復(fù)兩個(gè)頂點(diǎn)的主核。算法2描述了添加邊的過程。

算法2添加邊算法

2. return;

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

4.Du←AddToBag(u);

6.Dv←AddToBag(v);

7. else

/*兩個(gè)頂點(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)的度低于最大密度時(shí)才會(huì)從包中移除頂點(diǎn)，移除頂點(diǎn)不能是主核的一部分，算法從包中的D里移除頂點(diǎn)而不執(zhí)行其他操作。

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

算法3移除邊算法

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

2. return;

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

4. RemoveVertex(u);

5. return;

7. RemoveVertex(v);

8. return;

9. forDi∈Bdo

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

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

11.Di←Di(u,v);

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

3.4 完整的時(shí)態(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))的時(shí)間，移除邊操作需要O(log(A)log3(n))的時(shí)間，因此算法總的時(shí)間復(fù)雜度為O(Alog(A)log2(|V|)+Rlog(A)log3(|V|))，同時(shí)算法需要O(n2poly(A)logn)的空間。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 不同流排序方案對(duì)算法的影響

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

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

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

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

表3 不同大小的滑動(dòng)時(shí)間窗對(duì)算法運(yùn)行時(shí)間的影響 ms

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

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

5 結(jié) 語

本文研究了在時(shí)態(tài)網(wǎng)絡(luò)中基于滑動(dòng)時(shí)間窗找到一系列稠密子圖的問題，并提出一種有效的動(dòng)態(tài)算法?，F(xiàn)有算法在圖更新時(shí)迭代整個(gè)圖，本文算法僅影響圖的有限區(qū)域，因此只需要局部更新稠密子圖。結(jié)合滑動(dòng)時(shí)間窗將網(wǎng)絡(luò)時(shí)間線分割為k個(gè)非重疊間隔，使得間隔內(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ī)性對(duì)網(wǎng)絡(luò)進(jìn)行分割，另一種擴(kuò)展是每個(gè)間隔內(nèi)發(fā)現(xiàn)多個(gè)稠密子圖可能是更有意義的。還可以考慮是否有可能在高度頂點(diǎn)的閾值上實(shí)現(xiàn)更強(qiáng)的界限，是否有可能為問題實(shí)現(xiàn)更好的近似保證，進(jìn)一步改進(jìn)算法，使其成為許多實(shí)際應(yīng)用的有用工具。