劉瑩，杜奕智，鄒樂(lè)

?

大圖挖掘中一種基于云計(jì)算的改進(jìn)SpiderMine算法

劉瑩，杜奕智，鄒樂(lè)

摘 要：現(xiàn)有的圖挖掘算法在云環(huán)境下難以有效地進(jìn)行大規(guī)模圖形的高頻模式挖掘。為此，對(duì)SpiderMine算法做了改進(jìn)，提出一種基于云的SpiderMine算法（c-SpiderMine）。首先，利用最小切割算法將大規(guī)模圖形數(shù)據(jù)分為多個(gè)子圖，使分區(qū)/融合成本最小，然后，利用SpiderMine進(jìn)行模式挖掘，顯著降低了大型模式生成時(shí)的組合復(fù)雜度。最后，采用一種模式鍵函數(shù)來(lái)保存模式，以保證所有模式可被成功恢復(fù)和融合。基于3種真實(shí)數(shù)據(jù)集的仿真實(shí)驗(yàn)結(jié)果表明，c-SpiderMine可高效挖掘云環(huán)境下的前K個(gè)大型模式，在不同數(shù)據(jù)規(guī)模和最小支持設(shè)置條件下，c-SpiderMine在內(nèi)存使用和運(yùn)行時(shí)間方面的性能均優(yōu)于SpiderMine。

關(guān)鍵詞：圖挖掘；云計(jì)算；高頻模式；最小切割算法；模式鍵函數(shù)；運(yùn)行時(shí)間

0 引言

圖挖掘問(wèn)題[1-3]在移動(dòng)互聯(lián)網(wǎng)、大數(shù)據(jù)處理等領(lǐng)域具有十分重要的應(yīng)用價(jià)值，是目前的研究熱點(diǎn)。文獻(xiàn)[4]采用社會(huì)網(wǎng)絡(luò)中的信息傳播模型研究在單個(gè)大圖中挖掘近鄰頻繁模式，提出了一種基于共生頻繁項(xiàng)樹(shù)和逆矩陣的圖挖掘算法。該方法快過(guò)傳統(tǒng)的單個(gè)大圖頻繁子圖挖掘算法，返回的結(jié)果也多過(guò)頻繁子圖挖掘算法，并且可以發(fā)現(xiàn)一些傳統(tǒng)頻繁子圖挖掘算法發(fā)現(xiàn)不了的有趣模式。然而，該算法的計(jì)算量較大。文獻(xiàn)[5]中的SpiderMine算法采用概率挖掘理論來(lái)尋找前K個(gè)最大模式，通過(guò)將小規(guī)模高頻率模式融合為大規(guī)模模式，克服了算法瓶頸，效率較高。文獻(xiàn)[6]針對(duì)現(xiàn)有云計(jì)算平臺(tái)資源隨機(jī)調(diào)配與傳統(tǒng)導(dǎo)出子圖挖掘效率較低等問(wèn)題，提出了一種自適應(yīng)云端的大規(guī)模導(dǎo)出子圖提取算法，以解決資源優(yōu)化利用與海量圖挖掘等問(wèn)題。文獻(xiàn)[7]提出一種圖形挖掘系統(tǒng)OPAvion。該系統(tǒng)可引導(dǎo)用戶逐漸探索圖形，以選擇的節(jié)點(diǎn)或標(biāo)記后的異常節(jié)點(diǎn)開(kāi)始，然后用戶可擴(kuò)展至節(jié)點(diǎn)的鄰域，對(duì)它們貼上類別標(biāo)簽，因此可對(duì)圖形的感興趣部分進(jìn)行交互式引導(dǎo)。然而，上述方法均無(wú)法進(jìn)行云環(huán)境下大規(guī)模圖形的高頻率模式挖掘。其主要原因在于：（1）圖分割問(wèn)題?，F(xiàn)有的算法難以生成小型等直徑模式，如果模式切割不當(dāng)則會(huì)在模式恢復(fù)、模式再搜索和模式融合方面產(chǎn)生模式成本。為此，如何定義并有效利用合適的模式切割是本文主要任務(wù)之一。（2）信息不對(duì)稱。每臺(tái)機(jī)器間缺乏溝通，可能導(dǎo)致信息丟失，增加不必要的計(jì)算負(fù)擔(dān)。（3）模式保存融合問(wèn)題。在融合步驟，必須要保證不同分區(qū)中的模式利用其他模式仍可實(shí)現(xiàn)有效檢測(cè)和歸納。現(xiàn)有的算法難以做到這一點(diǎn)。

