基于加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)的頻繁模式挖掘研究＊

肖港松，陳曉云

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108)

近年來，針對(duì)社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等的挖掘研究越來越多(如社區(qū)識(shí)別、社區(qū)關(guān)系發(fā)現(xiàn)等)[1]，尤其是針對(duì)犯罪團(tuán)伙和恐怖分子活動(dòng)網(wǎng)絡(luò)的研究，引起了世界各國的重視[2]。實(shí)際中，網(wǎng)絡(luò)往往隨時(shí)間而變動(dòng)，即網(wǎng)絡(luò)是動(dòng)態(tài)網(wǎng)絡(luò)[3]。挖掘動(dòng)態(tài)網(wǎng)絡(luò)中的頻繁模式，即可以發(fā)現(xiàn)變化網(wǎng)絡(luò)中具有相對(duì)“穩(wěn)定性”的頻繁模式，這些模式在動(dòng)態(tài)網(wǎng)絡(luò)中往往也是比較有趣和重要的，這對(duì)研究動(dòng)態(tài)網(wǎng)絡(luò)很有意義。由于圖具有結(jié)構(gòu)關(guān)系，可用來表示事物之間復(fù)雜的相互作用關(guān)系，是基本的數(shù)據(jù)結(jié)構(gòu)，因此網(wǎng)絡(luò)可用圖來表示，即一個(gè)網(wǎng)絡(luò)可抽象成一個(gè)圖，對(duì)網(wǎng)絡(luò)的挖掘研究也就轉(zhuǎn)化為對(duì)圖的挖掘研究。

在實(shí)際中，一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)在某個(gè)時(shí)刻表現(xiàn)出來的整體重要性可能并不一樣，這就需要考慮各個(gè)時(shí)刻網(wǎng)絡(luò)的不同權(quán)重，即考慮加權(quán)的動(dòng)態(tài)網(wǎng)絡(luò)。而挖掘加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)的頻繁模式，即是挖掘加權(quán)圖集的頻繁子圖。

對(duì)圖加權(quán)主要包括頂點(diǎn)、邊和整個(gè)圖的加權(quán)。當(dāng)前，已經(jīng)提出一些關(guān)于加權(quán)圖集的頻繁子圖挖掘算法[4-7]，如參考文獻(xiàn)[4]、[6]提出的是基于頂點(diǎn)加權(quán)的頻繁子圖挖掘，而參考文獻(xiàn)[5]、[7]則是基于邊加權(quán)的頻繁子圖挖掘。

網(wǎng)絡(luò)在某個(gè)時(shí)刻的重要性可以對(duì)整個(gè)圖賦予不同權(quán)重來表示，無需考慮網(wǎng)絡(luò)內(nèi)部頂點(diǎn)和邊的權(quán)重，有時(shí)也很難知道頂點(diǎn)和邊的權(quán)重，針對(duì)這種整個(gè)圖加權(quán)的挖掘，關(guān)于頂點(diǎn)或邊加權(quán)的挖掘算法均不適用于這種挖掘。為此本文提出一種適用于整個(gè)圖加權(quán)的頻繁模式挖掘算法(簡稱 WGDM)。

1相關(guān)概念和定義

一些圖挖掘和動(dòng)態(tài)網(wǎng)絡(luò)的基本概念和定義[3-5]：

定義1(標(biāo)記圖) 一個(gè)標(biāo)記圖可表示為一個(gè)四元組G=(V，E，S，L)， 其中，V 是頂點(diǎn)集合，E?V×V 是邊集合，S則是標(biāo)記集合，L：V∪E→S是一個(gè)函數(shù)，用來分配頂點(diǎn)和邊的標(biāo)記。

