Spark環(huán)境下基于頻繁邊的大規(guī)模單圖采樣算法

李龍洋 董一鴻 嚴(yán)玉良 陳華輝 錢(qián)江波

(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江寧波 315211)

Spark環(huán)境下基于頻繁邊的大規(guī)模單圖采樣算法

李龍洋 董一鴻 嚴(yán)玉良 陳華輝 錢(qián)江波

(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江寧波 315211)

(sgavin1991@163.com)

隨著社交網(wǎng)絡(luò)的流行，對(duì)其進(jìn)行頻繁子圖挖掘的需求越來(lái)越強(qiáng)烈.大數(shù)據(jù)時(shí)代的到來(lái)，社交網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，頻繁子圖挖掘工作變得愈發(fā)困難.在實(shí)際應(yīng)用中，往往并不需要精確地挖掘出頻繁子圖，采樣的方法在保證一定準(zhǔn)確率的前提下能夠顯著提高頻繁子圖挖掘的效率.現(xiàn)有采樣算法大多是根據(jù)節(jié)點(diǎn)的度進(jìn)行采樣，不適用于頻繁子圖挖掘.提出了一種基于頻繁邊的采樣算法DIMSARI(distributed Monte Carlo sampling algorithm based on random jump and graph induction)，在蒙特卡羅算法的基礎(chǔ)上增加了根據(jù)頻繁邊進(jìn)行隨機(jī)跳的操作，并對(duì)其結(jié)果進(jìn)行了圖感應(yīng)操作，進(jìn)一步增加了算法的準(zhǔn)確性，并在理論上證明了該方法的無(wú)偏性.實(shí)驗(yàn)結(jié)果顯示:使用DIMSARI算法采樣后進(jìn)行頻繁子圖挖掘，準(zhǔn)確性比現(xiàn)有其他的采樣算法有較大的提高，在不同的采樣率下采樣后的子圖的節(jié)點(diǎn)度都保持更小的歸一化均方偏差.

采樣；頻繁子圖；大規(guī)模單圖；頻繁邊；Spark

現(xiàn)實(shí)生活中，人與人、人與物之間的關(guān)系可以用圖的形式來(lái)表示，節(jié)點(diǎn)表示實(shí)體對(duì)象，邊表示實(shí)體對(duì)象之間的關(guān)系.社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)等規(guī)模不斷擴(kuò)大，結(jié)構(gòu)復(fù)雜.例如，作為全球最流行的社交平臺(tái)，截至2015年6月，F(xiàn)acebook的單日活躍用戶數(shù)量為9.68億[1]，大部分圖挖掘算法復(fù)雜度較高，對(duì)于這樣的社交網(wǎng)絡(luò)進(jìn)行子圖同構(gòu)、頻繁子圖挖掘都屬于NP難問(wèn)題.特別在當(dāng)前大數(shù)據(jù)背景下，大規(guī)模單圖(指連通圖)的頻繁子圖挖掘算法的運(yùn)行時(shí)間較久，尤其在支持度較低的情況下無(wú)法解決.在實(shí)際頻繁子圖挖掘以及子圖同構(gòu)等圖操作中，并不需要精確地得到原始連通圖的頻繁子圖個(gè)數(shù)或子圖同構(gòu)個(gè)數(shù)等，故對(duì)原始連通圖進(jìn)行采樣后進(jìn)行頻繁子圖挖掘，雖然在一定程度上降低了挖掘的準(zhǔn)確性，但可以顯著地提高頻繁子圖挖掘的效率，在保證一定準(zhǔn)確率的前提下對(duì)原始圖進(jìn)行采樣[2]是解決大規(guī)模圖中頻繁子圖挖掘的有效手段.

傳統(tǒng)的采樣方法主要是根據(jù)節(jié)點(diǎn)的度轉(zhuǎn)移進(jìn)行采樣，且偏于度比較高的節(jié)點(diǎn)，不適用于頻繁子圖挖掘.為了更好地完成頻繁子圖挖掘的任務(wù)，本文提出了一種基于隨機(jī)跳和圖感應(yīng)的蒙特卡羅采樣算法(Monte Carlo sampling algorithm based on random jump and graph induction, MSARI)，并將其擴(kuò)展到Spark平臺(tái)下DIMSARI(distributed Monte Carlo sampling algorithm based on random jump and graph induction)算法，以處理大規(guī)模單圖.首先，根據(jù)頻繁邊的分布使用蒙特卡羅算法進(jìn)行圖采樣.為了降低頻繁邊的方差，采樣過(guò)程中對(duì)當(dāng)前邊和將要跳轉(zhuǎn)邊進(jìn)行頻繁度比較，如果跳轉(zhuǎn)邊的頻繁度小于當(dāng)前邊的頻繁度，則跳轉(zhuǎn)，否則停留在原處.最后進(jìn)行圖感應(yīng)操作，將采樣過(guò)程中丟失的子圖邊進(jìn)行補(bǔ)全，增加算法的有效性.

本文的主要貢獻(xiàn)如下：1)傳統(tǒng)的采樣算法多是根據(jù)節(jié)點(diǎn)擴(kuò)展，本文則根據(jù)頻繁邊的分布進(jìn)行蒙特卡羅采樣，并在其基礎(chǔ)上增加了隨機(jī)跳轉(zhuǎn)和圖感應(yīng)操作，提出MSARI算法，并擴(kuò)展到Spark平臺(tái)下的DIMSARI算法.將采樣后的結(jié)果使用在頻繁子圖挖掘中，提高了頻繁子圖挖掘算法的效率.2)對(duì)比實(shí)驗(yàn)顯示，在相同的采樣率下DIMSARI算法采樣后的子圖進(jìn)行頻繁子圖挖掘具有更高的準(zhǔn)確率，在相同的準(zhǔn)確率下該算法采樣量更少，且采樣后的子圖結(jié)構(gòu)與原始圖更相似.

1 相關(guān)工作

圖采樣算法分為基礎(chǔ)采樣、隨機(jī)游走采樣、蒙特卡羅采樣和基于拓?fù)浣Y(jié)構(gòu)的采樣.

基礎(chǔ)采樣算法包括隨機(jī)邊采樣[3]和隨機(jī)節(jié)點(diǎn)采樣[3].隨機(jī)節(jié)點(diǎn)采樣均勻地對(duì)節(jié)點(diǎn)進(jìn)行采樣，無(wú)法保持冪率性；而隨機(jī)邊采樣則是隨機(jī)均勻地選擇邊，得到的邊的結(jié)果非常稀疏無(wú)法保持較大的直徑.2011年Ahmed等人[4]在隨機(jī)邊采樣基礎(chǔ)上加入了圖感應(yīng)技術(shù)；2014年Blagus等人[5]對(duì)圖感應(yīng)算法進(jìn)行了擴(kuò)展，證明了圖感應(yīng)算法可以增加算法的準(zhǔn)確性.然而，由于基礎(chǔ)采樣算法本身的隨機(jī)性，即使增加圖感應(yīng)操作也無(wú)法達(dá)到較高的精度.