為了解決以上問(wèn)題，本文針對(duì)文獻(xiàn)[5]中的SpiderMine算法提出云環(huán)境下的新算法c-SpiderMine。已經(jīng)證明SpiderMine可有效地對(duì)經(jīng)過(guò)標(biāo)識(shí)的圖形進(jìn)行挖掘。它是一種基于近似的圖形模式挖掘算法，通過(guò)隨機(jī)游走實(shí)現(xiàn)模式檢測(cè)，但無(wú)法保證檢測(cè)出所有模式。于是，本文試圖通過(guò)完整的模式搜索來(lái)檢測(cè)模式，在隨機(jī)游走時(shí)對(duì)所有節(jié)點(diǎn)進(jìn)行游走以避免模式丟失。c-SpiderMine包括3個(gè)階段：分區(qū)；挖掘；融合。分區(qū)階段利用最小切割算法將大規(guī)模圖形數(shù)據(jù)分為多個(gè)子圖，使分區(qū)/融合成本最小。第2階段為挖掘階段，利用SpiderMine進(jìn)行模式挖掘，利用約簡(jiǎn)器可有效降低圖形同構(gòu)測(cè)試的成本，顯著降低大型模式生成時(shí)的組合復(fù)雜度。更重要的是，本文構(gòu)建一個(gè)全局表格以避免該階段出現(xiàn)不對(duì)稱信息。最后一個(gè)階段是模式融合。我們提出一種模式鍵(pattern key，PK)函數(shù)來(lái)保存模式，以保證所有模式可被成功恢復(fù)和融合。仿真結(jié)果表明，當(dāng)最小支持量和圖像規(guī)模不同時(shí)c-SpiderMine在運(yùn)行時(shí)間方面的性能均優(yōu)于SpiderMine。

1 問(wèn)題描述

首先在1.1節(jié)描述了圖分割問(wèn)題，然后在1.2節(jié)討論如果沒(méi)有及時(shí)的信息共享，部分高頻率模式是如何丟失的。最后一節(jié)簡(jiǎn)述模式保存融合問(wèn)題。

1.1圖分割

在進(jìn)行圖分割時(shí)必須要保留模式，因?yàn)槿绻谠撾A段大量模式被損壞，可能導(dǎo)致其余階段花費(fèi)大量時(shí)間搜索這些模式。此外，因?yàn)橛写罅窟吘墝⒈环指?，所以如果有模式受損，還將導(dǎo)致融合階段的成本增大。因此，本文采用最小切邊最大流算法[8]來(lái)解決這一問(wèn)題。將輸入的數(shù)據(jù)圖表示為G，將分割數(shù)據(jù)集表示為S。圖分割問(wèn)題可定義如下：

從定義1中可以發(fā)現(xiàn)，Si和Sj的所有并集為空集。即Si和Sj間的切邊在任何分區(qū)中都不會(huì)被保留。因此，在原始圖G中具有切邊的模式將被分割為不同的數(shù)據(jù)分區(qū)，進(jìn)而丟失其原先結(jié)構(gòu)。SpiderMine算法的思路是：模式1P1可用另一模式P2進(jìn)行擴(kuò)展，前提是有一個(gè)頂點(diǎn)u屬于u的頂點(diǎn)集合和P2的頂點(diǎn)集合即如果且則可用P2對(duì)P1進(jìn)行擴(kuò)展。然而，根據(jù)定義1，因此在MapReduce模型[9]中的每個(gè)映射程序生成高頻率模式后，Si和Sj中沒(méi)有屬于Pi和Pj的模式可被融合或通過(guò)SpiderMine實(shí)現(xiàn)增長(zhǎng)。

