王 卓，索 勃，潘 巍

(西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,西安 710129)

三角形的并行枚舉算法

王 卓，索 勃，潘 巍*

(西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,西安 710129)

經(jīng)典GT算法是三角形并行枚舉算法的MapReduce實(shí)現(xiàn)，然而該算法只能枚舉全圖的三角形結(jié)構(gòu)，對部分頂點(diǎn)構(gòu)成的三角形結(jié)構(gòu)無法直接進(jìn)行枚舉。針對此問題，提出一種直接枚舉部分頂點(diǎn)構(gòu)成三角形結(jié)構(gòu)的并行算法。首先,通過分析被選點(diǎn)的分布，給出被選點(diǎn)構(gòu)成三角形的所有組合集合；然后，通過對該集合的篩選，實(shí)現(xiàn)對部分點(diǎn)構(gòu)成三角形結(jié)構(gòu)的直接枚舉；最后，將該算法在Spark系統(tǒng)實(shí)現(xiàn)，以實(shí)現(xiàn)該算法的高效性和廣泛性。在人工生成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上與GT算法進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所提改進(jìn)算法的運(yùn)行時(shí)間只有GT算法運(yùn)行時(shí)間的1/3，在Spark上的運(yùn)行時(shí)間僅是Hadoop上運(yùn)行時(shí)間的1/7。該算法可用于更高效地直接生成圖中任意點(diǎn)所構(gòu)成的三角形數(shù)據(jù)集。

三角形枚舉；大規(guī)模圖數(shù)據(jù)；MapReduce；部分點(diǎn)枚舉；Spark

0 引言

在密集圖的應(yīng)用分析中，研究頂點(diǎn)之間的關(guān)系是圖分析的熱點(diǎn)，而對三角形關(guān)系的研究又是重要的研究方向。

在圖論的研究中，三角形關(guān)系是復(fù)雜社會(huì)網(wǎng)絡(luò)分析中常見的結(jié)構(gòu)[1]。如在社交網(wǎng)絡(luò)關(guān)系中，通過分析三角性關(guān)系可以確定節(jié)點(diǎn)之間的聯(lián)系程度；在角色行為識別中，通過分析三角形關(guān)系可以判斷角色之間的地位。三角關(guān)系的一個(gè)重要應(yīng)用是在枚舉圖的極大團(tuán)(Maximal Clique)過程中[2]，即將一跳(one-top，即與被選點(diǎn)直接相鄰的點(diǎn)構(gòu)成的集合)數(shù)據(jù)轉(zhuǎn)換為三角形結(jié)構(gòu)。

研究者已提出很多算法[3-5]實(shí)現(xiàn)一跳數(shù)據(jù)集向三角形數(shù)據(jù)集的轉(zhuǎn)換，但伴隨著數(shù)據(jù)量的增大，傳統(tǒng)的單機(jī)算法已無法快速地處理大規(guī)模圖數(shù)據(jù)。隨著MapReduce并行計(jì)算框架的普及，很多研究已開始使用MapReduce框架進(jìn)行圖數(shù)據(jù)的處理[6-7]，并且已有研究者實(shí)現(xiàn)了MapReduce框架下將一跳數(shù)據(jù)集向三角形數(shù)據(jù)集轉(zhuǎn)換的GT(Graph Twiddling)算法[8]。GT算法通過兩輪MapReduce 任務(wù)來完成數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，該算法可以很高效地將整個(gè)原圖的一跳形式處理成三角形結(jié)構(gòu)，但卻無法直接生產(chǎn)部分點(diǎn)的三角形結(jié)構(gòu)。同時(shí)，該算法是圖上迭代計(jì)算，在MapReduce計(jì)算框架下，由于需要將中間結(jié)果寫回磁盤，將造成很大的讀寫瓶頸。

基于以上兩個(gè)問題，本文首先提出可直接枚舉部分點(diǎn)三角形結(jié)構(gòu)的改進(jìn)GT算法，該算法經(jīng)過兩輪MapReduce任務(wù)：第一輪為查詢點(diǎn)的篩選，第二輪為查詢點(diǎn)三角形結(jié)構(gòu)的生成；同時(shí)，將改進(jìn)算法在Spark系統(tǒng)上實(shí)現(xiàn)，以實(shí)現(xiàn)該算法高效迭代的特性。本文的主要工作如下：