隨機(jī)游走采樣算法包含RW[6](random walk)，F(xiàn)F[7](forest fire)，RJ[7](random jump)，BFS[8](breadth first search)，1996年Lovász等人[6]提出隨機(jī)游走(RW)算法，以初始節(jié)點(diǎn)的鄰接節(jié)點(diǎn)進(jìn)行擴(kuò)展采樣.2005年Leskovec等人[7]提出了森林火災(zāi)模型(FF)和隨機(jī)跳(RJ)算法，F(xiàn)F算法隨機(jī)生成一個(gè)種子節(jié)點(diǎn)，擴(kuò)展的過(guò)程中以閾值來(lái)控制采樣，該方法會(huì)陷入局部區(qū)域，且偏向于度較高的節(jié)點(diǎn).RJ算法以修正的概率跳轉(zhuǎn)到原始圖的任一節(jié)點(diǎn)，有效避免陷入局部區(qū)域.2007年Ahn等人[8]提出BFS算法，該算法是廣度搜索的采樣方式.隨機(jī)游走算法以初始節(jié)點(diǎn)的鄰接節(jié)點(diǎn)擴(kuò)展采樣，一定程度上增加了采樣的有效性，但采樣結(jié)果容易陷入局部區(qū)域，且有偏向度較高的節(jié)點(diǎn)，不能很好地保持原始連通圖的結(jié)構(gòu).

蒙特卡羅采樣算法主要是利用蒙特卡羅模型來(lái)進(jìn)行采樣，2011年Gjoka等人[9]提出的蒙特卡羅散列隨機(jī)游走算法使用了蒙特卡羅算法通過(guò)對(duì)Facebook數(shù)據(jù)集的驗(yàn)證，2011年Long等人[10]對(duì)其增加了隨機(jī)跳的改進(jìn)，這2種算法偏向度比較高的節(jié)點(diǎn)，不適用于采樣后進(jìn)行頻繁子圖挖掘.

基于拓?fù)浣Y(jié)構(gòu)的采樣算法主要是利用原始圖的拓?fù)浣Y(jié)構(gòu)進(jìn)行采樣.2011年Yoon等人[11]提出了基于社區(qū)劃分的圖采樣算法，2014年Du等人[12]根據(jù)圖的拓?fù)浞謱有畔⑦M(jìn)行采樣，以直徑上的任一點(diǎn)為初始節(jié)點(diǎn)，根據(jù)與該初始節(jié)點(diǎn)的距離進(jìn)行采樣.2015年Rezvanian等人[13]以最短路徑上的點(diǎn)為初始節(jié)點(diǎn)開(kāi)始采樣.Jalali等人[14]提出了基于生成樹(shù)的社交網(wǎng)絡(luò)采樣算法，首先隨機(jī)選擇一些節(jié)點(diǎn)作為種子節(jié)點(diǎn)，根據(jù)這些種子節(jié)點(diǎn)生成多個(gè)生成樹(shù)，選擇頻繁度較高的邊作為采樣邊.基于拓?fù)浣Y(jié)構(gòu)的采樣算法雖然在一定程度上增加了采樣的精確度，但是時(shí)空復(fù)雜度過(guò)高，只適合小規(guī)模的圖或圖集，當(dāng)處理大規(guī)模單圖時(shí)則時(shí)空開(kāi)銷(xiāo)大，無(wú)法有效處理.

2 基本概念

定義1. 子圖同構(gòu)[15].給定圖G=(V,E,L)，G′=(V′,E′,L′)，V,V′表示節(jié)點(diǎn)集合，E,E′表示邊集合以及L,L′表示節(jié)點(diǎn)和邊的標(biāo)簽映射函數(shù).如果G與G′存在這樣的映射函數(shù)f:V→V′，滿足：1)u∈V，L(u)=L′(f(u))；2)(u，v)∈E，(f(u)，f(v))∈E′且L(u，v)=L′(f(u)，f(v))，則稱G與G′為子圖同構(gòu).

定義2. 頻繁子圖[16].給定圖G和最小支持度MinSupport，Sup(G,S)表示子圖S在圖G中同構(gòu)圖的個(gè)數(shù),當(dāng)Sup(G,S)>MinSupport，S為G的一個(gè)頻繁子圖.

給定圖G和最小支持度MinSupport，從圖G中找出支持度大于MinSupport的所有子圖的過(guò)程稱為頻繁子圖挖掘.

在圖1中，共存在9個(gè)子圖:A-2-B,B-1-C,B-3-C,A-2-B-1-C,A-2-B-3-C,B-1-C-3-B,A-2-B-1-C-3-B,A-2-B-3-C-1-B,A-2-B-1-C-3-B-2-A,支持度分別為：2,1,1,1,1,1,1,1,1.當(dāng)最小支持度為1時(shí)，共有9個(gè)頻繁子圖；當(dāng)最小支持度為2時(shí)，共有1個(gè)頻繁子圖；當(dāng)最小支持度為3時(shí)，則沒(méi)有頻繁子圖.

Fig. 1 The example of frequent subgraph圖1 頻繁子圖挖掘樣例圖

定義3. 頻繁邊及其方差.給定一個(gè)邊eu，且給定最小支持度MinSupport，當(dāng)且僅當(dāng)eu的支持度不小于最小支持度閾值時(shí)稱邊eu為頻繁邊，將頻繁邊的頻繁度的方差定義為頻繁邊方差，在頻繁子圖挖掘過(guò)程中，當(dāng)頻繁邊方差越大，圖中頻繁邊的分布越不均勻，最終挖掘時(shí)間越長(zhǎng).

定義4. 邊聚集系數(shù).1條邊的2個(gè)端點(diǎn)與其共同鄰接點(diǎn)之間的另外2邊所組成的三角環(huán)(邊數(shù)為3的閉合回路)與可能包含該邊的最大的三角環(huán)數(shù)之間的比值，公式如下：

(1)

其中，ki,kj分別表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的度，Zij表示網(wǎng)絡(luò)中實(shí)際包含該邊的三角環(huán)的個(gè)數(shù).

3 基于頻繁邊的圖采樣

3.1 內(nèi)存分布式計(jì)算框架——Spark

Spark[17]是UC Berkeley AMP Lab開(kāi)源的類(lèi)Hadoop通用的并行計(jì)算框架，Spark基于Hadoop MapReduce算法實(shí)現(xiàn)分布式計(jì)算，擁有Hadoop所具有的優(yōu)點(diǎn)；但不同于Hadoop將Job中間輸出和結(jié)果保存在HDFS，而將其直接保存在內(nèi)存中，且Spark啟用了彈性分布式數(shù)據(jù)集，除了能夠提供交互式查詢外，它還可以優(yōu)化迭代工作負(fù)載.因此Spark能更好地適用于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)等需要迭代的MapReduce的算法.其架構(gòu)如圖2所示：

