0 引言

　　圖挖掘問題[1-3]在移動互聯網、大數據處理等領域具有十分重要的應用價值，是目前的研究熱點。文獻[4]提出了一種基于共生頻繁項樹和逆矩陣的圖挖掘算法。文獻[5]中的SpiderMine算法采用概率挖掘理論來尋找前K個最大模式，通過將小規模高頻率模式融合為大規模模式，克服了算法瓶頸，效率較高。文獻[6]提出了一種自適應云端的大規模導出子圖提取算法，以解決資源優化利用與海量圖挖掘等問題。文獻[7]提出一種圖形挖掘系統OPAvion。然而，上述方法均無法進行云環境下大規模圖形的高頻率模式挖掘。為了解決以上問題，本文針對文獻[5]中的SpiderMine算法提出云環境下的新算法c-SpiderMine。c-SpiderMine包括分區、挖掘、融合3個階段。分區階段利用最小切割算法將大規模圖形數據分為多個子圖，使分區/融合成本最小。第2階段為挖掘階段，利用SpiderMine進行模式挖掘，利用約簡器可有效降低圖形同構測試的成本，顯著降低大型模式生成時的組合復雜度。更重要的是，本文構建一個全局表格以避免該階段出現不對稱信息，最后一個階段是模式融合。本文提出一種模式鍵(Pattern Key，PK)函數來保存模式，以保證所有模式可被成功恢復和融合。

1 問題描述

　　1.1 圖分割

　　將輸入的數據圖表示為G，將分割數據集表示為S。圖分割問題可定義如下：

　　定義1：已知圖形G=(V，E)，切邊集合C(Ec)，其中Ec將G分為多個分區{S1，S2，…，Sn}，且對任意i≠j有Ui Si=V。切邊集合Ec為頂點屬于不同分區的邊集合。

　　1.2 不對稱信息

　　基于經典的MapReduce[8]模型，本文在分區階段將圖形G分割為多個子圖S1，S2，…，Sn。在挖掘階段，需要挖掘初始時頻率較低的圖形模式，稱為spider，定義2中對此進行描述。

　　定義2：將半徑約束在r范圍內的高頻率模式稱為r-spider。用圖形的頭部表示每個spider，Spider的半徑為其節點的最小偏心率，因此，radius(spider)=min{e(v):v∈V(spider)}。

　　1.3 模式融合

　　在融合階段，將利用挖掘階段生成的spider生成全局高頻率模式。這一問題的簡單求解方法是發送spider然后對其融合。然而，如果在一臺機器上融合所有圖形，則將產生兩個問題。首先，約簡程序的存儲空間無法從所有映射程序中讀取所有的高頻率子圖，因為高頻率模式集合的數據規模大于原始的輸入圖形規模。其次，難以定義合適的融合鍵值。對鍵值做普通選擇會復制切割節點。然而，選擇這些節點作為鍵值會導致部分大規模模式無法被融合。

2 c-SpiderMine算法

　　圖1給出了本文方法的框架。

　　2.1 分割階段

　　本文采用最小切邊算法來進行圖分割。最小切邊集合概念見定義3。

　　定義3：已知圖形G(V，E)，其中V表示頂點結合，E表示邊緣集合，G(V，E)的最小切邊集合Ec(S，T)可將V分割為S且T=V-S，同時有s∈S，t∈T，且Ec(S，T)=Ec(u，v)的容量最小。

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

　　算法1：分割階段

　　要求：圖G=(V，E)

　　k：圖形分割數量

　　輸出：Gsub={g1，…，gk}，G被分割的子圖

　　1： Gsub←k-Partition(G，k)

　　2： for 每個gi，gj∈Gsub  do

　　3： Ec←{(vi，vj)|vi∈gi(V)，vj∈gj(V)}

　　//添加gi和gj中的切邊集合Ec

　　4： gi(E)←gi(E)∪Ec

　　//添加gi的切割節點集合Vc的連通邊緣

　　5： gi(E)←gi(E)∪{(vi，vj)|vi∈Ec|vj∈Ec∧i≠j}