定義 2(子圖同構(gòu)) 給定兩個(gè)圖 G=(V，E，S，L)和圖G′=(V′，E′，S′，L′)， 這兩個(gè)圖的子圖同構(gòu)即是一個(gè)單射函數(shù) f：V→V′，函數(shù) 滿足 ：(1)?ν∈V，L(ν)=L′(f(ν))；(2)?(u，ν)∈E；(f(u)，(f(ν))∈E′且 L((u，ν))=L′(f(u)，(f(ν))，也稱此單射函數(shù)f為G在G′中的一個(gè)嵌入。如果存在從 G～G′的子圖同構(gòu)， 則稱 G為 G′的子圖，G′為 G的超圖，記為 G?G′。

定義3(動(dòng)態(tài)網(wǎng)絡(luò)) 在用圖 G=(V，E)表示的網(wǎng)絡(luò)中，頂點(diǎn)集V和邊集E隨時(shí)間變化而變化的網(wǎng)絡(luò)稱為動(dòng)態(tài)網(wǎng)絡(luò)。

下面給出本文對(duì)加權(quán)圖集、加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)、加權(quán)圖集中子圖的支持度和頻繁子圖的定義。

定義 4(加權(quán)圖集) 給定一個(gè)圖的集合 D={G1，G2，……，Gn}， 對(duì) D中的圖 G1，G2， ……，Gn分別賦予權(quán)重w1，w2，……，wn(權(quán)重為非負(fù)實(shí)數(shù))，則稱 D 為加權(quán)圖集。

定義5(加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)) 加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)即是對(duì)不同時(shí)刻的網(wǎng)絡(luò)賦予權(quán)重的動(dòng)態(tài)網(wǎng)絡(luò)，權(quán)重為一非負(fù)實(shí)數(shù)，由該時(shí)刻網(wǎng)絡(luò)的重要性來決定權(quán)重大小。

定義 6(支持度) 給定加權(quán)圖集 D={G1，G2， ……，Gn}和圖模式 g，如果圖集 D中包含圖 g的圖為 Gi1，Gi2，……，Gin，各圖對(duì)應(yīng)的權(quán)重分別為 wi1，wi2，……，wik，則圖g的絕對(duì)支持度為：

定義 7(頻繁子圖) 給定加權(quán)圖集 D={G1，G2，……，Gn}和一個(gè)實(shí)數(shù)閾值min_sup，如果子圖g在加權(quán)圖集D中的支持度sup(g，D)≥min_sup，則稱該子圖g為頻繁子圖。

2挖掘加權(quán)圖集中的頻繁子圖

2.1頻繁子圖挖掘

(1)頻繁子圖挖掘的難點(diǎn)之一在于會(huì)產(chǎn)生數(shù)量龐大的候選子圖，使得搜索空間巨大。本文提出的 WGDM算法具有如下性質(zhì)，從而可利用該性質(zhì)來裁剪搜索空間。

性質(zhì)：給定加權(quán)圖集 D={G1，G2，……，Gn}，則一個(gè)圖模式g的支持度是它所有超圖支持度的上界。

由WGDM的性質(zhì)可得，如果圖g是非頻繁子圖，則其所有的超圖也不是頻繁子圖，即可裁減掉圖g的所有超圖，如圖1所示。

圖1 剪枝

子圖 g 可擴(kuò)展的超圖包括 g～e1、g～e2、g～e3。 首先計(jì)算子圖g的支持度support(g)，若小于最小支持度，則剪掉g的所有超圖。

(2)頻繁子圖挖掘的另外一個(gè)難點(diǎn)在于子圖同構(gòu)檢測[8-9]。參考文獻(xiàn)[9]提出的GASTON算法利用一種內(nèi)嵌列表(Embedding List)記錄了頂點(diǎn)和邊在圖集中的具體位置，在子圖擴(kuò)展時(shí)可以快速地從內(nèi)嵌列表中找出可擴(kuò)展的頂點(diǎn)和邊以及進(jìn)行同構(gòu)檢測，較好地解決了子圖同構(gòu)檢測問題；而且該算法將一個(gè)復(fù)雜的圖挖掘問題分割成三個(gè)比較簡單的子問題，即先列舉出路徑(Path)、再列舉由路徑擴(kuò)展出的樹 (Non-cyclic Tree)、最后列舉由路徑或樹擴(kuò)展后的具有循環(huán)的圖(Cyclic Graph)。