Fig. 2 The framework of Spark圖2 Spark架構(gòu)

3.2 基于頻繁邊的分布式圖采樣算法

在進(jìn)行頻繁子圖挖掘時(shí)，頻繁邊的分布相對(duì)于節(jié)點(diǎn)的度更為重要，本文提出了基于隨機(jī)跳和圖感應(yīng)的蒙特卡羅采樣方法MSARI，首先根據(jù)頻繁邊的分布進(jìn)行圖采樣.采樣中增加隨機(jī)跳轉(zhuǎn)，在滿足隨機(jī)跳轉(zhuǎn)概率后，對(duì)當(dāng)前邊和將要跳轉(zhuǎn)邊進(jìn)行頻繁度比較，當(dāng)跳轉(zhuǎn)邊的頻繁度小于當(dāng)前邊的頻繁度，則跳轉(zhuǎn).從邊eu跳轉(zhuǎn)到邊ev的概率如式(2)所示：

(2)

式(2)表示MSARI算法轉(zhuǎn)移概率，蒙特卡洛算法根據(jù)節(jié)點(diǎn)的度轉(zhuǎn)移，在采樣的過(guò)程中對(duì)節(jié)點(diǎn)無(wú)偏性，跳轉(zhuǎn)到各節(jié)點(diǎn)概率都滿足1|V|，而MSARI算法根據(jù)邊的頻繁度進(jìn)行轉(zhuǎn)移，在采樣的過(guò)程中按照頻繁邊進(jìn)行采樣，ev代表當(dāng)前的采樣邊，eu代表將要擴(kuò)展的采樣邊，且eu為ev的相鄰邊，f代表邊的頻繁度，當(dāng)滿足跳轉(zhuǎn)概率后，對(duì)eu和ev的頻繁度進(jìn)行判斷.當(dāng)random(0,1)

最后，為了增加采樣后的子圖的連通性，提升采樣后頻繁子圖的召回率，在初步采樣結(jié)束之后進(jìn)行圖感應(yīng)處理，采樣后對(duì)原始圖進(jìn)行遍歷，如果采樣后子圖的邊的2個(gè)節(jié)點(diǎn)都被采樣且原始圖有邊相連而采樣后沒(méi)有邊相連，則將其邊添加到子圖上以增加子圖的連通性.

Fig. 3 The demo of graph induced operation圖3 圖感應(yīng)操作演示

MSARI算法偽代碼如下：

算法1. MSARI采樣算法.

輸入：待采樣的圖G、采樣率R、隨機(jī)跳轉(zhuǎn)的概率p;

輸出：采樣之后的邊sampleEdge.

①sampleCount=r×G.vertexs；*得到采樣的數(shù)量*

②ev=random(G.edge)；*從原圖的節(jié)點(diǎn) 中隨機(jī)取一條邊*

③sampleSet=Set(ev)；*采樣后的集合*

④ whilesampleVertex.size

⑤ ifrandom(0,1)

⑥eu=random(G.edge)；*原圖的節(jié) 點(diǎn)中隨機(jī)取一條邊*

⑦ ifrandom(0,1)

⑧ev=eu；

⑨SampleSet.add(eu)；*將eu添加到采樣集合中*

⑩ end if

為了處理大規(guī)模單圖，本文將MSARI算法擴(kuò)展為分布式環(huán)境下的DIMSARI算法，由于需要多次迭代處理，Hadoop的MapReduce操作需要多次讀取HDFS上的文件，時(shí)間開(kāi)銷(xiāo)大，并不適用，而Spark的RDD操作可以滿足多次迭代要求，因此，實(shí)驗(yàn)使用的分布式平臺(tái)為Spark，Partition是Spark的分區(qū).DIMSARI算法步驟如下：

1) 使用節(jié)點(diǎn)分割策略進(jìn)行原圖的劃分，將其劃分為多個(gè)分區(qū)；

2) 在各自的分區(qū)上完成MSARI算法的采樣工作；

3) 在各自分區(qū)采樣完成的采樣圖的基礎(chǔ)上進(jìn)行圖感應(yīng)操作，增加連通性；

4) 將各自分區(qū)采樣完成的采樣圖進(jìn)行合并，形成單個(gè)采樣圖.

算法2. DIMSARI采樣算法.

輸入：待采樣的圖G、采樣率r、隨機(jī)跳轉(zhuǎn)概率p；

輸出：采樣完成后子圖Gsub.

①edgeFreqMap=getFrequentEdgeMap(G)；*獲取邊的頻繁度*

②sampleEdgeRdd=G.partitionBy(EdgePartition2D).map(edge(edge-FreqMap)).mapPartition{iter≥MSARI(iter,r,p)}；*進(jìn)行各個(gè)分區(qū)的MSARI采樣*

③ returnnewGraph(SampleEdgeRdd).*返回采樣后的圖*

算法2中，行①對(duì)原始圖進(jìn)行過(guò)濾并獲取邊的頻繁度;行②使用Graphx中的EdgePartition2D對(duì)原始圖進(jìn)行劃分，根據(jù)邊的頻繁度獲取圖信息，并對(duì)每一個(gè)分區(qū)進(jìn)行MSARI算法操作，得到各個(gè)分區(qū)結(jié)果;最后將總結(jié)果返回.

3.3 無(wú)偏性分析

MSARI算法在采樣的過(guò)程中每一步只與當(dāng)前邊和其將要轉(zhuǎn)移的邊有關(guān)，因此，MSARI采樣算法的過(guò)程可以抽象成一個(gè)Markov過(guò)程.其中，采樣到的邊eu為Markov過(guò)程的狀態(tài)eu，從邊eu到邊ev的概率Pe u,ev表示為Markov過(guò)程的狀態(tài)轉(zhuǎn)移概率Pe u,ev.在時(shí)間T采樣到邊eu的概率等價(jià)于Markov過(guò)程中狀態(tài)eu在時(shí)間T的狀態(tài)分布.如果該Markov過(guò)程屬于平穩(wěn)分布，則當(dāng)采樣時(shí)間足夠長(zhǎng)，該Markov過(guò)程的狀態(tài)分布將收斂至特定的平穩(wěn)分布π=(πe 1,πe 2,…,πe |E|)T，其中|E|為原始圖的邊的個(gè)數(shù).此概率分布π對(duì)應(yīng)著采樣算法對(duì)網(wǎng)絡(luò)每條邊的采樣概率.當(dāng)π服從均勻分布時(shí)，即πe 1=πe 2=…=πe |E|,該采樣算法則是無(wú)偏的.