1.2不對(duì)稱信息

在分割階段，每個(gè)映射程序開(kāi)始自己的任務(wù)直到任務(wù)完成。然而，每個(gè)映射程序只關(guān)注于自己的狀態(tài)，于是導(dǎo)致信息不對(duì)稱。例如，在機(jī)器1和2中有一個(gè)低頻率模式，但是該模式的總量非常頻繁，于是在該例子中，系統(tǒng)將會(huì)認(rèn)為該模式的頻率較低而修剪這一模式。在經(jīng)典的MapReduce模型中，我們會(huì)在分區(qū)階段把圖形G分割為多個(gè)子圖在挖掘階段，我們需要挖掘初始時(shí)頻率較低的圖形模式，稱為spider，定義2中對(duì)此進(jìn)行描述。于是，我們面臨的問(wèn)題是：如果一個(gè)模式在不同的數(shù)據(jù)分區(qū)中有許多類似模式，那么如何對(duì)高頻率模式的支持情況進(jìn)行統(tǒng)計(jì)。為此，本文采用BSP模型來(lái)在不同內(nèi)核中運(yùn)行并行模式增長(zhǎng)算法，并維護(hù)一個(gè)全局表來(lái)記錄全局支持計(jì)數(shù)。

定義2：將半徑約束在r范圍內(nèi)的高頻率模式稱為r-spider。用圖形的頭部（head）表示每個(gè)spider。Spider的半徑為其節(jié)點(diǎn)的最小偏心率。因此，radius（spider）

1.3模式融合

在融合階段，將利用挖掘階段生成的spider生成全局高頻率模式。這一問(wèn)題的簡(jiǎn)單求解方法是發(fā)送spider然后對(duì)其融合。然而，如果在一臺(tái)機(jī)器上融合所有圖形，則將產(chǎn)生兩個(gè)問(wèn)題。首先，約簡(jiǎn)程序的存儲(chǔ)空間無(wú)法從所有映射程序中讀取所有的高頻率子圖，因?yàn)楦哳l率模式集合的數(shù)據(jù)規(guī)模大于原始的輸入圖形規(guī)模。其次，難以定義合適的融合鍵值。對(duì)鍵值做普通選擇會(huì)復(fù)制切割節(jié)點(diǎn)。然而，選擇這些節(jié)點(diǎn)作為鍵值會(huì)導(dǎo)致部分大規(guī)模模式無(wú)法被融合。

2 c-SpiderMine算法

圖1給出了本文方法的框架。2.1節(jié)討論如何利用最小切邊算法將一個(gè)大型圖形數(shù)據(jù)分割為多個(gè)子圖。然后，在2.2節(jié)討論各機(jī)器間如何通過(guò)全局表進(jìn)行溝通。最后一節(jié)簡(jiǎn)要討論P(yáng)K函數(shù)如何恢復(fù)和融合spider，以避免模式丟失問(wèn)題。本文方法的框架如圖1所示：

圖1　c-SpiderMine的框架

2.1分割階段

本文采用最小切邊算法來(lái)進(jìn)行圖分割。這種算法的優(yōu)點(diǎn)在于，被切割的邊緣數(shù)量越少，被損壞的模式數(shù)量越少。換句話說(shuō)，我們可以保留更多當(dāng)前模式，降低剩余階段搜索相同模式的時(shí)間。最小切邊集合的概念見(jiàn)定義3。

