時序網絡的頻繁演化模式挖掘

蔣志恒

（四川大學計算機學院，成都 610065）

0 引言

圖挖掘一直是一個備受關注的問題。幾乎所有的復雜系統都可以建模成動態網絡，如社交網絡、合作者網絡、生物信息網絡等，這是一種合理有效的方式。目前，在各種應用領域諸如生物信息學和醫學到大型數據管理中，圖結構數據的量級隨著時間不斷增加。有效的圖挖掘算法對于增加我們對這些大型圖數據集所代表的信息的理解至關重要。圖挖掘的核心問題是在這些圖結構的數據集中發現頻繁子圖。但目前大量工作的焦點集中于如何在靜態圖中挖掘出頻繁子圖，而對具有時間維度的動態網絡中的頻繁模式挖掘的研究較少。

信息網絡通常隨著時間進行演化，在此時，我們稱它為動態信息網絡。在一個信息網絡中，一個新連接的形成、現存連接的消失或者連接屬性的改變這些現象廣泛存在。簡單地說，對應到一個社會網絡，這些現象表現為個體之間關系的建立或者解除（朋友、親人等），或者從一種關系轉變為另一種關系（朋友-＞親人）。特別地，這些關系的建立是基于現存的關系之上，而這些關系屬性的變化也是受到周圍關系的影響。因此，我們不能僅僅通過考慮單個結點的變化來捕捉這樣一個復雜的過程，而是應該從更大的尺度來分析這些變化。

圖1 動態圖的演化模式

在本文中，我們關注的就是子圖是如何隨著時間演化的，這種演化模式隨著時間推移不斷重復出現。研究這些變化對于很多場景都非常有意義，例如對社交網絡趨勢的分析、動態鏈接預測以及商品推薦。在社會網絡演化的場景里，這些變化揭示了主導網絡中個體信任傳播、觀點動態變化的復雜過程。如圖1所示的一個演化模式示例，這個示例可以看作是一個信任傳播過程，顧客C開始并不喜歡某個餐廳，在顧客A和顧客B先后喜歡此餐廳后，顧客C也喜歡上了餐廳，如果這種模式頻繁出現，那么很顯然顧客C是受到了顧客A和B的影響。

然而，現存大量研究集中于靜態圖的頻繁模式的挖掘[1-3]，或者僅僅是將靜態圖中頻繁模式挖掘的方式簡單遷移于動態網絡研究中[4-5]，并沒有充分考慮到時間維度的增加為這一問題帶來復雜性，無法高效地挖掘動態網絡中的頻繁演化模式。本文針對此問題，提出一種基于約束滿足問題的多跨度頻繁演化模式挖掘算法，有效地降低了算法復雜度，為頻繁演化模式挖掘提供一個一般性的方法。

1 基于CSP的頻繁演化模式挖掘

1.1 動態圖的定義

動態圖：一個圖可以表示為一個元組G=(V,E,l)，其中V為一個有限的節點集，E為一個有限的邊集：E?V×V?{(u ,u)|u∈V}，以及邊和節點標簽映射 l：V∪E→label。形式地，一個動態網絡是一個圖的序列。并且，我們假設節點集是靜態的，也就是說，對t=1,…,T，Gt=(V,Et,lt)。圖Gt被稱為動態圖的快照。如圖2所示。

圖2 一個動態網絡

動態網絡中頻繁演化模式：指不斷在大圖序列中重復出現的子圖序列。這里所說的“出現（Occurrence）”不僅包括廣度上的子圖序列的存在性（即圖中多個同構的子圖存在相同演化模式），還包括時間維度上隨著圖的演替，這些子圖序列在未來不斷重復交疊出現。給定一個長度為T大圖序列G1T=（G1,G2···,GT），其中T＞1，我們的目的是挖掘長度為k的子圖序列，其中 k＞1，且子圖序列滿足以下約束：

（1）存在一個圖序列g=(g1,g2,…,gk),?1≤i≤k,gi是 Gj+i的子圖，其中 0≤j≤T-k+1，Siisomorphism with gi，那么我們就稱S1k在G1T中出現了一次。

（2）圖序列在G1T中出現的次數大于一個給定的支持度閾值σ，即Support（S）≥σ。

這樣的子序列我們稱之為頻繁子圖序列。

1.2 頻繁演化模式的CSP模型

在計算一個子圖序列的頻繁度時，我們常常需要計算出一個子圖序列精確的頻繁度。然而，在很多場景這并不是必要的，因為我們只需要知道哪些子圖序列是頻繁的，而不是準確知道。在這里，我們采用一種新型的挖掘頻繁子圖序列的方法，將判斷一個子圖序列是否頻繁規約成一個約束滿足問題（CSP），再對這個CSP進行求解。

約束滿足問題（CSP）可以表示為一個元組(X,D,C)，在這里，X是一個變量的有續集，D是一組對應變量集中變量的域，C則是變量集X中變量之間的約束，C中所有的約束都要被滿足。

（1）對每個節點v∈Vsk，集合X包含一個變量xv。

（2）D對是所有xv∈X的域的集合。每個域是的子集。