引理1. 如果原始連通圖包含至少1個(gè)聚集系數(shù)不為0的邊，且對(duì)任意2條邊eu,ev，都有P{Pe v,eu>0|Pe u,ev>0}=1，則該原始圖抽象出的Markov過(guò)程是遍歷不可分的.

Fig. 4 An example of Markov chain abstracted from sampling process圖4 采樣過(guò)程中抽象出的Markov鏈?zhǔn)纠?/p>

可以看出，邊i-a-j可以至多|E|-3步就可以到達(dá)圖中任意邊，即邊i-a-j可以通過(guò)|E|-3-2n或|E|-3-2n-1次轉(zhuǎn)移到達(dá)圖中任意邊，其中n表示一個(gè)非負(fù)整數(shù).設(shè)he a,eb表示從邊i-a-j到邊m-b-n的最短轉(zhuǎn)移次數(shù).如果he a,eb=|E|-3-2n，邊i-a-j可以在he a,eb步的基礎(chǔ)上經(jīng)過(guò)n+1個(gè)2跳回環(huán)i-a-j→i-c-k→i-a-j到達(dá)邊m-b-n，即可以通過(guò)|E|-1步從邊i-a-j轉(zhuǎn)移到邊m-b-n；當(dāng)he a,eb=|E|-3-2n-1，邊i-a-j可以在he a,eb步的基礎(chǔ)上經(jīng)過(guò)n個(gè)2跳回環(huán)i-a-j→i-c-k→i-a-j和一個(gè)3跳回環(huán)i-a-j→i-c-k→k-d-l→i-a-j到達(dá)邊m-b-n,即可以通過(guò)|E|-1步從邊i-a-j轉(zhuǎn)移到邊m-b-n.

因此，必有正整數(shù)N=2(|E|-1)使得從圖4中的任一邊出發(fā)，經(jīng)過(guò)N步到達(dá)其他任意邊(以邊i-a-j為中轉(zhuǎn)邊).即對(duì)于從圖4中抽象出的Markov鏈，存在正整數(shù)N≥1，使得該Markov鏈中任意2個(gè)邊ea，ec，有Pe a,ec(n)≥0.這是Markov過(guò)程遍歷不可分的充分必要條件[18],所以引理1得證.

證畢.

證明. 1) 必要性.設(shè)定一個(gè)平穩(wěn)的Markov過(guò)程的狀態(tài)轉(zhuǎn)移概率矩陣P為

則該Markov過(guò)程的平穩(wěn)分布π為

π=(πe 1,πe 2,…,πe |E|)T,

狀態(tài)轉(zhuǎn)移矩陣P和平穩(wěn)分布π滿足式(3)：

(3)

在采樣過(guò)程中，πe u表示在采樣過(guò)程中邊eu的采樣概率，即對(duì)于無(wú)偏采樣，?eu,ev∈E,有πe u=πe v=1|E|，代入式(3)中可得：

(4)

2) 充分性.根據(jù)引理1，如果原始圖中至少存在一個(gè)聚集系數(shù)不為0的邊，在該網(wǎng)絡(luò)中進(jìn)行隨機(jī)游走的采樣過(guò)程可以抽象為一個(gè)遍歷不可分的Markov過(guò)程.因此，該Markov過(guò)程是一個(gè)平穩(wěn)過(guò)程且式(3)有且只有唯一解.可以得出πe u=πe v=1|E|是式(3)的一組解，綜上所述，該解為方程組的唯一解,即該采樣算法在采樣時(shí)間足夠長(zhǎng)時(shí)對(duì)每一個(gè)節(jié)點(diǎn)的采樣概率相等.

證畢.

證明. 1) 必要性.在節(jié)點(diǎn)i上，設(shè)定一個(gè)平穩(wěn)的Markov過(guò)程的狀態(tài)轉(zhuǎn)移概率矩陣Pi為

則該Markov過(guò)程的平穩(wěn)分布πi為

πi=(πe 1,πe 2,…,πe |Ei|)T.

狀態(tài)轉(zhuǎn)移矩陣Pi和平穩(wěn)分布πi滿足方程組：

(5)

在采樣過(guò)程中，πe i表示在采樣過(guò)程中邊ei的采樣概率，對(duì)于無(wú)偏采樣，?ei,ej∈E,有πe i=πe j，代入式(5)可得：

(6)

根據(jù)式(6)可得：

(7)

2) 充分性.根據(jù)引理1，如果原始圖中至少存在一個(gè)聚集系數(shù)不為0的邊，則整個(gè)采樣過(guò)程可以抽象為一個(gè)遍歷不可分的Markov過(guò)程.因此，該Markov過(guò)程是一個(gè)平穩(wěn)過(guò)程且式(5)有且只有唯一解，而πe u=πe v=1|E|是其中一個(gè)解，因此πe u=πe v=1|E|就是唯一解，即該采樣算法在采樣時(shí)間足夠長(zhǎng)時(shí)對(duì)每一個(gè)節(jié)點(diǎn)的采樣概率相等.

證畢.

因此，該采樣方法在分布式環(huán)境下具有無(wú)偏性.

3.4 頻繁子圖挖掘算法—FSMBUS

針對(duì)現(xiàn)有圖的規(guī)模不斷擴(kuò)大，使用完整圖用于頻繁子圖的挖掘時(shí)間和空間復(fù)雜度過(guò)高，使用DIMSARI算法采樣后進(jìn)行頻繁子圖挖掘，在保證準(zhǔn)確率的前提下大大減少了算法的運(yùn)行時(shí)間和空間復(fù)雜度.本文使用文獻(xiàn)[19]的FSMBUS算法對(duì)采樣后的子圖和原始圖分別進(jìn)行頻繁子圖挖掘，通過(guò)對(duì)頻繁子圖F1值和NMSE比較，分析算法的有效性.

2015年嚴(yán)玉良等人[19]提出的基于Spark的大規(guī)模單圖頻繁子圖挖掘算法FSMBUS，通過(guò)次優(yōu)樹(shù)構(gòu)建并行計(jì)算的候選子圖，在給定最小支持度后挖掘出所有滿足條件的頻繁子圖，并利用非頻繁檢測(cè)和搜索順序選擇進(jìn)行優(yōu)化，并設(shè)計(jì)了一種名為Sorted-Greedy的輕量級(jí)數(shù)據(jù)劃分方法.FSMBUS算法的主題框架包括數(shù)據(jù)準(zhǔn)備階段和挖掘階段，挖掘階段是算法的核心部分，將次優(yōu)樹(shù)按照廣度優(yōu)先搜索進(jìn)行生長(zhǎng)，并行計(jì)算每一層中CAM所表示的候選子圖是否頻繁，將不頻繁的候選子圖進(jìn)行剪枝操作，剩余的候選子圖繼續(xù)生長(zhǎng)，進(jìn)入下一次迭代，直到候選子圖都為非頻繁子圖算法停止.