定義3：已知圖形G( V, E )，其中V表示頂點(diǎn)結(jié)合，E表示邊緣集合，G( V, E )的最小切邊集合Ec ( S, T )可將V分割為S且T= V-S，同時(shí)我們有sE S，tE T，且Ec ( S, T )=ΣuE S, v E T Ec ( u, v )的容量最小。

為了將圖形G( V, E )分割為k個(gè)均勻子圖且每個(gè)子圖均能保留其結(jié)構(gòu)，本文首先利用最小切邊集合Ec將一個(gè)圖形分割為多個(gè)子圖。然后，在u和v分別隸屬的兩個(gè)子圖中，復(fù)制最小切邊集合Ec 上的所有節(jié)點(diǎn)對(duì)(u, v )。該階段的算法見(jiàn)算法1。

算法1：分割階段要求：圖G= V E(　 ) , k：圖形分割數(shù)量輸出：G被分割的子圖1：G　 g　 g sub　k ={｝1,...,：←_ 2：for 每個(gè)G　 k Partition G ksub(　 ) , g gE G　 do 3：,i　 j　 sub E　 v v　 v　 g V　 v　 g　 Vc←　　?E　　?E　 //添加{(　 )　 ( )　( ) i j　 i　 i　j　 j ,, ｝giE 4：g中的切邊集合和jc←　　∪//添加g E　 g E　 Ei( )　 ( ) i C V的連通邊緣、5：g的切割節(jié)點(diǎn)集合ic←　　∪　　?E?E?≠6：輸出所有子圖g　 E　 g　 E　 v v　 v　 E　 v　 E　 i　 ji( )　 ( )　 (　 ){,｝i i　 j　 i　 C　 j　 C Gsub

2.2挖掘階段

在挖掘階段的第1步，本文采用文獻(xiàn)[10]中提出的模式增長(zhǎng)算法實(shí)現(xiàn)spider增長(zhǎng)，以便在半徑約束內(nèi)挖掘所有的高頻率圖形模式。它只需一個(gè)處理器就可獲得所有的初始spider。在該階段中，首先需要選擇一個(gè)節(jié)點(diǎn)作為初始模式。然后，算法利用與模式相連的邊緣來(lái)擴(kuò)展模式，進(jìn)而生成新的候選。算法還收集模式嵌入因子。如果嵌入因子數(shù)量低于支持閾值，則算法修剪候選。為了實(shí)現(xiàn)spider的并行增長(zhǎng)，本文采用BSP模型來(lái)增長(zhǎng)相同深度內(nèi)不同子圖中的spider。即可以在同一超級(jí)步驟內(nèi)生成邊緣和節(jié)點(diǎn)數(shù)量相同的所有高頻率spider候選。

在挖掘階段的第2步中，通過(guò)構(gòu)建一個(gè)全局表來(lái)維護(hù)每個(gè)spider候選的支持?jǐn)?shù)。在同頻率圖形模式候選集合增長(zhǎng)期間，我們通過(guò)Canonical forms[11]對(duì)候選模式進(jìn)行編碼，將每個(gè)候選模式的本地支持量發(fā)送給全局表。然后，在超級(jí)步驟結(jié)束后修剪頻率較低的候選，并確保所有處理器均增加了候選的可能嵌入因子數(shù)。通過(guò)這種方法可以保證不會(huì)有模式由于信息不對(duì)稱而被修剪。給出了BSP模型的全局表示例如圖2所示：

圖2　BSP模型的全局表示例

挖掘階段的整個(gè)步驟見(jiàn)算法2。

算法2：MiningPhase（挖掘階段）要求：G　：分割后的子圖subr：圖形半徑θ：最小支持閾值輸出：G　中的切邊集合和高頻率圖形模式集合Map (Key k, Value v)E G　 S’：c　 id(　 ),sub