1) 改進(jìn)GT算法，使該算法可以直接生產(chǎn)部分點(diǎn)的三角形結(jié)構(gòu)；同時(shí)，在三角形的篩選過程中，提出按照最小度數(shù)點(diǎn)進(jìn)行切分的優(yōu)化思想，以提高枚舉效率。

2) 將改進(jìn)算法在Spark系統(tǒng)實(shí)現(xiàn)，避免因MapReduce框架下需要將中間結(jié)果寫回磁盤的瓶頸，以提高迭代計(jì)算效率。

3) 通過合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集驗(yàn)證該算法的高效性，與改進(jìn)前相比，具有至少3倍的運(yùn)行效率提升。

1 相關(guān)技術(shù)

本章介紹與本文研究密切相關(guān)的兩個(gè)概念：三角形結(jié)構(gòu)和MapReduce計(jì)算框架。

1.1 三角形結(jié)構(gòu)

設(shè)無向圖G=(V,E)，其中：V是頂點(diǎn)的集合，|V|是頂點(diǎn)的總數(shù)；E是邊的集合，|E|是邊的總數(shù)。

定義1 三角形結(jié)構(gòu)。給定一個(gè)無向圖G=(V,E)，{u,v,w}∈V，若三個(gè)頂點(diǎn)滿足以下關(guān)系{u,v}，{w,v}，{u,w}∈E，則稱三個(gè)頂點(diǎn)構(gòu)成了一個(gè)三角形結(jié)構(gòu)，記為△uvw。

1.2 MapReduce計(jì)算框架

MapReduce計(jì)算模型是將計(jì)算分為Map和Reduce兩個(gè)階段。在Map階段，由用戶定義的map函數(shù)將輸入的每條元組轉(zhuǎn)換為〈key,value〉形式，然后按照partition函數(shù)對key進(jìn)行分區(qū)，并將各分區(qū)Shuffle到Reduce端，且嚴(yán)格保證分區(qū)和Reducer是一一對應(yīng)的關(guān)系。當(dāng)各Reducer獲取分配給各自分區(qū)的全部數(shù)據(jù)后開始執(zhí)行用戶定義的reduce函數(shù)，并輸出結(jié)果。

影響Reducer執(zhí)行效率的關(guān)鍵是partition函數(shù)的定義，合理的partition函數(shù)可以實(shí)現(xiàn)各Reducer運(yùn)行過程中的均衡性，反之會(huì)出現(xiàn)數(shù)據(jù)傾斜，嚴(yán)重影響執(zhí)行效率。對于數(shù)據(jù)的分配均衡問題，文獻(xiàn)[9]已進(jìn)行了探討并提出了相應(yīng)的策略。該問題的避免可以通過定義partition函數(shù)或定義map函數(shù)等方法優(yōu)化，因此，在設(shè)計(jì)MapReduce算法時(shí)應(yīng)該考慮該數(shù)據(jù)傾斜的問題。

MapReduce在處理迭代計(jì)算時(shí)，有兩處磁盤操作，map函數(shù)后和reduce函數(shù)的結(jié)果輸出，因此MapReduce在處理圖的迭代計(jì)算時(shí)存在數(shù)據(jù)傳輸?shù)钠款i問題。針對該問題，已有i2MapReduce[10]方法可進(jìn)行高效的迭代計(jì)算，同時(shí)Spark系統(tǒng)更是被廣泛應(yīng)用的圖處理平臺(tái)。

2 GT算法

本章介紹基于MapReduce編程模型的GT算法。

GT算法將三角形的枚舉過程分為兩個(gè)MapReduce任務(wù)：第一，合并公共點(diǎn)；第二，判斷合并后的公共點(diǎn)集合中是否存在三角形結(jié)構(gòu)。