3.4.1 數(shù)據(jù)準(zhǔn)備階段

數(shù)據(jù)準(zhǔn)備階段主要是進(jìn)行頻繁邊的收集以及頻繁子圖數(shù)據(jù)集的初始化的工作.

當(dāng)原始圖輸入到算法中時(shí)，根據(jù)最小支持度過(guò)濾非頻繁邊，將過(guò)濾后的邊按照三元組(起始標(biāo)簽，邊標(biāo)簽，目標(biāo)標(biāo)簽)進(jìn)行存儲(chǔ)，將其作為次優(yōu)樹(shù)的第1層的頻繁子圖，同時(shí)使用頻繁邊RDD存儲(chǔ)頻繁邊兩邊的節(jié)點(diǎn)集合，頻繁邊RDD作為擴(kuò)展邊的緩存.

3.4.2 挖掘階段

挖掘階段主要通過(guò)迭代的方式將所有的頻繁子圖計(jì)算出來(lái)，包括候選子圖的生成、構(gòu)建候選搜索數(shù)據(jù)域以及支持度的計(jì)算.

1) 候選子圖的生成.第i次迭代由第i-1次迭代產(chǎn)生的頻繁子圖進(jìn)行FFSM-Join和FFSM-Extend后產(chǎn)生候選子圖.

2) 構(gòu)建候選搜索數(shù)據(jù)域.使用增量的方式獲取對(duì)應(yīng)的搜索數(shù)據(jù)域，每個(gè)候選子圖包含了父節(jié)點(diǎn)信息以及擴(kuò)展邊信息，當(dāng)前候選子圖的搜索數(shù)據(jù)域?yàn)楦讣?jí)子圖的有效分配數(shù)據(jù)連接擴(kuò)展邊對(duì)應(yīng)的有效分配數(shù)據(jù).

3) 支持度的計(jì)算.對(duì)候選搜索數(shù)據(jù)域進(jìn)行支持度的計(jì)算，采用啟發(fā)式算法來(lái)進(jìn)行搜索.

3.5 復(fù)雜度分析

原始圖的節(jié)點(diǎn)個(gè)數(shù)為N，采樣率為r.首先，使用蒙特卡羅算法進(jìn)行采樣，時(shí)間復(fù)雜度為O(r×N)；然后，在蒙特卡羅算法的基礎(chǔ)上增加了隨機(jī)跳概率p，因此，時(shí)間復(fù)雜度變?yōu)閜×O(r×N)+(1-p)×O(r×N)；最后，增加了圖感應(yīng)操作，需要遍歷原始圖，找出采樣后的子圖丟失邊，時(shí)間復(fù)雜度為O(N),因此總的時(shí)間復(fù)雜度為p×O(r×N)+(1-p)×O(r×N)+O(N)，對(duì)采樣后的子圖進(jìn)行頻繁子圖挖掘的時(shí)間復(fù)雜度在文獻(xiàn)[19]中已經(jīng)給出為O((n-2)×N3+n×τη×((1-θ)×N)n-1)，因此總的時(shí)間復(fù)雜度為O(r×N)+O(N)+O((n-2)×N3+n×τη×((1-θ)×N)n-1).

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用普通PC機(jī)22臺(tái)，其中1臺(tái)主節(jié)點(diǎn)，剩余21臺(tái)為從節(jié)點(diǎn).每臺(tái)PC機(jī)的配置相同：操作系統(tǒng)為Centos 6.5，CPU為Intel Core i5 2.4 GHz，8 GB內(nèi)存，使用Scala 2.10.4開(kāi)發(fā)，集群環(huán)境為建立在Hadoop2.2.0之上的Spark 1.2.0，jdk版本為1.7.

4.1 數(shù)據(jù)集和對(duì)比算法

實(shí)驗(yàn)數(shù)據(jù)集來(lái)自真實(shí)數(shù)據(jù)集SNAP[20]，如表1所示：

Table 1 The Description of Dataset

表1中，描述信息和相關(guān)處理如下：

1) DBLP(digital bibliography & library project).DBLP是計(jì)算機(jī)領(lǐng)域內(nèi)對(duì)研究的成果以作者為核心的一個(gè)計(jì)算機(jī)類(lèi)英文文獻(xiàn)的集成數(shù)據(jù)庫(kù)系統(tǒng)，按年代列出了作者的科研成果，包括國(guó)際期刊和會(huì)議等公開(kāi)發(fā)表的論文.節(jié)點(diǎn)表示作者，節(jié)點(diǎn)的標(biāo)簽表示其所在的學(xué)術(shù)領(lǐng)域，邊的標(biāo)簽為其作者之間的合作次數(shù)，為冪率分布數(shù)據(jù)集.

2) Amazon.亞馬遜商城上商品信息，節(jié)點(diǎn)表示商品，邊i-j表示購(gòu)買(mǎi)商品i的同時(shí)購(gòu)買(mǎi)商品j，節(jié)點(diǎn)標(biāo)簽表示商品ID，邊標(biāo)簽表示商品被同時(shí)購(gòu)買(mǎi)的次數(shù).由于原始數(shù)據(jù)集上并不含有節(jié)點(diǎn)和邊的標(biāo)簽，因此隨機(jī)地對(duì)節(jié)點(diǎn)和邊進(jìn)行標(biāo)簽的添加，標(biāo)簽分布服從高斯分布，節(jié)點(diǎn)和邊標(biāo)簽分別為5個(gè)和10個(gè)，為非冪率分布數(shù)據(jù)集.

3) LiveJournal.來(lái)自于LiveJournal社交網(wǎng)絡(luò)，節(jié)點(diǎn)表示用戶，標(biāo)簽表示用戶ID，邊表示用戶之間有關(guān)系，標(biāo)簽表示用戶之間的關(guān)系.由于原始數(shù)據(jù)集上并不含有節(jié)點(diǎn)和邊的標(biāo)簽，因此隨機(jī)地對(duì)節(jié)點(diǎn)和邊進(jìn)行標(biāo)簽的添加，標(biāo)簽分布服從高斯分布，節(jié)點(diǎn)和邊標(biāo)簽分別為50個(gè)和5個(gè)，為冪率分布數(shù)據(jù)集.

4) YouTube.來(lái)自于谷歌旗下的視頻分享網(wǎng)站，類(lèi)似于一個(gè)社交網(wǎng)絡(luò)，節(jié)點(diǎn)表示用戶，標(biāo)簽表示用戶ID，邊表示用戶之間有關(guān)系，標(biāo)簽表示用戶之間的關(guān)系.由于原始數(shù)據(jù)集上并不含有節(jié)點(diǎn)和邊的標(biāo)簽，因此隨機(jī)地對(duì)節(jié)點(diǎn)和邊進(jìn)行標(biāo)簽的添加，標(biāo)簽分布服從高斯分布，節(jié)點(diǎn)和邊標(biāo)簽分別為25個(gè)和5個(gè)，為非冪率分布數(shù)據(jù)集.