GASTON算法雖然不能挖掘加權(quán)圖集的頻繁子圖，不過其同構(gòu)檢測的方法與分解成三個(gè)子問題的策略很有意義。本文采用其策略方法來進(jìn)行同構(gòu)檢測，并將加權(quán)圖集挖掘也轉(zhuǎn)為挖掘路徑、樹和循環(huán)圖的三個(gè)步驟。

2.2算法描述

首先計(jì)算WGDM算法加權(quán)圖集中子圖的支持度，其計(jì)算步驟如下：

算法1 計(jì)算子圖支持度sup(g，D)

輸入：加權(quán)圖集D，子圖 g，內(nèi)嵌列表。

輸出：子圖 g的支持度 sup(g，D)。

(1)初始化 sup(g，D)=0；

(2)利用內(nèi)嵌列表(Embedding List)找出 D中包含子圖 g 的所有圖 Gi1，Gi2，……，Gik。

(3) 找出 Gi1，Gi2， ……，Gik各圖對(duì)應(yīng)的權(quán)重：wi1，wi2，……，wik。

(4)For j=1，2，…，k do

(5)輸出子圖 g 支持度 sup(g，D)。

計(jì)算加權(quán)子圖支持度的實(shí)例如圖2所示。圖中，動(dòng)態(tài)網(wǎng)絡(luò)在 t1、t2、t3時(shí)刻形成的無向網(wǎng)絡(luò)圖(本文針對(duì)的是頂點(diǎn)和邊均有標(biāo)記的無向加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)圖)，對(duì)應(yīng)的權(quán)重分別為 w1、w2、w3。 假設(shè)權(quán)重 w1=1、w2=2、w3=3，從圖2可看出，路徑圖 P(v1～v2～v3)只出現(xiàn)在 t1和 t3時(shí)刻的網(wǎng)絡(luò)圖中，所以其絕對(duì)支持度為：

圖2 加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)

結(jié)合GASTON算法[9]的策略方法，下面給出挖掘加權(quán)圖集中頻繁子圖的算法步驟：

算法2 挖掘頻繁路徑(Path)

輸入：加權(quán)圖集D，圖編碼，內(nèi)嵌列表，最小支持度min_sup，路徑 P。

輸出：頻繁路徑(Path)。

(1)事先由算法1計(jì)算加權(quán)圖集中所有頂點(diǎn)和邊的支持度，刪除小于min_sup的頂點(diǎn)和邊。

(2)由算法1計(jì)算出路徑P的支持度，如果其支持度support(P)＜min_sup，則停止擴(kuò)展，剪掉其所有超圖；否則從內(nèi)嵌列表選取可擴(kuò)展的邊l，構(gòu)造新圖g←l+P。

(3)如果新圖g還是路徑，則轉(zhuǎn)至步驟(2)。

(4)如果新圖g是樹則轉(zhuǎn)至算法3。

(5)如果新圖g是具有循環(huán)的圖則轉(zhuǎn)至算法4。

算法3 挖掘頻繁樹(Tree)

輸入：加權(quán)圖集D，圖編碼，內(nèi)嵌列表，最小支持度min_sup，樹 T。

輸出：頻繁樹。

(1)由算法1計(jì)算出樹T的支持度，如果其支持度support(G)＜min_sup，則停止擴(kuò)展，剪掉其所有超圖；否則從內(nèi)嵌列表選取可擴(kuò)展的邊l，構(gòu)造新圖g←l+T。

(2)如果新圖g還是樹，則轉(zhuǎn)至步驟(1)。

(3)如果新圖g是具有循環(huán)的圖則轉(zhuǎn)至算法4。

算法4 挖掘頻繁循環(huán)圖(Cyclic Graph)

輸入：加權(quán)圖集D，圖編碼，內(nèi)嵌列表，最小支持度min_sup，圖 G。

輸出：頻繁圖。

(1)由算法1計(jì)算出圖G的支持度，如果其支持度support(G)＜min_sup，則停止擴(kuò)展，剪掉其所有超圖。