　　6： 輸出所有子圖Gsub

　　2.2 挖掘階段

　　在挖掘階段的第1步，采用文獻[9]中提出的模式增長算法實現spider增長，以便在半徑約束內挖掘所有的高頻率圖形模式，它只需一個處理器就可獲得所有的初始spider。在該階段中，首先需要選擇一個節點作為初始模式。然后，算法利用與模式相連的邊來擴展模式，進而生成新的候選。算法還收集模式嵌入因子。如果嵌入因子數量低于支持閾值，則算法修剪候選。為了實現spider的并行增長，本文采用BSP模型來增長相同深度內不同子圖中的spider，即可以在同一超級步驟內生成邊緣和節點數量相同的所有高頻率spider候選。在挖掘階段的第2步中，通過構建一個全局表來維護每個spider候選的支持數。在同頻率圖形模式候選集合增長期間，通過Canonical forms[10]對候選模式進行編碼，將每個候選模式的本地支持量發送給全局表。然后，在超級步驟結束后修剪頻率較低的候選，并確保所有處理器均增加了候選的可能嵌入因子數。通過這種方法可以保證不會有模式由于信息不對稱而被修剪。挖掘階段的整個步驟見算法2。

　　算法2：MiningPhase（挖掘階段）

　　要求：Gsub：分割后的子圖

　　r：圖形半徑

　　最小支持閾值

　　輸出：〈Ec(Gid)，S′〉，Gsub中的切邊集合和高頻率圖形模式集合

　　Map(Key k，Value v)

　　1： Gid←k//鍵定義為子圖ID

　　2： Gsub←v//值定義為子圖數據

　　3： 利用標識頻率對Gsub中所有節點進行同步和排序

　　4： for all gi∈Gsub do

　　5： 修剪低頻率標識，重新標識gi的節點

　　6： 輸出〈Gid，Gsub〉

　　Reduce(Key k，Values v[])

　　1： Gid←k//鍵為子圖ID

　　2： Gsub←v//值為子圖數據

　　3： S1←Gsub中所有本地高頻率單邊圖形

　　4： for 每個s∈S1 do

　　5： supglobal(s)←CalculateSupport(s)

　　6： S∈S1；

　　7： if  S≠?覫 do

　　8：  for 每個s∈S  do

　　9：    if supglobal(s)<?茲且Radius(s)≠r then

　　10：S′←S-{s}

　　11：    else

　　12：S′←GrowPattern{s}

　　//生成候選圖形模式并更新supglobal

　　13：sync(s，supglobal)//BSP模型同步

　　14： 輸出〈Ec(Gid)，S′〉

　　2.3 融合階段

　　融合階段包括兩個MapReduce任務。第1個任務是將不同子圖中的spider擴展為更大規模的模式。為了解決融合問題，文中提出一種基于重疊的模式鍵(Pattern Key，PK)函數。鍵(key)定義為每個高頻率圖形模式候選的哈希碼，值(value)定義為候選spider每個子圖中嵌入因子數的支持數之和。PK函數的作用在于保留初始關系，提供兩個子圖間的關聯。PK函數的定義見定義4。

　　定義4：已知一個子圖g(V，E)，其中V表示節點集合，E表示邊集，Vc表示復制節點集。將切割節點vc∈Vc的重疊切割節點集定義。

　　第2個任務稱為模式修剪任務，內容是當兩個模式同形時修剪掉重復的模式。模式修剪任務之后，可以計算每個模式的支持數。最后，將所有模式發送給模式融合任務。因為本文已經在先前的任務中修剪掉了低頻率模式并進行了同構測試，所以通過檢查兩個模式是否擁有相同的PK來進行模式融合。如果兩個模式的PK相同，則通過該相同的spider對其融合。重復這一步驟，直到新生成的模式的直徑超出直徑界限為止。限于篇幅，融合階段的詳細步驟在此略去。

3 仿真實驗

　　3.1 實驗環境