1：G　← k //鍵定義為子圖ID 2：id G　← v //值定義為子圖數(shù)據(jù)3：利用標(biāo)識(shí)頻率對(duì)subG　中所有節(jié)點(diǎn)進(jìn)行同步和排序4：for allgE G　 do5： 修剪低頻率標(biāo)識(shí)，重新標(biāo)識(shí)sub g的節(jié)點(diǎn)6：輸出i　sub G　 G Reduce(Key k, Values v[]) 1：iid　 sub , G　← k //鍵為子圖ID 2：id G　← v //值為子圖數(shù)據(jù)3：subG　中所有本地高頻率單邊緣圖形4：for 每個(gè)S←1 sub sE S do 5：1( )　( ) supglobals　 CalculateSupport s←S← S；7：if6：1 S≠? do 8： for 每個(gè)sE Sdo9： if( ) supglobals＜ θ 且( ) Radius s　 r≠ then10：'←　_ 11： else 12：{｝S　 S　 ssup 13　 ,sup　/ /{｝S　 GrowPattern sglobal'←　 //生成候選圖形模式并更新sync s　 //BSP模型同步14：輸出13：(　 ) s global E　 G　 S'(　 ) ,supglobalc　 id(　 ),

2.3融合階段

融合階段的整個(gè)步驟見(jiàn)算法3：

算法3：MergingPhase（融合階段）要求：E Cand Patterns，圖形切邊和候選模式對(duì)組成的集合輸出：c,　 _ F，高頻率圖形模式Map (Key k, Value v) 1：Cand Patterns← v _ 2：for each do 3： for each v　 Cand Patterns E__　　?≠　 do 4：iv　 Cand Patterns　 v　 i　 jjE{｝_ i Q　 SpiderExtend v v =(　 ) , i　 j Q≠? then 6： 輸出5： if Q　 E Q　 //模式規(guī)模和被融合模式對(duì)Reduce(Key k, Values v[]) 1：while,　 ,(　 ) c v≠? do 2： for 每個(gè)p pE v do 3： if, p= p then 4： 從i　 j i　 jv中修剪pj5： else if p可被融合6：p和i j F　 MergePattern p p ←(　 ) , i　 j 7： else 8：　←　←9： if F　 p F　 p; F≠? then 10： 輸出i j F

融合階段包括兩個(gè)MapReduce任務(wù)。第1個(gè)任務(wù)是將不同子圖中的spider擴(kuò)展為更大規(guī)模的模式。為了解決融合問(wèn)題，我們提出一種可提供基于重疊的模式鍵(pattern key，PK)函數(shù)。鍵(key)定義為每個(gè)高頻率圖形模式候選的哈希碼，值(value)定義為候選spider每個(gè)子圖中嵌入因子數(shù)的支持?jǐn)?shù)之和。PK函數(shù)的作用在于保留初始關(guān)系，提供兩個(gè)子圖間的關(guān)聯(lián)。PK函數(shù)的定義見(jiàn)定義4。

定義4：已知一個(gè)子圖g( V, E )，其中V表示節(jié)點(diǎn)集合，E表示邊緣集合，Vc 表示復(fù)制節(jié)點(diǎn)集。將切割節(jié)點(diǎn)υc EV c的重疊切割節(jié)點(diǎn)集定義為

第2個(gè)任務(wù)稱為模式修剪任務(wù)，內(nèi)容是當(dāng)兩個(gè)模式同形時(shí)修剪掉重復(fù)的模式。模式修剪任務(wù)之后，我們可以計(jì)算每個(gè)模式的支持?jǐn)?shù)。最后，將所有模式發(fā)送給模式融合任務(wù)。因?yàn)?，我們已?jīng)在先前的任務(wù)中修剪掉了低頻率模式并進(jìn)行了同構(gòu)測(cè)試，所以通過(guò)檢查兩個(gè)模式是否擁有相同的PK來(lái)進(jìn)行模式融合。如果兩個(gè)模式的PK相同，則通過(guò)該相同的spider對(duì)其融合。重復(fù)這一步驟，直到新生成的模式的直徑超出直徑界限為止。本文方法的一個(gè)示例如圖3所示：