針對(duì)不同的數(shù)據(jù)集特點(diǎn)，在算法的運(yùn)行過(guò)程中需要設(shè)置不同的參數(shù)使其能夠運(yùn)行，具體的參數(shù)設(shè)置如表2所示.表2中，MinSupport表示最小支持度，只有滿足最小支持度的子圖才會(huì)認(rèn)為是頻繁子圖；Num-Executors表示執(zhí)行的CPU數(shù)量；Executor-Cores表示執(zhí)行核心數(shù)；Parallelism表示算法的并行程度；Batch-Size表示防止內(nèi)存溢出，對(duì)任務(wù)進(jìn)行了分片處理的分片大小.

Table 2 Experiment Parameter Setting

為了評(píng)估DIMSARI算法的性能，實(shí)驗(yàn)部分選擇了與下列算法進(jìn)行對(duì)比，對(duì)比算法都改造為Spark平臺(tái)下的算法，以保證實(shí)驗(yàn)運(yùn)行環(huán)境的一致性.

1) RDN.是文獻(xiàn)[2]的隨機(jī)節(jié)點(diǎn)采樣算法的進(jìn)化版本，采樣的過(guò)程中偏向于節(jié)點(diǎn)度比較高的節(jié)點(diǎn)，屬于不均勻采樣.

2) TIES.是在文獻(xiàn)[11]的隨機(jī)邊采樣的基礎(chǔ)上增加了圖感應(yīng)操作，準(zhǔn)確率得到了較大的提高.

3) AS.是文獻(xiàn)[8]的MHRW算法和文獻(xiàn)[9]隨機(jī)跳算法的結(jié)合，可以有效地避免陷入局部區(qū)域，增加了非連通圖處理.

4.2 度量指標(biāo)

1) 歸一化均方偏差(normalized mean squared error,NMSE)

NMSE是一種常用的檢驗(yàn)方法，主要用于檢驗(yàn)采樣后的子圖節(jié)點(diǎn)的度與原始圖節(jié)點(diǎn)的度的差異，定義如下：

其中，θ表示原始圖的節(jié)點(diǎn)的度，θ′表示采樣后子圖節(jié)點(diǎn)的度.NMSE值越小，代表采樣后的子圖節(jié)點(diǎn)的分布與原始圖越相似.

2) 準(zhǔn)確率、召回率和F1值

Accuracy=HitsSampledCount,

Recall=HitsOriginalCount,

F1=2×Accuracy×Recall(Accuracy+Recall),

其中，Hits表示采樣前和采樣后頻繁子圖相同的數(shù)量，SampledCount表示采樣后子圖的頻繁子圖的數(shù)量，OriginalCount表示采樣前原始圖的頻繁子圖的數(shù)量.

準(zhǔn)確率為采樣前后頻繁子圖相同的數(shù)量與采樣后子圖的頻繁子圖的數(shù)量的比值，召回率為采樣前后頻繁子圖相同的數(shù)量與采樣前原始圖的頻繁子圖的數(shù)量的比值，對(duì)準(zhǔn)確率和召回率進(jìn)行組合得到F1值，可以有效地評(píng)價(jià)結(jié)果的好壞.

4.3 采樣前后的結(jié)構(gòu)相似度評(píng)估

采樣后的子圖是否保持原圖的結(jié)構(gòu)可以評(píng)價(jià)采樣結(jié)果的好壞，采樣后的子圖與原始圖的節(jié)點(diǎn)的度的NMSE值對(duì)比結(jié)果在圖5中給出，各數(shù)據(jù)集的參數(shù)設(shè)置如表2所示.

圖5顯示了不同的數(shù)據(jù)集下不同的采樣率時(shí)各算法的NMSE值的大小.可以看出，不管在哪種數(shù)據(jù)集下，DIMSARI算法的NMSE值都是最小，說(shuō)明使用DIMSARI算法對(duì)原圖的結(jié)構(gòu)保持最好；隨著采樣率的提高，NMSE值逐漸減小，滿足采樣越多，跟原圖結(jié)構(gòu)越相似的特點(diǎn)；AS算法性能次之，這是因?yàn)樵诓蓸訒r(shí)只考慮節(jié)點(diǎn)的度，沒(méi)有考慮邊的缺失，實(shí)驗(yàn)顯示性能普遍低于DIMSARI算法；TIES算法在隨機(jī)邊采樣的基礎(chǔ)上增加了圖感應(yīng)操作，可以看出其結(jié)果與AS算法類(lèi)似，隨機(jī)邊采樣后邊稀疏，NMSE值會(huì)很高，在此基礎(chǔ)上增加了圖感應(yīng)操作，將丟失邊補(bǔ)齊，使其取得不錯(cuò)的結(jié)果；而RDN算法根據(jù)節(jié)點(diǎn)的度進(jìn)行采樣，集中于采樣節(jié)點(diǎn)度較高的節(jié)點(diǎn)，使其N(xiāo)MSE值較大，與原圖結(jié)構(gòu)相似性較低.

Fig. 5 Sample Rate and NMSE圖5 采樣率與NMSE圖

Fig. 6 Sample Rate and F1 score圖6 采樣率與F1值圖

4.4 采樣后頻繁子圖挖掘的性能評(píng)估

將本方法與對(duì)比采樣方法用于頻繁子圖挖掘，挖掘方法均采用文獻(xiàn)[18]的算法，F(xiàn)1值的結(jié)果如圖6所示(各數(shù)據(jù)集的參數(shù)設(shè)置見(jiàn)表2).

圖6顯示在不同的數(shù)據(jù)集下DIMSARI與RDN，TIES，AS算法的對(duì)比，橫坐標(biāo)表示采樣率的范圍是0.1～0.9，縱坐標(biāo)表示算法的F1值.從圖6可以看出，DIMSARI算法在DBLP數(shù)據(jù)集、Amazon數(shù)據(jù)集、LiveJournal數(shù)據(jù)集中不同的采樣率下F1值都是最高；在YouTube數(shù)據(jù)集上，在采樣率低于0.3時(shí)被TIES算法短暫超越，此時(shí)采樣率較低，采樣后的子圖構(gòu)成的頻繁子圖個(gè)數(shù)少，但是隨著采樣率的提高，DIMSARI算法有明顯的優(yōu)勢(shì).圖6中之所以出現(xiàn)直線，是因?yàn)檫M(jìn)行頻繁子圖挖掘時(shí)設(shè)置最小的子圖為邊，因此根據(jù)最小支持度，每一個(gè)數(shù)據(jù)集都有一個(gè)固定的邊集組成的頻繁子圖集合，頻繁子圖挖掘時(shí)將單個(gè)邊進(jìn)行邊擴(kuò)展，挖掘滿足條件的頻繁子圖，后期不會(huì)出現(xiàn)直線.