第一輪MapReduce任務(wù)：map函數(shù)將同一節(jié)點(diǎn)的所有鄰接點(diǎn)進(jìn)行匯總，并傳到一個(gè)Reducer上處理。reduce函數(shù)將與該點(diǎn)相連，且編號大于該點(diǎn)的所有頂點(diǎn)進(jìn)行笛卡爾積運(yùn)算，并將結(jié)果輸出。

第二輪MapReduce任務(wù)：map函數(shù)將原圖和第一輪Reduce端的輸出結(jié)果合并，即邊作為key值輸出。reduce函數(shù)判斷第一輪笛卡爾積所構(gòu)成的邊集合中，是否存在原圖中的邊。若在原圖中存在該邊，則說明該邊的兩個(gè)頂點(diǎn)與生成該邊的點(diǎn)，即第一輪中reduce函數(shù)key所表示的頂點(diǎn)，構(gòu)成了一個(gè)三角形結(jié)構(gòu)。

根據(jù)對GT算法的描述可知，在第一輪Reduce階段，需要進(jìn)行笛卡爾積操作，度數(shù)較大的點(diǎn)會(huì)產(chǎn)生大量的中間結(jié)果。GT算法在處理時(shí)，將原圖以一跳的形式表示，并滿足第一個(gè)頂點(diǎn)編號的值小于第二個(gè)頂點(diǎn)編號的值，同時(shí)，將度數(shù)小的頂點(diǎn)作為key值，然后再進(jìn)行分區(qū)，從而達(dá)到減少中間結(jié)果的目的。

GT算法不能直接枚舉出部分點(diǎn)所構(gòu)成的三角形結(jié)構(gòu)。由于第一輪map函數(shù)是按照度數(shù)或者頂點(diǎn)編號進(jìn)行劃分的，因此在枚舉部分點(diǎn)構(gòu)成的三角形結(jié)構(gòu)時(shí)，當(dāng)被選點(diǎn)出現(xiàn)在value中，就無法獲得被選點(diǎn)的完整鄰接點(diǎn)集合，從而導(dǎo)致查詢的結(jié)果不完整。因此，若使用GT算法來枚舉部分點(diǎn)的三角形結(jié)構(gòu)，首先需要枚舉出原圖的所有三角形，然后從全圖的三角形集合中篩選出包含被選點(diǎn)的結(jié)構(gòu)。由此可見，這樣將造成大量的不相關(guān)計(jì)算。

3 PGT算法

本章介紹可直接枚舉部分頂點(diǎn)構(gòu)成三角形結(jié)構(gòu)的改進(jìn)GT算法，本文稱為PGT(Parts-of-vertex for GT)算法。

3.1 算法描述

要解決GT算法直接枚舉部分點(diǎn)構(gòu)成三角形結(jié)構(gòu)的問題，就需要解決如何在劃分過程中保持?jǐn)?shù)據(jù)的完整性問題，因此首先需要統(tǒng)計(jì)出被選點(diǎn)劃分后的分布情況。由于MapReduce模型采用〈key,value〉對處理數(shù)據(jù)的特點(diǎn)，在數(shù)據(jù)劃分后被選點(diǎn)只會(huì)現(xiàn)在兩個(gè)集合中：第一是在key中，如圖 1(a)所示的第一層頂點(diǎn)編號為A的頂點(diǎn)(被選點(diǎn))；第二個(gè)是在value中，如圖 1(b)所示的第二層頂點(diǎn)編號為B的頂點(diǎn)(被選點(diǎn))。因此，要保證數(shù)據(jù)的完整性需要同時(shí)將兩種情況進(jìn)行分析。

圖 1 被選點(diǎn)的分布Fig. 1 Distribution of candidate vertexes

如圖 1(a)所示，被選點(diǎn)在key集合中。在該結(jié)構(gòu)中，value集合中的頂點(diǎn)是key的鄰接點(diǎn)集合，如圖中實(shí)線所示。在該結(jié)構(gòu)中若存在三角形，一定是value中的某兩個(gè)頂點(diǎn)存在一條邊，即如圖中虛線所示。因此，對于這種情況，需要將value集合中的所有頂點(diǎn)進(jìn)行笛卡爾積運(yùn)算，即構(gòu)建出一條新邊，并通過下一輪MapReduce任務(wù)判斷該邊是否在原圖中存在，若存在，則該點(diǎn)(key)與相連的兩點(diǎn)(value中的頂點(diǎn))構(gòu)成了三角形結(jié)構(gòu)。