（3）集合C包含下列約束：

①對所有xv,xv'∈X，xv=xv'

②對每個變量xv∈X，l(xv)=ls(v)

③對所有xv,xv'∈X ，且

為了更清楚地說明上述標記，我們在這里用v表示子圖序列中的一個節點，xv是其在CSP中對應的一個變量，這個變量的值域是大圖序列中的節點。一個子圖序列S1k對大圖序列G1T的約束滿足問題的解對應于一個子圖序列S1k對大圖序列G1T同構。直覺地，一個CSP的解會分配G1T中不同的節點給S1k中每個節點對應的變量，并且它們對應的節點和邊的標簽相匹配。一個分配有效當且僅當存在一個CSP的解對應于這個取值。

如果(X,D,C)是子圖序列S1k對大圖序列G1T的一個CSP，如果S1k的頻繁次數滿足最小支持度σ，也就是說Support(S1k)≥σ，當且僅當對X中的每個變量都至少有σ個有效的取值。如果每個變量都存在至少σ有效的取值，那么Support(S1k)≥σ，也就是說S1k是頻繁的。

1.3 基于CSP的頻繁演化模式挖掘

我們現在將1.2小節所述的CSP模型應用于解決頻繁演化模式挖掘問題。時序網絡中演化模式挖掘需要挖掘所有滿足最小支持度的子圖序列。因此，除了要判斷一個圖序列是否頻繁，還要生成所有的子圖序列。在這里我們采用模式增長的方法，從更小的子圖通過擴展的方式得到更大的子圖。

算法：FSGSequenceMining

輸入：一個圖序列G1T，最小支持度閾值σ，以及子圖序列時間步長k

輸出：所有Support(S1k)≥σ的子圖序列

1 result←?

2 fEdges表示G1T中所有的頻繁的邊集

3 foreach e∈fEages：

4 result←result∪SGSequenceExtension(e,G1T,σ,k,

fEdges)

5 從fEdges中移除e

6 return result

算法：SGSequenceExtension

輸入：一個初始子圖序列S1k，一個圖序列G1T，最小支持度閾值σ，子圖序列時間步長k，以及頻繁邊集fEdges

輸出：所有的基于S1k擴展而來的頻繁子圖序列

1 result←S1k，candidateSet←?

2 foreach e∈fEdges and節點u∈Vs1k：

3 i（f邊e可以通過節點u擴展）：

4 ext=S1kextend e

5 i（f ext之前沒有被生成）：

6 candidateSet←candidateSet∪ext

7 foreach c∈candidateSet：

8 求c對G1T的約束滿足問題的解Solution

9 i（f所有變量都有至少σ個有效取值）：

10 result←result∪SGSequenceExtension

(c，G1T，σ，k，fEdges）

11 return result

如上所示，我們提供了兩個算法FSGSequenceMining和SGSequenceExtension來共同實現本文算法。第一個FSGSequenceMining算法結構比較簡單，提供了一個總體的挖掘算法。本文核心算法的核心由第二個算法實現。在FSGSequenceMining中，首先用頻繁邊集擴展初始子圖序列，然后把擴展的子圖序列應用約束滿足問題的求解，判斷這個子圖序列是否頻繁，然后遞歸調用這個算法得到所有基于初始子圖S1k擴展而來的頻繁子圖序列。因為我們采用的是MNI的支持度計算方法，這使得一個圖序列和其子圖序列的支持度能夠保持反單調性，即一個圖序列是頻繁，那么其所有的子圖序列也必定是頻繁的，這是本文將小的頻繁子圖序列擴展成更大的頻繁子圖序列的核心思想。

2 實驗

我們使用了DBLP數據集驗證了我們模型的性能，以挖掘出的子圖序列數量和時間消耗作為評估指標。實驗結果如圖3-5。

圖3 k=2時的子圖序列數量（a）與運行時間（b）

圖4 k=3時的子圖序列數量與運行時間

圖5 k=4時的子圖序列數量與運行時間

圖3顯示子圖序列時間步長k=2時的算法得到的子圖序列數量和算法消耗時間都隨著設置的最小支持度閾值變小。這是因為隨著最小支持度閾值減少，產生大量潛在的候選子圖序列，需要額外篩選這些可能頻繁但實際卻不頻繁的子圖序列。圖4顯示的是時間步長k=3時算法得到子圖序列和算法消耗時間，同樣也隨著最小支持度閾值變小而減少。類似的，圖5顯示了k=4情況下的子圖數量與時間消耗。

3 結語

很多重要的應用都要基于圖挖掘，從生物信息學到社交網絡的研究，從個性化廣告（例如推薦系統）安全。本文介紹了一個關于大型時序網絡中演化模式挖掘的算法，大型時序網絡演化模式挖掘相比于傳統的大圖中頻繁子圖挖掘是一個更復雜的問題，它增加了一個時間維度，復雜度也增加了一個層次。我們將頻繁演化模式建模成一個約束滿足問題（CSP），減少了時序網絡中演化模式挖掘問題的復雜度，為頻繁演化模式挖掘提供一個一般性的方法。