蔣志恒

（四川大學(xué)計算機(jī)學(xué)院，成都 610065）

0 引言

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

信息網(wǎng)絡(luò)通常隨著時間進(jìn)行演化，在此時，我們稱它為動態(tài)信息網(wǎng)絡(luò)。在一個信息網(wǎng)絡(luò)中，一個新連接的形成、現(xiàn)存連接的消失或者連接屬性的改變這些現(xiàn)象廣泛存在。簡單地說，對應(yīng)到一個社會網(wǎng)絡(luò)，這些現(xiàn)象表現(xiàn)為個體之間關(guān)系的建立或者解除（朋友、親人等），或者從一種關(guān)系轉(zhuǎn)變?yōu)榱硪环N關(guān)系（朋友-＞親人）。特別地，這些關(guān)系的建立是基于現(xiàn)存的關(guān)系之上，而這些關(guān)系屬性的變化也是受到周圍關(guān)系的影響。因此，我們不能僅僅通過考慮單個結(jié)點(diǎn)的變化來捕捉這樣一個復(fù)雜的過程，而是應(yīng)該從更大的尺度來分析這些變化。

圖1 動態(tài)圖的演化模式

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

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

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

1.1 動態(tài)圖的定義

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

圖2 一個動態(tài)網(wǎng)絡(luò)

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

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

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

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

1.2 頻繁演化模式的CSP模型

在計算一個子圖序列的頻繁度時，我們常常需要計算出一個子圖序列精確的頻繁度。然而，在很多場景這并不是必要的，因?yàn)槲覀冎恍枰滥男┳訄D序列是頻繁的，而不是準(zhǔn)確知道。在這里，我們采用一種新型的挖掘頻繁子圖序列的方法，將判斷一個子圖序列是否頻繁規(guī)約成一個約束滿足問題（CSP），再對這個CSP進(jìn)行求解。

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

（1）對每個節(jié)點(diǎn)v∈Vsk，集合X包含一個變量xv。

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

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

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

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

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

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

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

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

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

算法：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擴(kuò)展而來的頻繁子圖序列

1 result←S1k，candidateSet←?

2 foreach e∈fEdges and節(jié)點(diǎn)u∈Vs1k：

3 i（f邊e可以通過節(jié)點(diǎn)u擴(kuò)展）：

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來共同實(shí)現(xiàn)本文算法。第一個FSGSequenceMining算法結(jié)構(gòu)比較簡單，提供了一個總體的挖掘算法。本文核心算法的核心由第二個算法實(shí)現(xiàn)。在FSGSequenceMining中，首先用頻繁邊集擴(kuò)展初始子圖序列，然后把擴(kuò)展的子圖序列應(yīng)用約束滿足問題的求解，判斷這個子圖序列是否頻繁，然后遞歸調(diào)用這個算法得到所有基于初始子圖S1k擴(kuò)展而來的頻繁子圖序列。因?yàn)槲覀儾捎玫氖荕NI的支持度計算方法，這使得一個圖序列和其子圖序列的支持度能夠保持反單調(diào)性，即一個圖序列是頻繁，那么其所有的子圖序列也必定是頻繁的，這是本文將小的頻繁子圖序列擴(kuò)展成更大的頻繁子圖序列的核心思想。

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

我們使用了DBLP數(shù)據(jù)集驗(yàn)證了我們模型的性能，以挖掘出的子圖序列數(shù)量和時間消耗作為評估指標(biāo)。實(shí)驗(yàn)結(jié)果如圖3-5。

圖3 k=2時的子圖序列數(shù)量（a）與運(yùn)行時間（b）

圖4 k=3時的子圖序列數(shù)量與運(yùn)行時間

圖5 k=4時的子圖序列數(shù)量與運(yùn)行時間

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

3 結(jié)語

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