如圖 1(b)所示，被選點(diǎn)出現(xiàn)在value中。出現(xiàn)這種情況的原因是：為了減少笛卡爾積集合的大小，在劃分時(shí)是以兩個(gè)點(diǎn)的度數(shù)為標(biāo)準(zhǔn)，即度數(shù)小的點(diǎn)為key，因此導(dǎo)致被選點(diǎn)會(huì)出現(xiàn)在value中的現(xiàn)象。在此種結(jié)構(gòu)中，同樣value集合中的點(diǎn)是key點(diǎn)的鄰接點(diǎn)，然而只需要枚舉包含有被選點(diǎn)的集合。因此，此時(shí)只需要將被選點(diǎn)從value中取出，然后將該點(diǎn)和value中的其他點(diǎn)進(jìn)行笛卡爾積運(yùn)算，構(gòu)建出一條新邊，如圖 1(b)中虛線所示。同樣，通過下一輪MapReduce任務(wù)判斷該邊是否在原圖中存在，若存在，則該點(diǎn)(value中的被選點(diǎn))和相連的兩個(gè)點(diǎn)(key頂點(diǎn)和在value中與被選點(diǎn)相連的頂點(diǎn))構(gòu)成了三角形結(jié)構(gòu)。

3.2 算法實(shí)現(xiàn)

算法1 PGT算法的MapReduce實(shí)現(xiàn)。

輸入 集合key,集合value,被選點(diǎn)構(gòu)成的集合Cand;

輸出 候選邊集Edge。

1)

ifkeyinCand

//被選點(diǎn)在key集合中

2)

forvtovalue

//遍歷value集合，求笛卡爾積

3)

Edge←v×{value-v}

4)

Write(Edge,key)

//輸出，并標(biāo)注是在key集合中

5)

endfor

6)

endif

7)

else

8)

forntovalue

//被選點(diǎn)在value集合中

9)

ifninCand

10)

Edge←n×{value-n}

11)

Write(Edge,n)

//輸出，并標(biāo)注是在value集合中

12)

endif

13)

endfor

14)

endelse

算法1可分為兩部分：第一部分從1)～6)行，是對被選點(diǎn)在key中情況的處理，第二部分從7)～14)行，是對被選點(diǎn)在value中的處理。由于在第二輪MapReduce任務(wù)中，需要將被選點(diǎn)進(jìn)行聚合，所以在輸出時(shí)，需要標(biāo)明被選點(diǎn)的編號，即如算法1第4)行和第11)行所示。由算法1描述可知，該算法的復(fù)雜度為O(n)。

算法2 PGT算法的Spark實(shí)現(xiàn)。

輸入 集合key，集合value，被選點(diǎn)構(gòu)成的集合Cand;

輸出 三角形邊集edges。

1)

defPGT(key: Int,value:Set[Int],Cand:Set[Int])={

2)

if (Cand.contains(key)) {

3)

for (v←value){

//遍歷value集合

4)

valnotV=value-v

5)

valedges=notV.map(v2 => {

6)

(v,v2)

// 對value中的點(diǎn)求笛卡爾積

7)

})

8)

(edges,key)

//第一種情況的輸出

9)

}

//end for

10)

}

//end if

11)

else {

12)

for (n←value) {

13)

if (Cand.contains(n)){

//被選點(diǎn)在value中

14)

valnotN=value-n

//除去本點(diǎn)后求笛卡爾積

15)

valedges=notN.map(n2=> {

16)

(n,n2)

//第二種情況的輸出

17)

}

18)

(edges,n)

19)

}

//end if

20)

}

//end for

21)

}

//end else

22)

}

//end function