圖3　c-SpiderMine算法的一個(gè)示例

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

本節(jié)利用真實(shí)的數(shù)據(jù)集來(lái)評(píng)估c-SpiderMine算法的性能。3.1節(jié)介紹環(huán)境配置。在3.2節(jié)對(duì)本文算法和SpiderMine算法做比較。最后，在3.3節(jié)介紹c-SpiderMine算法的運(yùn)行時(shí)間和伸縮性。

3.1實(shí)驗(yàn)環(huán)境

本文在33個(gè)虛擬機(jī)構(gòu)成的云計(jì)算環(huán)境下，將c-SpiderMine部署于HAMA 0.5和Hadoop 1.0.3上。其中一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn)，其余節(jié)點(diǎn)均作為從屬節(jié)點(diǎn)。所有實(shí)驗(yàn)運(yùn)行于256GB內(nèi)存和1GB以太網(wǎng)英特爾Xeon服務(wù)器平臺(tái)上。3.2與SpiderMine的比較

為了證明c-SpiderMine的有效性，本文選擇SpiderMine作為基準(zhǔn)算法來(lái)比較節(jié)點(diǎn)數(shù)量不同時(shí)的運(yùn)行時(shí)間，最小支持?jǐn)?shù)不同時(shí)的運(yùn)行時(shí)間及內(nèi)存使用情況。從網(wǎng)站上選擇兩種大型數(shù)據(jù)集[12]進(jìn)行測(cè)試。第1個(gè)大型數(shù)據(jù)集基于comDBLP，包含317,080個(gè)節(jié)點(diǎn)和1,049,866條邊。第2個(gè)數(shù)據(jù)集選擇了Amazone0302，包含262,111個(gè)節(jié)點(diǎn)和1,234,877條邊。這兩種數(shù)據(jù)集廣泛應(yīng)用于實(shí)況社區(qū)，如圖4所示：

圖4　c-SpiderMine和SpiderMine算法的性能比較

如圖4（a）所示，當(dāng)節(jié)點(diǎn)規(guī)模變大時(shí)運(yùn)行時(shí)間上升。在該圖中，我們可以發(fā)現(xiàn)當(dāng)數(shù)據(jù)規(guī)模大于20，000時(shí)，SpiderMine難以為圖形提供支持。相反，當(dāng)數(shù)據(jù)規(guī)模增大時(shí)，c-SpiderMine的性能較優(yōu)。當(dāng)數(shù)據(jù)規(guī)模小于20，000時(shí)，c-SpiderMine的運(yùn)行時(shí)間長(zhǎng)于SpiderMine，因?yàn)樗枰跏荚O(shè)置時(shí)間，比SpiderMine多出180秒。圖4（b）表明即使最小支持?jǐn)?shù)較低，c-SpiderMine在運(yùn)行時(shí)間方面的性能仍優(yōu)于SpiderMine。此外，我們發(fā)現(xiàn)當(dāng)最少支持?jǐn)?shù)低于0.82%時(shí)，c-SpiderMine優(yōu)于SpiderMine。最小支持?jǐn)?shù)控制了高頻率模式的數(shù)量，當(dāng)最小支持?jǐn)?shù)變小時(shí)，生成的高頻率模式數(shù)量將會(huì)上升，導(dǎo)致運(yùn)行時(shí)間變長(zhǎng)。如果最小支持?jǐn)?shù)上升，則運(yùn)行時(shí)間將會(huì)下降?？傮w來(lái)說(shuō)，本文c-SpiderMine方法在處理大規(guī)模圖形數(shù)據(jù)時(shí)顯示出了良好的運(yùn)行時(shí)間性能，降低了內(nèi)存使用量，且效率高于SpiderMine。

3.3伸縮性

