摘  要： 不同時刻的動態(tài)網(wǎng)絡(luò)往往具有不同權(quán)重,，針對加權(quán)動態(tài)網(wǎng)絡(luò)的頻繁模式挖掘,，提出一種挖掘算法WGDM,，它適用于加權(quán)動態(tài)社會網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等方面的頻繁模式挖掘,。WGDM算法利用支持度的反單調(diào)性裁剪搜索空間,，從而減少冗余候選子圖，提高算法效率,。通過實驗測試了WGDM算法的性能,，并根據(jù)中國實際股票市場網(wǎng)絡(luò)，利用WGDM算法挖掘股票市場網(wǎng)絡(luò)中有趣的頻繁模式,。
關(guān)鍵詞： 加權(quán)動態(tài)網(wǎng)絡(luò),；加權(quán)圖集；頻繁子圖,；圖挖掘

　近年來,，針對社會網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等的挖掘研究越來越多(如社區(qū)識別,、社區(qū)關(guān)系發(fā)現(xiàn)等)[1]，尤其是針對犯罪團伙和恐怖分子活動網(wǎng)絡(luò)的研究,，引起了世界各國的重視[2],。實際中，網(wǎng)絡(luò)往往隨時間而變動,，即網(wǎng)絡(luò)是動態(tài)網(wǎng)絡(luò)[3],。挖掘動態(tài)網(wǎng)絡(luò)中的頻繁模式，即可以發(fā)現(xiàn)變化網(wǎng)絡(luò)中具有相對“穩(wěn)定性”的頻繁模式,，這些模式在動態(tài)網(wǎng)絡(luò)中往往也是比較有趣和重要的,，這對研究動態(tài)網(wǎng)絡(luò)很有意義。由于圖具有結(jié)構(gòu)關(guān)系,，可用來表示事物之間復(fù)雜的相互作用關(guān)系,，是基本的數(shù)據(jù)結(jié)構(gòu)，因此網(wǎng)絡(luò)可用圖來表示,，即一個網(wǎng)絡(luò)可抽象成一個圖,，對網(wǎng)絡(luò)的挖掘研究也就轉(zhuǎn)化為對圖的挖掘研究。
　在實際中,，一個動態(tài)網(wǎng)絡(luò)在某個時刻表現(xiàn)出來的整體重要性可能并不一樣,，這就需要考慮各個時刻網(wǎng)絡(luò)的不同權(quán)重，即考慮加權(quán)的動態(tài)網(wǎng)絡(luò),。而挖掘加權(quán)動態(tài)網(wǎng)絡(luò)的頻繁模式,，即是挖掘加權(quán)圖集的頻繁子圖。
對圖加權(quán)主要包括頂點,、邊和整個圖的加權(quán),。當(dāng)前,，已經(jīng)提出一些關(guān)于加權(quán)圖集的頻繁子圖挖掘算法[4-7]，如參考文獻(xiàn)[4],、[6]提出的是基于頂點加權(quán)的頻繁子圖挖掘,，而參考文獻(xiàn)[5]、[7]則是基于邊加權(quán)的頻繁子圖挖掘,。
網(wǎng)絡(luò)在某個時刻的重要性可以對整個圖賦予不同權(quán)重來表示,，無需考慮網(wǎng)絡(luò)內(nèi)部頂點和邊的權(quán)重，有時也很難知道頂點和邊的權(quán)重,，針對這種整個圖加權(quán)的挖掘,，關(guān)于頂點或邊加權(quán)的挖掘算法均不適用于這種挖掘。為此本文提出一種適用于整個圖加權(quán)的頻繁模式挖掘算法(簡稱WGDM),。

　sup(P)=w1+w3=1+3=4
　結(jié)合GASTON算法[9]的策略方法,，下面給出挖掘加權(quán)圖集中頻繁子圖的算法步驟：
　算法2 挖掘頻繁路徑(Path)
　輸入：加權(quán)圖集D，圖編碼,，內(nèi)嵌列表,，最小支持度min_sup，路徑P,。
　輸出：頻繁路徑(Path),。
　(1)事先由算法1計算加權(quán)圖集中所有頂點和邊的支持度，刪除小于min_sup的頂點和邊,。
　(2)由算法1計算出路徑P的支持度,，如果其支持度support(P)<min_sup，則停止擴展,，剪掉其所有超圖,；否則從內(nèi)嵌列表選取可擴展的邊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計算出樹T的支持度，如果其支持度support(G)<min_sup,，則停止擴展,，剪掉其所有超圖,；否則從內(nèi)嵌列表選取可擴展的邊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計算出圖G的支持度,，如果其支持度support(G)<min_sup，則停止擴展,，剪掉其所有超圖,。
　(2)否則從內(nèi)嵌列表選取可擴展的邊l，構(gòu)造新圖g←l+G,，轉(zhuǎn)至步驟(1),。
　(3)輸出所有頻繁圖。
　從算法2~算法4,，先找出頻繁路徑，如果該路徑擴展成樹,，則轉(zhuǎn)至找頻繁樹,；如果擴展成圖，則轉(zhuǎn)至尋找頻繁循環(huán)圖,。在尋找頻繁樹時,，如果樹擴展成循環(huán)圖則轉(zhuǎn)至尋找頻繁循環(huán)圖；最后找出頻繁循環(huán)圖,。其實,，路徑和樹都是無循環(huán)的特殊的圖，所以最后輸出的加權(quán)頻繁子圖也包括路徑和樹,。
3 實驗
3.1 算法性能測試
　本文測試使用的數(shù)據(jù)集是有關(guān)分子生物活性信息的真實數(shù)據(jù)集NCI-H23,，這個數(shù)據(jù)集可以從以下網(wǎng)址獲　得：http：//www.cs.ucsb.edu/~xyan/dataset.htm。
　NCI-H23數(shù)據(jù)集包括具有活性和無活性兩種類別的圖集,，其中頂點有60多種標(biāo)記,，邊有2種標(biāo)記。假設(shè)無活性的圖權(quán)重為1,，而具有活性的圖權(quán)重為2,。本文選取200個具有活性和200個無活性的圖,，然后組成了一個具有400個圖的加權(quán)圖集。
　算法測試用的PC機使用Intel Pentium(R)2.6 GHz CPU和512 MB的內(nèi)存,，操作系統(tǒng)為Red Hat Linux,，算法使用C++語言實現(xiàn)，并用g++編譯,。實驗結(jié)果如圖3所示,。

