蔣志恒

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

0 引言

圖挖掘一直是一個(gè)備受關(guān)注的問(wèn)題。幾乎所有的復(fù)雜系統(tǒng)都可以建模成動(dò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ù)的量級(jí)隨著時(shí)間不斷增加。有效的圖挖掘算法對(duì)于增加我們對(duì)這些大型圖數(shù)據(jù)集所代表的信息的理解至關(guān)重要。圖挖掘的核心問(wèn)題是在這些圖結(jié)構(gòu)的數(shù)據(jù)集中發(fā)現(xiàn)頻繁子圖。但目前大量工作的焦點(diǎn)集中于如何在靜態(tài)圖中挖掘出頻繁子圖，而對(duì)具有時(shí)間維度的動(dòng)態(tài)網(wǎng)絡(luò)中的頻繁模式挖掘的研究較少。

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

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

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

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

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

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

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

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

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

（1）存在一個(gè)圖序列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ù)大于一個(gè)給定的支持度閾值σ，即Support（S）≥σ。

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

1.2 頻繁演化模式的CSP模型

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

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

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

（2）D對(duì)是所有xv∈X的域的集合。每個(gè)域是的子集。

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

①對(duì)所有xv,xv'∈X，xv=xv'

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

③對(duì)所有xv,xv'∈X ，且

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

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

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

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

算法：FSGSequenceMining

輸入：一個(gè)圖序列G1T，最小支持度閾值σ，以及子圖序列時(shí)間步長(zhǎng)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

輸入：一個(gè)初始子圖序列S1k，一個(gè)圖序列G1T，最小支持度閾值σ，子圖序列時(shí)間步長(zhǎng)k，以及頻繁邊集fEdges

輸出：所有的基于S1k擴(kuò)展而來(lái)的頻繁子圖序列

1 result←S1k，candidateSet←?

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

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

4 ext=S1kextend e

5 i（f ext之前沒(méi)有被生成）：

6 candidateSet←candidateSet∪ext

7 foreach c∈candidateSet：

8 求c對(duì)G1T的約束滿足問(wèn)題的解Solution

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

10 result←result∪SGSequenceExtension

(c，G1T，σ，k，fEdges）

11 return result

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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