算法2由兩部分組成：第一部分從1)～10)行，是對被選點(diǎn)在key中情況的處理，第二部分從11)～22)行，是對被選點(diǎn)在value中的處理。函數(shù)PGT()是Spark中reduce函數(shù)的參數(shù)，即實(shí)現(xiàn)對三角形的篩選工作，不同于MapReduce的輸出，Spark的輸出可存儲(chǔ)在內(nèi)存中，以實(shí)現(xiàn)迭代計(jì)算的高效性。

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

本章通過兩部分實(shí)驗(yàn)驗(yàn)證GPT算法的高效性，實(shí)驗(yàn)是在兩個(gè)人工生成數(shù)據(jù)集和兩個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行，通過隨機(jī)選點(diǎn)的方法比較兩個(gè)算法的運(yùn)行時(shí)間。

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

本文的所有實(shí)驗(yàn)在11個(gè)節(jié)點(diǎn)的集群上進(jìn)行，其中包含1個(gè)Master節(jié)點(diǎn)負(fù)責(zé)任務(wù)的調(diào)度和集群管理， 10個(gè)Worker節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)數(shù)據(jù)和計(jì)算。每個(gè)節(jié)點(diǎn)的系統(tǒng)配置為:16 核主頻為 2.20 GHz 的AMD 處理器，16 GB 的 RAM 和 1 TB的硬盤，節(jié)點(diǎn)之間通過1 Gb的網(wǎng)絡(luò)連接，各節(jié)點(diǎn)用的是 64 位Ubuntu Linux12.01，部署的是Hadoop-1.2.1版本和Spark-1.6.1。

配置Hadoop，設(shè)置每個(gè)節(jié)點(diǎn)有10個(gè)Map slots和6個(gè)Reduce slots，采用默認(rèn)的Hash分區(qū)函數(shù)，其他配置設(shè)置為默認(rèn)值。為增強(qiáng)實(shí)驗(yàn)的說服力，同一組實(shí)驗(yàn)運(yùn)行5次，取5次結(jié)果的平均值作為最終結(jié)果。

4.2 實(shí)驗(yàn)數(shù)據(jù)

對于兩種數(shù)據(jù)源作去重和格式化處理，并將數(shù)據(jù)處理為1-跳的形式。實(shí)驗(yàn)數(shù)據(jù)分為合成數(shù)據(jù)和真實(shí)數(shù)據(jù)，合成數(shù)據(jù)通過GTgraph[11]生成，包含DARPA HPCS SSCA (SSCA)和Recursive Matrix (R-MAT)數(shù)據(jù)，SSCA的參數(shù)設(shè)置：頂點(diǎn)數(shù)為220，極大團(tuán)的大小為100；R-MAT設(shè)置頂點(diǎn)數(shù)為104，邊與頂點(diǎn)的比值為1 000。真實(shí)數(shù)據(jù)包含兩種SOCIAL NETWORKS[12]數(shù)據(jù)，數(shù)據(jù)的分布情況如表1所示。

表 1 實(shí)驗(yàn)數(shù)據(jù)Tab. 1 Experimental data

4.3 對比實(shí)驗(yàn)

本節(jié)在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上比較兩種算法的運(yùn)行時(shí)間。實(shí)驗(yàn)采用隨機(jī)選點(diǎn)，驗(yàn)證選點(diǎn)個(gè)數(shù)的不同對兩種算法運(yùn)行時(shí)間的影響。由于GT算法首先需要將一跳數(shù)據(jù)集全部轉(zhuǎn)換為三角形數(shù)據(jù)集，這部分需要兩輪MapReduce任務(wù)完成，經(jīng)過5次測試，這部分的平均時(shí)間為3 200 s。由于是處理部分點(diǎn)，在對比實(shí)驗(yàn)部分，不將這部分的時(shí)間計(jì)算在內(nèi)；因此運(yùn)行時(shí)間的統(tǒng)計(jì)分別為：GT算法為從全部三角形數(shù)據(jù)集中讀取部分點(diǎn)的時(shí)間，PGT算法為從一跳數(shù)據(jù)集直接生產(chǎn)部分點(diǎn)的三角形數(shù)據(jù)集的時(shí)間。