對(duì)采樣后的子圖進(jìn)行頻繁子圖挖掘，在保證準(zhǔn)確性的前提下時(shí)間開(kāi)銷(xiāo)的實(shí)驗(yàn)結(jié)果如圖7所示：

Fig. 7 Sample rate and time ratio圖7 采樣率與時(shí)間比圖

圖7中橫坐標(biāo)表示采樣率，縱坐標(biāo)表示采樣后子圖進(jìn)行頻繁子圖挖掘的時(shí)間與原始圖進(jìn)行頻繁子圖挖掘的時(shí)間的比值.從圖7可以看出隨著采樣率的提高，先采樣再進(jìn)行頻繁子圖挖掘的時(shí)間不斷增加；由于在AS算法的基礎(chǔ)上增加了隨機(jī)跳轉(zhuǎn)判斷以及圖感應(yīng)操作，使得DIMSARI算法的運(yùn)行時(shí)間最長(zhǎng)；而TIES算法和AS算法在大部分?jǐn)?shù)據(jù)集上運(yùn)行時(shí)間類(lèi)似，比DIMSARI算法的運(yùn)行時(shí)間短；RDN算法由隨機(jī)節(jié)點(diǎn)采樣增加了節(jié)點(diǎn)度的考慮，運(yùn)行時(shí)間最短，但是其F1值最低，不能很好地滿足采樣后進(jìn)行頻繁子圖挖掘.

4.5 不同最小支持度下算法性能評(píng)估

在采樣率保持0.5不變的情況下，比較不同的最小支持度下進(jìn)行采樣后的子圖與原始圖的歸一化均方偏差NMSE、采樣后進(jìn)行頻繁子圖挖掘的結(jié)果的F1值和運(yùn)行時(shí)間，實(shí)驗(yàn)的結(jié)果如圖8～11所示.

Fig. 8 DBLP dataset圖8 DBLP數(shù)據(jù)集

Fig. 9 Amazon dataset圖9 Amazon數(shù)據(jù)集

Fig. 10 YouTube dataset圖10 YouTube數(shù)據(jù)集

Fig. 11 LiveJournal dataset圖11 LiveJournal數(shù)據(jù)集

圖8～11顯示4個(gè)真實(shí)數(shù)據(jù)集下NMSE,F1值和運(yùn)行時(shí)間與最小支持度的關(guān)系.首先，比較最小支持度與NMSE的關(guān)系，隨著最小支持度不斷減小，NMSE值也減少，DIMSARI算法的NMSE值顯著小于其他算法，而TIES和AS算法的NMSE比較相近，兩者都次于DIMSARI算法，而RDN算法的NMSE值最大，說(shuō)明RDN算法在采樣后的子圖結(jié)構(gòu)與原始圖差距最大，DIMSARI算法與原始圖結(jié)構(gòu)最相似.其次，比較最小支持度與F1值的關(guān)系，隨著最小支持度不斷減小，RDN，TIES，AS算法的F1值一直保持增長(zhǎng)，而DIMSARI算法的F1值會(huì)有一個(gè)增加后減少的過(guò)程，原因在于對(duì)原始圖進(jìn)行頻繁子圖挖掘會(huì)給定一個(gè)最小支持度，一旦超過(guò)該支持度則原始圖無(wú)法進(jìn)行頻繁子圖挖掘，對(duì)原始圖采樣后雖然可以解決頻繁子圖挖掘操作，但是會(huì)挖掘出更多的子圖，使得準(zhǔn)確率降低從而導(dǎo)致F1值減少.最后，比較最小支持度與采樣后進(jìn)行頻繁子圖挖掘時(shí)間開(kāi)銷(xiāo)的關(guān)系，隨著最小支持度不斷減小，運(yùn)行時(shí)間一直保持增加，由于DIMSARI算法在AS算法的基礎(chǔ)上增加了隨機(jī)跳轉(zhuǎn)判斷以及圖感應(yīng)操作，使得DIMSARI算法的運(yùn)行時(shí)間比其他算法的運(yùn)行時(shí)間長(zhǎng).從上面幾個(gè)實(shí)驗(yàn)綜合可以看出，雖然在相同的采樣率和最小支持度下DIMSARI算法的運(yùn)行時(shí)間最長(zhǎng)，但是在達(dá)到相同的F1值的情況下，DIMSARI算法的運(yùn)行時(shí)間最短；而RDN算法采樣的是在隨機(jī)節(jié)點(diǎn)采樣的基礎(chǔ)上增加了節(jié)點(diǎn)度的考慮，運(yùn)行時(shí)間短，但是其F1值不能滿足頻繁子圖挖掘需要.

DIMSARI算法根據(jù)頻繁邊的分布進(jìn)行采樣，在采樣后進(jìn)行頻繁子圖挖掘，不管在冪率圖上還是非冪率圖上都取得不錯(cuò)的結(jié)果.TIES算法在隨機(jī)邊采樣的基礎(chǔ)上增加了圖感應(yīng)操作，AS算法是在MHRW算法的基礎(chǔ)上增加了隨機(jī)跳算法，此2種算法運(yùn)行結(jié)果較為滿意，但都次于DIMSARI算法.RDN算法由于采用的是隨機(jī)節(jié)點(diǎn)采樣，雖然在采樣的過(guò)程中根據(jù)節(jié)點(diǎn)度的信息進(jìn)行采樣，但是由于其采樣時(shí)有偏性，使其在進(jìn)行頻繁子圖挖掘時(shí)效果最差.

5 總 結(jié)

本文提出了一種Spark環(huán)境下基于頻繁邊的大規(guī)模大圖的采樣算法——DIMSARI，該算法在蒙特卡羅算法的基礎(chǔ)上增加了根據(jù)頻繁邊進(jìn)行隨機(jī)跳的操作，在跳轉(zhuǎn)時(shí)考慮邊的頻繁度選擇是否跳轉(zhuǎn)，并對(duì)采樣后的結(jié)果進(jìn)行了圖感應(yīng)操作，一定程度上增加了算法的有效性.實(shí)驗(yàn)通過(guò)對(duì)采樣后的子圖的節(jié)點(diǎn)的度與原始圖節(jié)點(diǎn)的度的差異以及采樣后的子圖進(jìn)行頻繁子圖挖掘的結(jié)果與原始圖進(jìn)行頻繁子圖挖掘的結(jié)果進(jìn)行了準(zhǔn)確性和時(shí)間對(duì)比，顯示該算法比現(xiàn)有算法更加準(zhǔn)確和有效.