(2)否則從內(nèi)嵌列表選取可擴(kuò)展的邊l，構(gòu)造新圖g←l+G，轉(zhuǎn)至步驟(1)。

(3)輸出所有頻繁圖。

從算法 2～算法 4，先找出頻繁路徑，如果該路徑擴(kuò)展成樹，則轉(zhuǎn)至找頻繁樹；如果擴(kuò)展成圖，則轉(zhuǎn)至尋找頻繁循環(huán)圖。在尋找頻繁樹時(shí)，如果樹擴(kuò)展成循環(huán)圖則轉(zhuǎn)至尋找頻繁循環(huán)圖；最后找出頻繁循環(huán)圖。其實(shí)，路徑和樹都是無循環(huán)的特殊的圖，所以最后輸出的加權(quán)頻繁子圖也包括路徑和樹。

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

3.1算法性能測試

本文測試使用的數(shù)據(jù)集是有關(guān)分子生物活性信息的真實(shí)數(shù)據(jù)集NCI-H23，這個(gè)數(shù)據(jù)集可以從以下網(wǎng)址獲得：http：//www.cs.ucsb.edu/～xyan/dataset.htm。

NCI-H23數(shù)據(jù)集包括具有活性和無活性兩種類別的圖集，其中頂點(diǎn)有60多種標(biāo)記，邊有2種標(biāo)記。假設(shè)無活性的圖權(quán)重為1，而具有活性的圖權(quán)重為2。本文選取200個(gè)具有活性和200個(gè)無活性的圖，然后組成了一個(gè)具有400個(gè)圖的加權(quán)圖集。

算法測試用的PC機(jī)使用Intel Pentium(R)2.6GHz CPU和512 MB的內(nèi)存，操作系統(tǒng)為Red Hat Linux，算法使用C++語言實(shí)現(xiàn)，并用g++編譯。實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 性能測試

從圖3可以看出，當(dāng)支持度比較小時(shí)，算法挖出到的頻繁子圖數(shù)目非常大，如在最小絕對(duì)支持度為60時(shí)，可挖掘到18 673個(gè)頻繁子圖，這比最小絕對(duì)支持度為120時(shí)挖掘到的675個(gè)頻繁子圖多了27倍；運(yùn)行時(shí)間則是隨著最小支持度的增加而減少，在最小絕對(duì)支持度為96時(shí)，運(yùn)行時(shí)間只需0.69 s，總體上算法具有良好的效率。

3.2股票市場網(wǎng)絡(luò)的挖掘應(yīng)用

結(jié)合中國股票市場，利用本文提出的算法挖掘股票市場網(wǎng)絡(luò)中的頻繁模式。一般股票價(jià)格會(huì)隨著時(shí)間變化，不同時(shí)段股票跌幅或漲幅不一樣。本文抽取20支股票，這些股票來自電子行業(yè)、啤酒行業(yè)、金融銀行等領(lǐng)域，然后以一個(gè)季度為一個(gè)時(shí)段，統(tǒng)計(jì)這些股票在2010年四個(gè)季度里的漲跌情況，其中在每個(gè)季度里，分四種情況劃分成四種網(wǎng)絡(luò)：漲幅超過40%的股票網(wǎng)絡(luò)、漲幅在40%以內(nèi)的股票網(wǎng)絡(luò)、跌幅在20%以內(nèi)的股票網(wǎng)絡(luò)以及跌幅超過20%的股票網(wǎng)絡(luò)。股票網(wǎng)絡(luò)中，頂點(diǎn)表示股票，不同股票，標(biāo)記也不同，而股票間的關(guān)聯(lián)就是邊，不同股票的邊標(biāo)記也不同，同一個(gè)網(wǎng)絡(luò)中的任意兩支股票均有一條具有標(biāo)記的邊相連。在實(shí)際中，對(duì)于漲幅比較高或者跌幅比較大的情況應(yīng)給予額外關(guān)注，為此對(duì)漲幅超過40%和跌幅超過20%的網(wǎng)絡(luò)加大權(quán)重，本文設(shè)定這兩種網(wǎng)絡(luò)權(quán)重為2，而其他兩種網(wǎng)絡(luò)則給予1的權(quán)重?？偣驳玫?個(gè)網(wǎng)絡(luò)圖組成的圖集，其中有3個(gè)網(wǎng)絡(luò)圖屬于漲幅超過40%或者跌幅超過20%，給予的權(quán)重為 2，其余6個(gè)網(wǎng)絡(luò)圖權(quán)重為 1。利用本文WGDM算法挖掘這個(gè)加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)圖集的頻繁模式，而用GASTON算法挖掘無加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)圖集(即所有圖權(quán)重都為1)，其中設(shè)定絕對(duì)最小絕對(duì)支持度min_sup為4時(shí)，可以發(fā)現(xiàn)兩種具有5個(gè)頂點(diǎn)的頻繁模式如圖4所示。