圖2(a)、(b)分別是兩種算法在合成數(shù)據(jù)集SSCA和R-MAT上的實(shí)驗(yàn)，圖2(c)、(d)分別是兩種算法在真實(shí)數(shù)據(jù)集Orkut和Twitter上的實(shí)驗(yàn)。通過結(jié)果可以發(fā)現(xiàn)，GT算法和PGT算法都有很好的穩(wěn)定性，而從運(yùn)行時(shí)間上來看，在SSCA和R-MAT數(shù)據(jù)集上，GT算法的運(yùn)行時(shí)間是PGT算法的3倍和4倍。隨著輸入數(shù)據(jù)量的增大，在真實(shí)數(shù)據(jù)集Orkut和Twitter上，GT算法的運(yùn)行時(shí)間都是PGT算法運(yùn)行時(shí)間的11倍。由此可見PGT算法在運(yùn)行效率上有很大的提升。

4.4 Spark性能實(shí)驗(yàn)

由于GT算法本身只有MapReduce實(shí)現(xiàn)，因此本節(jié)給出PGT算法在Hadoop和Spark系統(tǒng)上運(yùn)行的對比實(shí)驗(yàn)，使用的數(shù)據(jù)集為圖2(d)的Twitter數(shù)據(jù)集，對比實(shí)驗(yàn)如圖3所示。

從圖3結(jié)果可以看出，Spark系統(tǒng)在運(yùn)行時(shí)間上比Hadoop系統(tǒng)有近7倍的性能提升，這主要因?yàn)镾park在迭代過程中未將結(jié)果寫入磁盤，從而減少了對磁盤的讀寫操作。

圖2 GT和PGT算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間對比Fig. 2 Runtime contrast of GT and PGT on different datasets

圖3 Spark與Hadoop上PGT算法運(yùn)行時(shí)間對比Fig. 3 Runtime contrast of PGT algorithm on Spark and Hadoop

5 結(jié)語

本文提出一種改進(jìn)的PGT算法，用于枚舉部分點(diǎn)的三角形結(jié)構(gòu)，并給出算法的MapReduce實(shí)現(xiàn)和Spark實(shí)現(xiàn)方法。該算法與傳統(tǒng)算法相比，可以在三角形的生成過程中，只生成部分點(diǎn)的三角形結(jié)構(gòu)，而避免對非篩選節(jié)點(diǎn)的三角形枚舉工作，并最后在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上，驗(yàn)證該算法的高效性。三角形枚舉是圖數(shù)據(jù)研究中重要的應(yīng)用，今后可通過本文的方法實(shí)現(xiàn)快速的三角形結(jié)構(gòu)枚舉。

References)

[1] PARANJAPE A, BENSON A R, LESKOVEC J. Motifs in temporal networks [C]// Proceedings of the 2017 Tenth ACM International Conference on Web Search and Data Mining. New York: ACM, 2017: 601-610.

[2] WANG Z, CHEN Q, HOU B Y, et al. Parallelizing maximal clique andk-plex enumeration over graph data [J]. Journal of Parallel and Distributed Computing, 2017, 106: 79-91.

[3] COHEN J. Trusses: cohesive subgraphs for social network analysis [R]. Fort Meade, MD: National Security Agency, 2008.

[4] 金宏橋,董一鴻.大數(shù)據(jù)下圖三角計(jì)算的研究進(jìn)展[J].電信科學(xué),2016,32(6):153-162.(JIN H Q, DONG Y H. Research progress of triangle counting in big data [J]. Telecommunications Science, 2016, 32(6): 153-162.)

[5] SHAIK F, SUBRAMANYAM R, SOMAYAJULU D. Map-reduce based multiple sub-graph enumeration using dominating-set graph partition [J]. International Journal of Information Engineering and Electronic Business, 2017, 9(2): 36-44.

[6] QIN L, YU J X, CHANG L J, et al. Scalable big graph processing in MapReduce [C]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2014: 827-838.

[7] SALIHOGLU S, WIDOM J. GPS: a graph processing system [C]// Proceedings of the 25th International Conference on Scientific and Statistical Database Management. New York: ACM, 2013: Article No. 22.