　從圖3可以看出，當(dāng)支持度比較小時,，算法挖出到的頻繁子圖數(shù)目非常大,，如在最小絕對支持度為60時，可挖掘到18 673個頻繁子圖,，這比最小絕對支持度為120時挖掘到的675個頻繁子圖多了27倍,；運行時間則是隨著最小支持度的增加而減少，在最小絕對支持度為96時,，運行時間只需0.69 s,，總體上算法具有良好的效率。
3.2 股票市場網(wǎng)絡(luò)的挖掘應(yīng)用
　結(jié)合中國股票市場,，利用本文提出的算法挖掘股票市場網(wǎng)絡(luò)中的頻繁模式,。一般股票價格會隨著時間變化，不同時段股票跌幅或漲幅不一樣,。本文抽取20支股票,，這些股票來自電子行業(yè)、啤酒行業(yè),、金融銀行等領(lǐng)域,，然后以一個季度為一個時段，統(tǒng)計這些股票在2010年四個季度里的漲跌情況,，其中在每個季度里,，分四種情況劃分成四種網(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ò)中，頂點表示股票,，不同股票,，標(biāo)記也不同，而股票間的關(guān)聯(lián)就是邊,，不同股票的邊標(biāo)記也不同,，同一個網(wǎng)絡(luò)中的任意兩支股票均有一條具有標(biāo)記的邊相連。在實際中,，對于漲幅比較高或者跌幅比較大的情況應(yīng)給予額外關(guān)注,，為此對漲幅超過40%和跌幅超過20%的網(wǎng)絡(luò)加大權(quán)重,，本文設(shè)定這兩種網(wǎng)絡(luò)權(quán)重為2，而其他兩種網(wǎng)絡(luò)則給予1的權(quán)重,?？偣驳玫?個網(wǎng)絡(luò)圖組成的圖集，其中有3個網(wǎng)絡(luò)圖屬于漲幅超過40%或者跌幅超過20%,，給予的權(quán)重為2,，其余6個網(wǎng)絡(luò)圖權(quán)重為1。利用本文WGDM算法挖掘這個加權(quán)動態(tài)網(wǎng)絡(luò)圖集的頻繁模式,，而用GASTON算法挖掘無加權(quán)動態(tài)網(wǎng)絡(luò)圖集(即所有圖權(quán)重都為1),，其中設(shè)定絕對最小絕對支持度min_sup為4時，可以發(fā)現(xiàn)兩種具有5個頂點的頻繁模式如圖4所示,。

　實際中,，相同行業(yè)的公司、企業(yè)的發(fā)展趨勢比較有相同之處,，其股價也較有可能同漲同跌,。如圖4所示，本文挖掘出的頻繁模式,，都是由銀行組成,，而GASTON算法挖掘出的頻繁模式由銀行和汽車兩個不同行業(yè)組成。所以本文算法的挖掘結(jié)果,，與實際比較吻合,，進(jìn)一步驗證了本文算法的有效性。
　挖掘加權(quán)動態(tài)網(wǎng)絡(luò)的頻繁子圖困難在于產(chǎn)生的候選子圖數(shù)量過多,，而且子圖同構(gòu)檢測問題也會影響算法的效率,。對此，本文算法利用支持度的反單調(diào)性對搜索空間進(jìn)行裁剪,，并采用參考文獻(xiàn)[7]的策略將挖掘圖劃分成挖掘路徑、樹和循環(huán)圖的三個子問題,，減少了候選子圖數(shù)量和子圖同構(gòu)檢測次數(shù),，提高了算法效率。而且將算法應(yīng)用于實際的股票市場網(wǎng)絡(luò),，挖掘結(jié)果也驗證了本文算法的有效性,。本文算法還可進(jìn)一步拓展應(yīng)用到其他網(wǎng)絡(luò)的頻繁模式挖掘。
參考文獻(xiàn)
[1] RADICCHI F,， CASTELLANO C,， CECCONI F， et al. 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].計算機集成制造系統(tǒng)，2008,，14(6)：1220-1229.
[5] 王映龍,，楊珺，周法國,，等.加權(quán)最大頻繁子圖挖掘算法的研究[J].計算機工程與應(yīng)用,，2009，45(20)：31-34.
[6] 封軍,，鄭誠,，鄭曉波，等.基于加權(quán)有向圖的權(quán)頻繁模式挖掘算法[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é)報，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.