實(shí)際中，相同行業(yè)的公司、企業(yè)的發(fā)展趨勢比較有相同之處，其股價(jià)也較有可能同漲同跌。如圖4所示，本文挖掘出的頻繁模式，都是由銀行組成，而GASTON算法挖掘出的頻繁模式由銀行和汽車兩個(gè)不同行業(yè)組成。所以本文算法的挖掘結(jié)果，與實(shí)際比較吻合，進(jìn)一步驗(yàn)證了本文算法的有效性。

圖4 挖掘的頻繁模式對(duì)比

挖掘加權(quán)動(dòng)態(tài)網(wǎng)絡(luò)的頻繁子圖困難在于產(chǎn)生的候選子圖數(shù)量過多，而且子圖同構(gòu)檢測問題也會(huì)影響算法的效率。對(duì)此，本文算法利用支持度的反單調(diào)性對(duì)搜索空間進(jìn)行裁剪，并采用參考文獻(xiàn)[7]的策略將挖掘圖劃分成挖掘路徑、樹和循環(huán)圖的三個(gè)子問題，減少了候選子圖數(shù)量和子圖同構(gòu)檢測次數(shù)，提高了算法效率。而且將算法應(yīng)用于實(shí)際的股票市場網(wǎng)絡(luò)，挖掘結(jié)果也驗(yàn)證了本文算法的有效性。本文算法還可進(jìn)一步拓展應(yīng)用到其他網(wǎng)絡(luò)的頻繁模式挖掘。

[1]RADICCHIF， CASTELLANO C， CECCONIF， etal.Defining and identifying communities in networks[J].PNAS，2004， 101(9)： 2658-2663.

[2]XU J J， CHEN H C.CrimeNet explorer： a framework for criminal network knowledge discovery[J].ACM Transactions on Information Systems， 2005， 23(2).

[3]BERGER-W T Y，SAIA J.A frameworkfor analysis of dynamic social networks[C].KDD’06.Philadelphia： [s.n.]，2006：523-528.

[4]耿汝年，董祥軍，須文波.基于全局圖遍歷的加權(quán)頻繁模式挖掘算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2008，14(6)：1220-1229.

[5]王映龍，楊珺，周法國，等.加權(quán)最大頻繁子圖挖掘算法的研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(20)：31-34.

[6]封軍，鄭誠，鄭曉波，等.基于加權(quán)有向圖的權(quán)頻繁模式挖掘算法[J].微型機(jī)與應(yīng)用，2010，29(20)：4-7.

[7]Jiang Chuntao， COENEN F， ZITO M.Frequent sub-graph minjing on edge weighted graphs[C].DaWak’10 Proceedings of the 12th international conference on Data Warehousing and knowledge discovery， Spinger-Verlag， 2010：77-88.

[8]高琳，覃桂敏，周曉峰.圖數(shù)據(jù)庫中頻繁模式挖掘算法研究綜述[J].電子學(xué)報(bào)，2008，36(8)：1603-1609.

[9]NIJSSEN S，KOK J N.Aquick start in frequent structure mining can make a difference[C].Proceeding of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD-2004).Seattle， WA， USA：Springer-Verlag， 2004： 4571-4577.