[8] COHEN J. Graph twiddling in a MapReduce world [J]. Computing in Science & Engineering, 2009, 11(4): 29-41.

[9] 王卓,陳群,李戰(zhàn)懷,等.基于增量式分區(qū)策略的MapReduce數(shù)據(jù)均衡方法[J].計(jì)算機(jī)學(xué)報(bào),2016,39(1):19-35.(WANG Z, CHEN Q, LI Z H, et al. An incremental partitioning strategy for data balance on MapReduce [J]. Chinese Journal of Computers, 2016, 39(1): 19-35.)

[10] ZHANG Y F, CHEN S M, WANG Q, et al. i2MapReduce: incremental MapReduce for mining evolving big data [J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(7): 1906-1919.

[11] BADER D A, MADDURI K. GTGraph: a synthetic graph generator suite [EB/OL]. [2017- 05- 06]. https://www.researchgate.net/publication/228993783_GTGraph_A_synthetic_graph_generator_suite.

[12] ROSSI R A, AHMED N K. The network data repository with interactive graph analytics and visualization [C]// Proceedings of the 2015 Twenty-Ninth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI, 2015: 4292-4293.

This work is partially supported by the Ministry of Science and Technology of China, National Key Research and Development Program (2016YFB1000703), the National High Technology Research and Development Program of China (863 Program) (2015AA015307), the Key Program of National Natural Science Foundation of China (61332006), the General Program of National Natural Science Foundation of China (61672432, 61472321), the National Natural Science Foundation of China for Young Scholars (61502390).

WANGZhuo, born in 1984, Ph. D. candidate. His research interests include graph data management, distributed computing platform.

SUOBo, born in 1987, Ph. D. candidate. His research interests include graph data management.

PANWei, born in 1978, Ph. D., associate professor. His research interests include memory computing.

Parallelalgorithmfortriangleenumeration

WANG Zhuo, SUO Bo, PAN Wei*

(SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’anShaanxi710129,China)

The classical Graph Twiddling (GT) algorithm is the MapReduce implementation of triangle parallel enumeration algorithm. However, the GT algorithm can only enumerate the triangle structure of whole graph and can not enumerate the triangle structure of candidate vertexes directly. To solve the problem, a parallel algorithm was proposed for directly enumerating the triangle structure of candidate vertexes. Firstly, the set of all the combinations of candidate vertexes for forming triangle was given by analyzing the distribution of candidate vertexes. Then, through the screening of the set, the triangle structure of candidate vertexes was directly enumerated. Finally, the proposed algorithm was implemented on Spark to achieve high efficiency and popularity. The contrast experiment was completed on artificial datasets and real datasets. The experimental results show that, compared with the GT algorithm, the running time of the proposed algorithm is only 1/3 of the running time of GT algorithm, and the running time on Spark is only 1/7 of the running time on Hadoop. The proposed algorithm can be used to generate the triangle dataset of any candidate vertex directly and efficiently.

triangle enumeration; large-scale graph data; MapReduce; candidate vertex enumeration; Spark

2017- 07- 04;

2017- 09- 05。

中國科技部國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1000703)；國家863重大項(xiàng)目(2015AA015307)；國家自然科學(xué)基金重點(diǎn)項(xiàng)目(61332006)；國家自然科學(xué)基金面上項(xiàng)目(61672432，61472321)；國家自然科學(xué)基金青年項(xiàng)目(61502390)。

王卓 (1984—)，男，河南濮陽人，博士研究生，CCF會(huì)員，主要研究方向：圖數(shù)據(jù)管理、分布式計(jì)算平臺(tái)； 索勃(1987—)，男(滿族)，遼寧錦州人，博士研究生，主要研究方向：圖數(shù)據(jù)管理； 潘巍(1978—)，男，陜西西安人，副教授，博士，CCF會(huì)員，主要研究方向：內(nèi)存計(jì)算。

1001- 9081(2017)12- 3397- 04

10.11772/j.issn.1001- 9081.2017.12.3397

(*通信作者電子郵箱wzhuo918@mail.nwpu.edu.cn)

TP311.131

A