雖然本文算法的性能優(yōu)于基準(zhǔn)算法，但是c-SpiderMine對(duì)大規(guī)模圖形數(shù)據(jù)的支持性能仍然需要驗(yàn)證。本小節(jié)實(shí)驗(yàn)將會(huì)改變最小支持設(shè)置、機(jī)器數(shù)量及真實(shí)數(shù)據(jù)集的平均度。

如圖5所示：

圖5　節(jié)點(diǎn)數(shù)量和最小支持設(shè)置不同時(shí)的運(yùn)行時(shí)間

（1）最小支持設(shè)置的影響：我們分別在圖5（a）和5 （b）中給出com-DBLP和Amazone0302的運(yùn)行時(shí)間。兩組實(shí)驗(yàn)的最小支持設(shè)置范圍為0.01%-0.035%，節(jié)點(diǎn)規(guī)模(N )分別為40，000，70，000和100，000。結(jié)果表明，當(dāng)最小支持設(shè)置增加時(shí)，運(yùn)行時(shí)間下降。這表明，當(dāng)最小支持設(shè)置增加時(shí)，生成的模式數(shù)量變小，運(yùn)行時(shí)間降低。此外，當(dāng)N增加時(shí)，運(yùn)行時(shí)間同步增加，明顯表明有更多的節(jié)點(diǎn)生成更多的模式，消耗更多的時(shí)間。實(shí)驗(yàn)表明，當(dāng)節(jié)點(diǎn)規(guī)模和最小支持?jǐn)?shù)增加時(shí)，c-SpiderMine在運(yùn)行時(shí)間方面具有良好的伸縮性。

（2）機(jī)器數(shù)量的影響：本節(jié)研究了機(jī)器數(shù)量不同時(shí)的性能，如圖6所示：

圖6　機(jī)器數(shù)量和最小支持設(shè)置不同時(shí)的運(yùn)行時(shí)間

驗(yàn)證c-SpiderMine的性能時(shí)，對(duì)com-DBLP數(shù)據(jù)集使用4，8，16和32臺(tái)機(jī)器，最小支持設(shè)置為0.25%，0.35%和0.4%；對(duì)Amazone0302數(shù)據(jù)集使用2，4，8，16和32臺(tái)機(jī)器，最小支持設(shè)置為0.2%，0.28%和0.35%。在圖6（a）和6（b）中，當(dāng)機(jī)器數(shù)量上升時(shí)運(yùn)行時(shí)間呈指數(shù)下降。結(jié)果表明，機(jī)器數(shù)量增加可提高性能和效率，這進(jìn)一步證明云計(jì)算可直接提高大規(guī)模圖形數(shù)據(jù)挖掘的伸縮性。

4 總結(jié)

本文提出了c-SpiderMine算法，在處理大規(guī)模圖形數(shù)據(jù)時(shí)有效融合了BSP模型、SpiderMine和云計(jì)算。結(jié)果表明，在不同數(shù)據(jù)規(guī)模和最小支持設(shè)置條件下，c-SpiderMine在內(nèi)存使用和運(yùn)行時(shí)間方面的性能均優(yōu)于SpiderMine，證明c-SpiderMine可高效挖掘云環(huán)境下的前K個(gè)大型模式。我們還證明c-SpiderMine在不同的最小支持設(shè)置、節(jié)點(diǎn)規(guī)模、機(jī)器數(shù)量和平均度條件下，具有良好的伸縮性。經(jīng)證明，c-SpiderMine處理云環(huán)境下大規(guī)模圖形數(shù)據(jù)的性能更為強(qiáng)大。在下步工作中，可結(jié)合更多的真實(shí)大型數(shù)據(jù)集對(duì)本文方法展開(kāi)研究。此外，可在云中部署其他更多的數(shù)據(jù)挖掘算法以提高大數(shù)據(jù)的處理效率。

參考文獻(xiàn)

