基于滑動時間窗的稠密子圖發現算法研究

田朝霞 張 俊 陳 旭 曲賢菲

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

0 引 言

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

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

在現實應用中，圖數據會隨時間發生動態變化，也就是所謂的時態圖，時態圖有兩種變化形式：一種是圖的拓撲結構變化，圖中的節點和邊隨時間發生插入和刪除，從而導致圖的結構發生變化；另一種是圖的內容變化，圖中的節點和邊所表征的數據值或者對象內容發生變化。本文更多關注時態圖的拓撲結構變化對稠密子圖發現結果的影響。當處理時態網絡時，首先要確定如何處理時間維度，即識別哪段時間是可以發現稠密子圖的時間間隔。本文算法不是先驗地定義這些間隔，而是研究自動識別稠密子圖的間隔的問題，因此能夠在時態網絡中發現一系列稠密子圖，捕獲網絡生命周期中發生的有趣事件的演變。

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

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

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

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

對于時態網絡，只有很少的論文提出了發現時間上連續的最稠密子圖的方法。與本文工作最相似的是找到所有或k個快照中存在的重子圖[8]，另一個相關工作側重在時態網絡中找到由k個散亂區間覆蓋的稠密子圖[9]。然而這兩種方法都只發現了一個最稠密子圖。

本文的目標是研究在滑動時間窗中發現稠密子圖的問題，為了實現這一目標，采用動態稠密子圖的現有工作設計一個快速的近似算法，結合滑動時間窗將時態網絡劃分成k個非重疊的間隔，使得間隔內能夠發現最大稠密子圖。

本文的主要思路如下：

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

(2) 結合時間窗大小將時態網絡的時間線分割成k個非重疊間隔，每個間隔內能夠發現具有最大密度的子圖。

(3) 在真實數據集上進行實驗，驗證了本文方法的有效性，并解釋結果的合理性。

1 相關工作

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

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

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

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

總之，與已有研究相比，本文希望能夠在時態網絡中發現一系列稠密子圖，捕獲網絡生命周期中發生的有趣事件的演變。

2 時態稠密子圖問題定義

(1)

(2)

下面介紹與稠密子圖相關的其他概念：圖核、核心分解和頂點的誘導核心子圖。

V=C0?C1?…?Cl??

(3)

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

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

換言之，誘導子圖包含可從v到達并具有相同核數κ(v)的所有頂點。

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

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

(4)

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

下面定義本文研究的問題，即以滑動時間窗進行分割，在時態網絡中找到一系列稠密子圖。

3 時態稠密子圖發現算法

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

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

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

3.1 存儲高度頂點的數據結構

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

圖1 存儲高度頂點的數據結構圖

3.2 添加頂點/邊操作

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

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

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

算法1添加頂點算法

1.H*←?;

2. forDi∈Bdo

/*識別候選D*/

3. ifu∈Dithen

/*找到包含頂點的D*/

4. returnDi;

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

6.H*←Di;

/*候選D具有小于或等于新頂點內度的主核數*/

7. ifH*=? then

8.H*←{u};

9. elseH*←H*∪{u}

10. returnH*;

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

算法2添加邊算法

2. return;

/*只有一個頂點是高度頂點*/

4.Du←AddToBag(u);

6.Dv←AddToBag(v);

7. else

/*兩個頂點都是高度頂點*/

8.Du←AddToBag(u);

9.Dv←AddToBag(v);

10. ifDu=Dvthen

11.Du←Du∪{u,v}

3.3 移除頂點/邊操作

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

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

算法3移除邊算法

/*其中一個頂點是高度頂點*/

2. return;

/*其中一個頂點位于高度頂點邊界*/

4. RemoveVertex(u);

5. return;

7. RemoveVertex(v);

8. return;

9. forDi∈Bdo

/*兩個頂點都是高度并且屬于同一個D*/

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

11.Di←Di(u,v);

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

3.4 完整的時態稠密子圖發現算法

算法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*;

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

4 實驗與結果分析

為了評估本文算法TDSubgraph，使用社交網絡，檢查算法的運行時間，分析發現稠密子圖的結構特征。實驗中使用的所有數據集都是公開可用的。

4.1 數據集

表1 數據集包含的信息

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

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

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

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

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

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

4.2 實驗設置

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

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

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

(1) BFS。排序是從隨機頂點開始的廣度優先搜索的結果。

(2) DFS。排序是從隨機頂點開始的深度優先搜索的結果。

4.3 最優基線

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

圖2 最優和近似算法的比較

4.4 真實數據集上的結果

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

為了確保公平性，本文給出算法發現的區間內最佳稠密子圖的總密度。

本文用近似稠密子圖搜索(εDP)和近似動態編程(εDS)的不同參數進行實驗。表2給出算法TDSubgraph、kGoptDP和kGoptDS和發現的稠密子圖的密度及算法的運行時間。對于這兩個數據集，kGoptDS發現了最佳稠密子圖，因為該算法具有最佳近似因子。此外，kGoptDS算法的運行時間最長，隨著參數εDS的增大，算法運行時間減少，即使是最大的參數值(εDS=2)，運行時間仍能達到一個多小時。kGoptDP算法發現了第二好的稠密子圖，只是略微優于本文算法(例如εDP=0.1)，從表2看出，隨著εDP的增大，得到的稠密子圖的密度減小。對于這三個算法，隨著近似參數增大，發現稠密子圖的密度減小，然而密度減小并非像最壞情況表明得那樣明顯，使用這樣的近似參數加快運行時間，TDSubgraph為近似參數提供最快的高性能估計，從表2可以看出，本文算法對參數εDP影響的稠密子圖密度的變化更敏感。

表2 TDSubgraph、kGoptDP和kGoptDS的比較結果

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

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

4.5 運行時間與可擴展性

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

圖4 不同近似參數對算法的影響

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

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

圖5是在Facebook和Twitter數據集中增加交互次數，運行時間的變化顯示出算法的可擴展性。實際上，運行時間在前1 000次交互中快速增長，然后飽和到線性依賴，因為網絡初期頂點數量增長比較快，而且可能出現比之前更稠密的子圖，必須頻繁計算近似稠密子圖。圖5表明區間k的數量對算法的運行時間也有影響，隨著k的增加運行時間增加。

圖5 算法的可擴展性

5 結 語

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

今后的研究中，將考慮子圖的頻率、子圖的統計非隨機性對網絡進行分割，另一種擴展是每個間隔內發現多個稠密子圖可能是更有意義的。還可以考慮是否有可能在高度頂點的閾值上實現更強的界限，是否有可能為問題實現更好的近似保證，進一步改進算法，使其成為許多實際應用的有用工具。