　　本文在33個虛擬機構成的云計算環境下，將c-SpiderMine部署于HAMA 0.5和Hadoop 1.0.3上，其中一個節點作為主節點，其余節點均作為從屬節點。所有實驗運行于256 GB內存和1 GB以太網英特爾Xeon服務器平臺上。

　　3.2 與SpiderMine的比較

　　為了證明c-SpiderMine的有效性，選擇SpiderMine作為基準算法來比較節點數量不同時的運行時間，最小支持數不同時的運行時間及內存使用情況。從網站上選擇兩種大型數據集[11]進行測試，如圖2(a)所示，當節點規模變大時運行時間上升，在該圖中，可以發現當數據規模大于20 000時，SpiderMine難以為圖形提供支持，相反，當數據規模增大時，c-SpiderMine的性能較優。圖2(b)表明即使最小支持數較低，c-SpiderMine在運行時間方面的性能仍優于SpiderMine。此外，可以發現當最少支持數低于0.82%時，c-SpiderMine優于SpiderMine。總體來說，本文c-SpiderMine方法在處理大規模圖形數據時顯示出了良好的運行時間性能，降低了內存使用量，且效率高于SpiderMine。

　　3.3 伸縮性

　　(1)最小支持設置的影響：下面分別在圖3(a)和3(b)中給出com-DBLP和Amazone0302的運行時間。兩組實驗的最小支持設置范圍為0.01%-0.035%，節點規模分別為40 000、70 000和100 000。結果表明，當最小支持設置增加時，運行時間下降。這表明，當最小支持設置增加時，生成的模式數量變小，運行時間降低。此外，當N增加時，運行時間同步增加，明顯表明有更多的節點生成更多的模式，消耗更多的時間。實驗表明，當節點規模和最小支持數增加時，c-SpiderMine在運行時間方面具有良好的伸縮性。

　　(2)機器數量的影響：本節研究了機器數量不同時的性能。驗證c-SpiderMine的性能時，對com-DBLP數據集使用4、8、16和32臺機器，最小支持設置為0.25%、0.35%和0.4%，對Amazone0302數據集使用2、4、8、16和32臺機器，最小支持設置為0.2%、0.28%和0.35%。在圖4(a)和4(b)中，當機器數量上升時運行時間呈指數下降。結果表明，機器數量增加可提高性能和效率，這進一步證明云計算可直接提高大規模圖形數據挖掘的伸縮性。

4 結論

　　本文提出了c-SpiderMine算法，在處理大規模圖形數據時有效融合了BSP模型、SpiderMine和云計算。實驗結果表明，在不同數據規模和最小支持設置條件下，c-SpiderMine在內存使用和運行時間方面的性能均優于SpiderMine。文中還證明了c-SpiderMine在不同的最小支持設置和機器數量條件下，具有良好的伸縮性。在下一步工作中，可結合更多的真實大型數據集對本文方法展開研究。

參考文獻

　　[1] 孫鶴立，陳強，劉瑋，等.利用MapReduce平臺實現高效并行的頻繁子圖挖掘[J].計算機科學與探索，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].Proceedingsof the ACM ASONAM，2013，13：25-28.

　　[4] 李濤，肖南峰.基于共生頻繁項樹和逆矩陣的圖挖掘[J].計算機應用研究，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] 郭鑫，董堅峰，周清平.自適應云端的大規模導出子圖提取算法[J].計算機科學，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 2012ACM SIGMOD International Conference on Management of Data.ACM，2012：717-720.

　　[8] SARMA A D，AFRATI F N，SALIHOGLU S，et al.Upper and lower bounds on the cost of a map-reduce computa-tion[C].Proceedings of the VLDB Endowment. VLDB Endowment，2013，6(4)：277-288.

　　[9] 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：frequentpattern mining implementations.ACM，2005：6-15.

　　[10] BORGELT C.Canonical forms for frequent graph mining[M].Advances in Data Analysis，Springer Berlin Heidelberg，2007：337-349.

　　[11] LESKOVEC J.Stanford large network dataset collection[J].URL http：//snap.stanford.edu/data/index.html，2011.