[1] 孫鶴立,陳強(qiáng),劉瑋,等.利用 MapReduce 平臺(tái)實(shí)現(xiàn)高效并行的頻繁子圖挖掘[J].計(jì)算機(jī)科學(xué)與探索, 2014, 8(7): 790-801.

[2] Anchuri P, Zaki M J, Barkol O, et al. Approximate graph mining with label costs[C]. Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 518-526.

[3] Kang U, Akoglu L, Chau D H P. Big Graph Mining: Algorithms, Anomaly Detection, and Applications [J]. Proceedings of the ACM ASONAM, 2013, 13: 25-28.

[4] 李濤,肖南峰.基于共生頻繁項(xiàng)樹(shù)和逆矩陣的圖挖掘[J].計(jì)算機(jī)應(yīng)用研究,2014, 31(10): 2916-2919.

[5] Zhu F, Qu Q, Lo D, et al. Mining top-k large structural patterns in a massive network[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 807-818.

[6] 郭鑫,董堅(jiān)峰,周清平.自適應(yīng)云端的大規(guī)模導(dǎo)出子圖提取算法[J].計(jì)算機(jī)科學(xué),2014, 41(6): 155-160.

[7] Akoglu L, Chau D H, Kang U, et al. Opavion: Mining and visualization in large graphs[C]. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 2012: 717-720.

[8] Yuan J, Bae E, Tai X C. A study on continuous max-flow and min-cut approaches[C]. Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010: 2217-2224.

[9] Sarma A D, Afrati F N, Salihoglu S, et al. Upper and lower bounds on the cost of a map-reduce computation[C]. Proceedings of the VLDB Endowment. VLDB Endowment, 2013, 6(4): 277-288.

[10] Borgelt C, Meinl T, Berthold M. Moss: a program for molecular substructure mining[C]. Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations. ACM, 2005: 6-15.

[11] Borgelt C. Canonical forms for frequent graph mining [M]. Advances in Data Analysis. Springer Berlin Heidelberg, 2007: 337-349.

[12] Leskovec J. Stanford large network dataset collection [J]. URL http://snap. stanford. edu/data/index. html, 2011

Improved SpiderMine Algorithm Based on Cloud Computing in Big Graph Mining

Liu Ying, Du Yizhi, Zou Le
(Hefei University, Hefei 230060, China)

Abstract:The existing graph mining algorithms in a cloud environment are difficult to carry out mining the high frequent patterns of a massive graph .To solve this problem, this paper has made the improvement to the SpiderMine algorithm, and an improved SpiderMine algorithm is proposed based on the cloud(c-SpiderMine). Firstly, one big graph data is divided into several sub graphs by minimum cut algorithm to minimize partition/merge costs. And then it exploits SpiderMine to mine the patterns, which generates large patterns with much lower combinational complexity. Finally, a pattern key (PK) function is proposed to preserve the patterns, which guarantees that all patterns can be successfully recovered and merged. The experiments are conducted with three real data sets, and the experimental results demonstrate that c-SpiderMine can efficiently mine top-k large patterns in the cloud, and performs well in memory usage and execution time with different data sizes and minimum supports than the SpiderMine.

Key words:Graph Mining; Cloud Computing; Frequent Patterns; Minimum Cut Algorithm; Pattern Key Function; Execution Time

收稿日期：（2015.08.28）

作者簡(jiǎn)介：劉 瑩（1979-），女，合肥學(xué)院，助教，碩士，研究方向：云計(jì)算、大數(shù)據(jù)，合肥，230060杜奕智（1962-），男，合肥學(xué)院，副教授，碩士，研究方向：為云計(jì)算、大數(shù)據(jù)，合肥，230060 鄒 樂(lè)（1966-），男，合肥學(xué)院，講師，碩士，研究方向：云計(jì)算、大數(shù)據(jù)，合肥，230060

基金項(xiàng)目：合肥學(xué)院校級(jí)基金（14KY12ZR）

文章編號(hào)：1007-757X(2016)01-0033-05

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A