本文針對(duì)頻繁子圖挖掘進(jìn)行了基于頻繁邊的采樣算法研究，后期工作可以將其擴(kuò)展到子圖同構(gòu)等圖算法工作中來(lái)提高算法的運(yùn)行效率.

[1]Facebook. Facebook annual reports[EBOL]. 2015 [2016-04-08]. http:investor.fb.comannuals.cfm

[2]Wang Dong, Li Zhenyu, Xie Gaogang. Unbiased sampling technologies on online social network[J]. Journal of Computer Research and Development, 2016, 53(5): 949-967 (in Chinese)(王棟, 李振宇, 謝高崗. 在線社會(huì)網(wǎng)絡(luò)無(wú)偏采樣技術(shù)[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(5): 949-967)

[3]Leskovec J, Faloutsos C. Sampling from large graphs[C]Proc of the 12th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 631-636

[4]Ahmed N, Neville J, Kompella R R. Network sampling via edge-based node selection with graph induction[EBOL]. 2011[2017-02-09]. https:www.researchgate.netpublica-tion254639513

[5]Blagus N, Subelj L, BajecM. Improving the accuracy of network sampling with subgraph induction[JOL]. Physica A, 2014[2016-10-21]. http:lpt.fri.uni-lj.sifileslovroresearchpa-persssi.pdf

[6]Lovász L, Lov L, Erdos O P. Random walks on graphs: A survey[J]. Combinatorics, 1996, 8(4): 1-46

[7]Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: Densification laws, shrinking diameters and possible explanations[C]Proc of the 11th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2005: 177-187

[8]Ahn Y Y, Han S, Kwak H, et al. Analysis of topological characteristics of huge online social networking services[C]Proc of the 16th Int Conf on World Wide Web. New York: ACM, 2007: 835-844

[9]Gjoka M, Kurant M, Butts C T, et al. Walking in Facebook: A case study of unbiased sampling of OSNs[C]Proc of the 30th IEEE Int Conf on Computer Communications. Los Alamitos, CA: IEEE Computer Society, 2011: 1-9

[10]Jin Long, Chen Yang, Hui Pan, et al. Albatross sampling: Robust and effective hybrid vertex sampling for social graphs[C]Proc of the 3rd ACM Int Workshop on MobiArch. New York: ACM, 2011: 11-16

[11]Yoon S H, Kim K N, Hong J, et al. A community-based sampling method using DPL for online social networks[J]. Information Sciences, 2011, 306: 53-69

[12]Du Xiaolin, Ye Yunming, Li Yueping, et al. A new relational networks sampling algorithm using topologically divided stratums[J]. Advanced Science and Technology Letters, 2014, 48: 108-119

[13]Rezvanian A, Meybodi M R. Sampling social networks using shortest paths[J]. Physica A: Statistical Mechanics & Its Applications, 2015, 424: 254-268

[14]Jalali Z S, Rezvanian A, Meybodi M R. Social network sampling using spanning trees[J]. International Journal of Modern Physics C, 2015, 27(5): 1-20

[15]Ullmann J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1): 31-42

[16]Holder L B, Cook D J, Djoko S. Substructure discovery in the subdue system[C]Proc of the Workshop on Knowledge Discovery in Databases. Menlo Park, CA: AAAI, 1994: 169-180

[18]Nummelin E. General Irreducible Markov Chains and Nonneigative Operators[M]. Cambridge, UK: Cambridge University Press, 2004

[19]Yan Yuliang, Dong Yihong, He Xianmang, et al. FSMBUS: A frequent subgraph mining algorithm in single large-scale graph using Spark[J]. Journal of Computer Research and Development, 2015, 52(8): 1768-1783 (in Chinese)(嚴(yán)玉良, 董一鴻, 何賢芒, 等. FSMBUS: 一種基于Spark的大規(guī)模頻繁子圖挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(8): 1768- 1783)

[20]Standford University. SNAP[EBOL]. [2016-05-23]. http:snap.stanford.edusnappy

Li Longyang, born in 1991. Master from the Faculty of Information Science and Engineering, Ningbo University. His main research interests include data mining and machine learning.

Dong Yihong, born in 1969. PhD, professor and master supervisor in the Faculty of Information Science and Engineering, Ningbo University. His main research interests include big data, data mining and artificial intelligence.

Yan Yuliang, born in 1990. Master from the Faculty of Information Science and Engineering, Ningbo University. His main research interests include graph mining, cloud computing and machine learning.

Chen Huahui, born in 1964. PhD, professor. Member of CCF. His main research interests include data streams and massive data processing (chenhuahui@nbu.edu.cn).

Qian Jiangbo, born in 1974. PhD, professor. Member of CCF. His main research interests include data management, streaming data processing, multidimensional indexing and query optimization (qianjb@163.com).

A Sampling Algorithm Based on Frequent Edges in Single Large-Scale Graph Under Spark

Li Longyang, Dong Yihong, Yan Yuliang, Chen Huahui, and Qian Jiangbo

(FacultyofElectricalEngineeringandComputerScience,NingboUniversity,Ningbo,Zhejiang315211)

With the popularity of social networks, the demand for its frequent subgraph mining becomes more intense. With the arrival of the era of big data, social networks have been expanding and frequent subgraph mining becomes increasingly difficult. In fact, it does not require to mine frequent subgraphs exactly in application, so sampling methods are adopted to improve the efficiency of mining frequent subgraphs under certain accuracy. Most existing sampling algorithms are not fit for frequent subgraph mining because they use vertex transfer or compute the topology of the original graph first which will take a lot of time. In this paper, we propose a new sampling algorithm named DIMSARI (distributed Monte Carlo sampling algorithm based on random jump and graph induction) based on frequent edge, and it runs on a distributed framework named Spark. This algorithm is created on the basis of the Monte Carlo algorithm meanwhile adding random jump. The results are added by subgraph induction step to promote the accuracy of the algorithm and prove that the algorithm is unbiased. The experiments show that the accuracy of frequent subgraph mining using DIMSARI algorithm has been greatly improved and at the same time the proposed algorithm only spends a little more time than other algorithms. The apex of sampling at different sampling rates after subgraphs has maintained a lower normalized mean square error.

sample; frequent subgraph; single large-scale graph; frequent edge; Spark

2016-07-27；

2017-03-07

國(guó)家自然科學(xué)基金項(xiàng)目(61572266，61472194)；浙江省自然科學(xué)基金項(xiàng)目(Y16F020003)；寧波市自然科學(xué)基金項(xiàng)目(2017A610114) This work was supported by the National Natural Science Foundation of China (61572266, 61472194), the Natural Science Foundation of Zhejiang Province of China (Y16F020003), and the Natural Science Foundation of Ningbo of China (2017A610114).

董一鴻(dongyihong@nbu.edu.cn)

TP301