高效的社會(huì)網(wǎng)絡(luò)傳遞性MapReduce并行計(jì)算方法*

李國(guó)慶， 程林鳳

(1.中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008;2.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院，江蘇 徐州 221008)

高效的社會(huì)網(wǎng)絡(luò)傳遞性MapReduce并行計(jì)算方法*

李國(guó)慶1,2*， 程林鳳1

(1.中國(guó)礦業(yè)大學(xué) 理學(xué)院，江蘇 徐州 221008;2.江蘇聯(lián)合職業(yè)技術(shù)學(xué)院，江蘇 徐州 221008)

社會(huì)網(wǎng)絡(luò)中的傳遞性對(duì)于網(wǎng)絡(luò)中的社團(tuán)分析和節(jié)點(diǎn)重要性分析都有著十分重要的意義.為了提高社會(huì)網(wǎng)絡(luò)傳遞性分析中三角計(jì)數(shù)的性能，提出了一種MapReduce環(huán)境下的三角計(jì)數(shù)并行計(jì)算方法.首先，將社會(huì)網(wǎng)絡(luò)的傳遞性問題轉(zhuǎn)化為計(jì)算網(wǎng)絡(luò)中三角個(gè)數(shù)的問題.其次，在計(jì)算網(wǎng)絡(luò)中的三角時(shí)按照節(jié)點(diǎn)之間的度約束對(duì)重復(fù)的三角進(jìn)行了過濾，并在MapReduce環(huán)境下實(shí)現(xiàn)了高效的三角計(jì)數(shù)并行算法.最后，分析了MapReduce環(huán)境下三角計(jì)數(shù)并行算法的時(shí)間和空間復(fù)雜性.理論分析和實(shí)驗(yàn)表明，該文提出的方法與相關(guān)方法相比，不僅降低了算法的內(nèi)存使用量，也減小了算法的運(yùn)行時(shí)間，因而更適用于大規(guī)模社會(huì)網(wǎng)絡(luò)的傳遞性分析.

社會(huì)網(wǎng)絡(luò)；三角；并行計(jì)算；聚類系數(shù)

隨著“六度分割理論”的提出，社會(huì)網(wǎng)絡(luò)引起了社會(huì)各界的廣泛關(guān)注.社會(huì)網(wǎng)絡(luò)[1]是一門與社會(huì)學(xué)、心理學(xué)、數(shù)學(xué)、計(jì)算機(jī)科學(xué)等學(xué)科相關(guān)的交差學(xué)科.社會(huì)網(wǎng)絡(luò)分析方法將社會(huì)網(wǎng)絡(luò)表示為矩陣，并用矩陣分析的方法分析社會(huì)網(wǎng)絡(luò)的相關(guān)屬性和特征[2].社會(huì)網(wǎng)絡(luò)的一個(gè)重要特征是節(jié)點(diǎn)之間往往呈現(xiàn)社團(tuán)結(jié)構(gòu)，即社團(tuán)內(nèi)部節(jié)點(diǎn)間的連接很緊密，而不同社團(tuán)節(jié)點(diǎn)之間的連接很松散.為了衡量節(jié)點(diǎn)在社團(tuán)中的重要性，研究人員提出了聚類系數(shù)[3]，即節(jié)點(diǎn)的兩個(gè)不同鄰居節(jié)點(diǎn)互為鄰居的比例.聚類系數(shù)除了可以度量節(jié)點(diǎn)在社團(tuán)中的重要性之外，還可以度量網(wǎng)絡(luò)的傳遞性[4]，進(jìn)行異常檢測(cè)[5]和基于社團(tuán)的推薦[6]等.

網(wǎng)絡(luò)的傳遞性依賴于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的度數(shù)及其聚類系數(shù).通俗的聚類系數(shù)計(jì)算方法通過迭代網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)，檢測(cè)任意兩個(gè)節(jié)點(diǎn)的連通性.該方法雖然簡(jiǎn)單，但是每個(gè)節(jié)點(diǎn)所需要的時(shí)間復(fù)雜度為節(jié)點(diǎn)度數(shù)的平方，即O(d2).由于社會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)度數(shù)往往服從冪率分布，極少數(shù)度數(shù)大的節(jié)點(diǎn)將消耗大量的計(jì)算時(shí)間，這嚴(yán)重影響了算法并行執(zhí)行的效率.為了提高算法的執(zhí)行效率，Chiba等人[7]提出了一種優(yōu)化序列算法，該算法在平面圖上的時(shí)間復(fù)雜性為O(m·α(G)).為了解決圖數(shù)據(jù)量大無法載入內(nèi)存的問題，文獻(xiàn)[8, 9]將圖數(shù)據(jù)以流的形式進(jìn)行處理，并提出了相應(yīng)的近似算法.此外，文獻(xiàn)[10～13]將網(wǎng)絡(luò)的傳遞性問題轉(zhuǎn)化為三角計(jì)數(shù)的問題，并進(jìn)行了相關(guān)的研究工作.

近些年，隨著信息技術(shù)的不斷發(fā)展，催生了大量的海量數(shù)據(jù)社會(huì)網(wǎng)絡(luò)，如WorldWideWeb、Facebook關(guān)系網(wǎng)絡(luò)、網(wǎng)頁(yè)的點(diǎn)擊紀(jì)錄網(wǎng)絡(luò)、電子商務(wù)中的用戶-商品網(wǎng)絡(luò)等.這些網(wǎng)絡(luò)通常含有數(shù)以億計(jì)的節(jié)點(diǎn)和數(shù)十億的邊，整個(gè)網(wǎng)絡(luò)規(guī)模已經(jīng)嚴(yán)重超出了個(gè)人計(jì)算機(jī)的處理能力.MapReduce[14]環(huán)境應(yīng)用大量的商業(yè)計(jì)算機(jī)通過并行計(jì)算的方式對(duì)海量的數(shù)據(jù)進(jìn)行分析，已經(jīng)成為了數(shù)據(jù)密集型計(jì)算領(lǐng)域的事實(shí)標(biāo)準(zhǔn).Hadoop[15]平臺(tái)作為MapReduce的開源實(shí)現(xiàn)，引起了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注，并取得了大量的應(yīng)用實(shí)例，如Pegasus[16]和Hadi[17].

本文研究了MapReduce環(huán)境下的社會(huì)網(wǎng)絡(luò)傳遞性問題.由于網(wǎng)絡(luò)的傳遞性與網(wǎng)絡(luò)中的三角個(gè)數(shù)相關(guān)，本文通過過濾掉重復(fù)三角的方法來提高算法的性能.在三角的過濾過程中，本文基于節(jié)點(diǎn)的度數(shù)約束，實(shí)現(xiàn)了高效的三角計(jì)數(shù)方法，從而提高了分析社會(huì)網(wǎng)絡(luò)傳遞性的性能.

1 基于MapReduce的社會(huì)網(wǎng)絡(luò)傳遞性計(jì)算

1.1 問題描述

令G=(V,E)為一個(gè)無向無權(quán)圖，其中節(jié)點(diǎn)的個(gè)數(shù)為n=|V|，邊的個(gè)數(shù)為m=|E|.節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合為N(v)={u|(u,v)∈E}，v的度數(shù)dv=|N(v)|.節(jié)點(diǎn)v的聚類系數(shù)為兩個(gè)鄰居節(jié)點(diǎn)互為鄰居的比率，可表示為如下公式：

(1)

對(duì)于任意兩條邊(u,v)∈E和(v,w)∈E，如果(u,w)∈E，那么u，v和w構(gòu)成一個(gè)三角形，這表明v此時(shí)滿足傳遞性；如果(u,w)?E，那么v此時(shí)不滿足傳遞性.因而，節(jié)點(diǎn)的傳遞性等價(jià)于節(jié)點(diǎn)的聚類系數(shù).

在圖G=(V,E)中，對(duì)于所有的節(jié)點(diǎn)三元組，并且(u,v)∈E和(v,w)∈E，如果(u,w)∈E，那么構(gòu)成一個(gè)三角形.圖G的全局傳遞性為G的所有滿足上述條件的三元組中三角形的比例，即

(2)

在公式(2)中，分子為每個(gè)節(jié)點(diǎn)為傳遞節(jié)點(diǎn)的三角形個(gè)數(shù)之和，值為圖G中的所有三角形個(gè)數(shù)的3倍，那么公式(2)可改寫為如下公式

(3)

1.2 MapReduce迭代算法

在MapReduce環(huán)境下，我們通過對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行迭代計(jì)算出每個(gè)節(jié)點(diǎn)的三角形個(gè)數(shù)，并將所有節(jié)點(diǎn)的三角形個(gè)數(shù)相加，再除以總共的三元組個(gè)數(shù)，就可以得到圖的全局傳遞性.在計(jì)算三角形個(gè)數(shù)時(shí)，對(duì)于u，v和w構(gòu)成的三角形共計(jì)算6次，其中每個(gè)節(jié)點(diǎn)為傳遞節(jié)點(diǎn)計(jì)算兩次.如果按照節(jié)點(diǎn)的度數(shù)將節(jié)點(diǎn)排序，令dv

在應(yīng)用MapReduce環(huán)境統(tǒng)計(jì)三角形的個(gè)數(shù)時(shí)，需要兩次迭代過程.第一次迭代時(shí)，采用并行方式遍歷每個(gè)節(jié)點(diǎn)生成相應(yīng)的三元組(長(zhǎng)度為2的路徑)；第二次迭代時(shí)，對(duì)每個(gè)三元組，通過掃描圖中的邊檢查該三元組的封閉性，并對(duì)三角形進(jìn)行統(tǒng)計(jì).算法的細(xì)節(jié)見算法1.

算法1. 圖的三角個(gè)數(shù)統(tǒng)計(jì)

1.Mapper1: 輸入: <(u,v),?> //圖G

2.Ifdv>du

3.Emit;

4.Else

5.Emit;

6.Reducer1: 輸入: //S?N(v)

7.Foreach(u,w)s.t.u∈S∧w∈S∧du

8.Emit;

10.If輸入類型為

11.Emit<(u,w),v>;

12.If輸入類型為 <(u,w),?>

13.Emit<(u,w),-1>;

14.Reducer2: 輸入: <(u,w),S> //S?V∪{-1}

15.If-1∈S

16.Foreachv∈S∩V

17.Emit;

在第一次迭代中，Mapper1函數(shù)按照節(jié)點(diǎn)的度數(shù)將節(jié)點(diǎn)重新排序，使得度數(shù)小的節(jié)點(diǎn)作為鍵值.MapReduce環(huán)境將具有相同鍵值的鍵/值對(duì)收集起來后，作為輸入發(fā)送到Reduce函數(shù).在Reducer1函數(shù)中，由于鍵v小于每個(gè)值，因此值的集合S為v的鄰居節(jié)點(diǎn)集合的子集.如果將所有Reducer1的輸入數(shù)據(jù)合并起來，得到的矩陣為圖G的鄰接矩陣的上三角矩陣.對(duì)于每個(gè)節(jié)點(diǎn)v，Reducer1函數(shù)將v的鄰居節(jié)點(diǎn)對(duì)作為值進(jìn)行輸出.在得到節(jié)點(diǎn)v為傳遞節(jié)點(diǎn)的三元組后，Mapper2函數(shù)將Reducer1的輸出和原圖G作為輸入進(jìn)行處理.在向系統(tǒng)存入的鍵值對(duì)中，-1表示該項(xiàng)來源于圖G.在Reducer2函數(shù)中，與鍵(u,w)對(duì)應(yīng)的值的集合S包含節(jié)點(diǎn)u和w的公共鄰居集合以及-1.當(dāng)鍵(u,w)的值集包含元素-1時(shí)，那么u、w及其公共鄰居構(gòu)成一個(gè)三角形.

在算法1中，由于限定了中心節(jié)點(diǎn)v的度數(shù)小于u和w的度數(shù)，并且u的度數(shù)小于w的度數(shù)，那么可以得到dv

(4)

1.3 理論分析

下面對(duì)算法1的時(shí)間和空間復(fù)雜性進(jìn)行理論分析.

定理1表明，在MapReduce環(huán)境中，每個(gè)機(jī)器所需要的內(nèi)存都是亞線性的，因此即使圖中節(jié)點(diǎn)的度數(shù)分布不均勻，Reducer函數(shù)也不會(huì)因數(shù)據(jù)過多而阻塞.根據(jù)定理1，可以得到如下推論.

推論1 所有Reducer1實(shí)例的輸出數(shù)據(jù)之和為O(m3/2).

在含有m條邊的圖中，推論1為該算法的最壞情況.在實(shí)際過程中，Reducer1的實(shí)際輸出數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于m3/2.在Reducer2中，對(duì)于給定的鍵(u,w)，任何一個(gè)Reducer實(shí)例的數(shù)據(jù)量至多為O(du+dw)=O(n)，因此完全可以存儲(chǔ)在機(jī)器的內(nèi)存中.

2 實(shí)驗(yàn)分析

本實(shí)驗(yàn)采用的平臺(tái)為MapReduce的開源實(shí)現(xiàn)平臺(tái)Hadoop，編程語言為Java，實(shí)驗(yàn)環(huán)境為具有20個(gè)節(jié)點(diǎn)的虛擬機(jī)集群環(huán)境.每一個(gè)節(jié)點(diǎn)含有一個(gè)2.16 GHz的英特爾酷睿雙核處理器，1 GB內(nèi)存和500 GB磁盤存儲(chǔ)空間，其運(yùn)行的操作系統(tǒng)為CentOS v6.0.

實(shí)驗(yàn)采用的數(shù)據(jù)集為L(zhǎng)iveJournal[18]和Tencent*http://www.kddcup2012.org/兩個(gè)開放的數(shù)據(jù)集，這兩個(gè)數(shù)據(jù)集均為在線社交網(wǎng)絡(luò)數(shù)據(jù)集.LiveJournal數(shù)據(jù)集包含480萬個(gè)節(jié)點(diǎn)和6 900萬條邊無向邊，Tencent數(shù)據(jù)集包含1 000萬個(gè)用戶和300萬個(gè)關(guān)注行為.在Tencent數(shù)據(jù)集中，用戶間的關(guān)注關(guān)系是有向的，我們?nèi)コ诉叺姆较?，將其視為一個(gè)無向的圖.在LiveJournal數(shù)據(jù)集中，平均聚類系數(shù)和三角個(gè)數(shù)是已知的，分別為0.312 3和2.8億.Tencent數(shù)據(jù)集的聚類系數(shù)和三角是未知的.

在實(shí)驗(yàn)結(jié)果的性能分析中，我們將本文提出的方法與文獻(xiàn)[9]的方法進(jìn)行了對(duì)比，分別對(duì)比了算法的運(yùn)行時(shí)間和內(nèi)存使用量.首先，實(shí)驗(yàn)對(duì)比了兩種算法的運(yùn)行時(shí)間.在MapReduce環(huán)境下，程序的運(yùn)行主要包括Map、Shuffle和Reduce三個(gè)過程，我們分別對(duì)比了兩種算法在這三個(gè)階段的運(yùn)行時(shí)間.圖1和圖2分別為兩種算法在不同數(shù)據(jù)集下的運(yùn)行時(shí)間對(duì)比.從這兩個(gè)圖可以看出，兩種方法在兩個(gè)數(shù)據(jù)集下有著相似的實(shí)驗(yàn)結(jié)果.在Map階段，本文提出的方法在Mapper函數(shù)中引入了兩次圖的輸入，與此同時(shí)，Reducer1階段的輸出量減少了，總的輸入數(shù)據(jù)量有少量的增加，因而算法在Mapper階段的運(yùn)行時(shí)間有少量的增加.在Shuffler和Reducer階段，由于本文采用節(jié)點(diǎn)的度數(shù)來約束三角的計(jì)數(shù)方法，過濾掉了那些重復(fù)的三角，因而算法在這兩個(gè)階段的運(yùn)行時(shí)間明顯較少.

接下來，實(shí)驗(yàn)對(duì)比了兩種方法的內(nèi)存使用量.在MapReduce環(huán)境下，Map階段用于逐行讀取數(shù)據(jù)信息，因而其內(nèi)存占用很小.MapReduce算法的內(nèi)存消耗量最大的階段為Reduce階段對(duì)具有相同鍵的值集進(jìn)行處理.在本文提出的算法中，內(nèi)存消耗量最大的階段為Reduce2函數(shù).我們對(duì)比了本文提出的算法在Reduce2函數(shù)中的內(nèi)存使用量和文獻(xiàn)[9]中的Reduce階段的內(nèi)存使用量，實(shí)驗(yàn)結(jié)果如圖3所示.從該圖可以看出，在Twitter和LiveJournal兩個(gè)數(shù)據(jù)集下，本文提出的方法的內(nèi)存使用量都明顯小于文獻(xiàn)[9].這表明，本文提出的方法占用相對(duì)較小的內(nèi)存，因而在相同的硬件環(huán)境下可以處理更大的數(shù)據(jù)集.

最后，實(shí)驗(yàn)對(duì)比了兩種算法在Reduce階段算法的運(yùn)行時(shí)間隨著節(jié)點(diǎn)度數(shù)的變化.在MapReduce環(huán)境下，算法的Shuffle時(shí)間由系統(tǒng)控制，用戶通過Mapper和Reducer函數(shù)控制算法的運(yùn)行.Mapper函數(shù)主要用于數(shù)據(jù)的讀取預(yù)處理，因而算法的運(yùn)行時(shí)間主要由Reducer函數(shù)所決定.由于實(shí)驗(yàn)結(jié)果在Tencent和LiveJournal數(shù)據(jù)集上的結(jié)果相似，我們只展示了LiveJournal數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果，見圖4.當(dāng)針對(duì)每個(gè)節(jié)點(diǎn)計(jì)算其聚類系數(shù)時(shí)，隨著節(jié)點(diǎn)度數(shù)的增大，其鄰居節(jié)點(diǎn)增多，因而鄰居節(jié)點(diǎn)對(duì)也增多，故Reducer階段的運(yùn)行時(shí)間逐漸增大.在文獻(xiàn)[9]提出的方法下，Reducer階段的運(yùn)行時(shí)間近似呈指數(shù)增長(zhǎng)，而在本文提出的方法中，Reducer階段的運(yùn)行時(shí)間近似呈線性增長(zhǎng).

綜上所述，由于本文提出的方法在三角計(jì)數(shù)上對(duì)節(jié)點(diǎn)的度數(shù)進(jìn)行了約束，過濾掉了那些重復(fù)出現(xiàn)的三角，算法在Shuffle階段無重復(fù)出現(xiàn)的三角，因而在Reducer階段的數(shù)據(jù)量大大減少了.這不僅降低了算法的內(nèi)存使用量，也減小了算法的運(yùn)行時(shí)間.

3 結(jié)束語

社會(huì)網(wǎng)絡(luò)的傳遞性研究是社會(huì)網(wǎng)絡(luò)領(lǐng)域的重要研究?jī)?nèi)容，它可以為分析社會(huì)網(wǎng)絡(luò)中的社團(tuán)和節(jié)點(diǎn)的重要性提供依據(jù).本文將社會(huì)網(wǎng)絡(luò)的傳遞性研究轉(zhuǎn)化為網(wǎng)絡(luò)中的三角計(jì)數(shù)問題.由于社會(huì)網(wǎng)絡(luò)的規(guī)模不斷增長(zhǎng)，本文采用當(dāng)前流行的并行計(jì)算環(huán)境MapReduce對(duì)三角計(jì)算進(jìn)行了分析，提出了一種MapReduce環(huán)境下的并行三角計(jì)數(shù)方法.在將社會(huì)網(wǎng)絡(luò)的傳遞性問題轉(zhuǎn)化為三角計(jì)數(shù)的問題后，提出了一種基于節(jié)點(diǎn)度數(shù)約束的三角過濾方法及相應(yīng)的MapReduce實(shí)現(xiàn)算法，并對(duì)算法的性能進(jìn)行了理論分析.理論分析和實(shí)驗(yàn)表明，本文提出的方法與相關(guān)方法相比，不僅降低了算法的內(nèi)存使用量，也減小了算法的運(yùn)行時(shí)間.

[1] 趙蓉英, 王靜. 社會(huì)網(wǎng)絡(luò)分析 (SNA) 研究熱點(diǎn)與前沿的可視化分析[J]. 圖書情報(bào)知識(shí), 2011 (1): 88-94.

[2] BURT R S, KILDUFF M, TASSELLI S. Social network analysis: foundations and frontiers on advantage[J]. Annual Review of Psychology, 2013, 64: 527-547.

[3] EGGEMANN N, NOBLE S D. The clustering coefficient of a scale-free random graph[J]. Discrete Applied Mathematics, 2011, 159(10): 953-965.

[4] REGENWETTER M, DANNA J, DAVIS-STOBER C P. Transitivity of preferences[J]. Psychological Review, 2011, 118(1): 42.

[5] CAMACHO J, MACIA-FERNANDEZ G, DIAZ-VERDEJO J, et al. Tackling the Big Data 4 vs for anomaly detection[C]// Computer Communications Workshops (INFOCOM WKSHPS), 2014 IEEE Conference on IEEE, 2014: 500-505.

[6] 陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法 [J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 349-359.

[7] CHIBA N, NISHIZEKI T. Arboricity and subgraph listing algorithms[J]. SIAM Journal on Computing, 1985, 14(1): 210-223.

[8] COPPERSMITH D, KUMAR R. An improved data stream algorithm for frequency moments[C]// Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2004: 151-156.

[9] BURIOL L S, FRAHLING G, LEONARDI S, et al. Counting triangles in data streams[C]// Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM, 2006: 253-262.

[10] LOUCH H. Personal network integration: transitivity and homophily in strong-tie relations[J]. Social Networks, 2000, 22(1): 45-64.

[11] BURDA Z, JURKIEWICZ J, KRZYWICKI A. Network transitivity and matrix models[J]. Physical Review E, 2004, 69(2): 026 106.

[12] BATJARGAL B. Network triads: transitivity, referral and venture capital decisions in China and Russia[J]. Journal of International Business Studies, 2007, 38(6): 998-1 012.

[13] BERRY M W, CHARTIER T P, HUTSON K R, et al. Identifying influential edges in a directed network: big events, upsets and non-transitivity[J]. Journal of Complex Networks, 2013，2(2)：87-109.

[14] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[15] BHANDARKAR M. Hadoop: a view from the trenches[C]// Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 1 138.

[16] DEELMAN E, SINGH G, SU M H, et al. Pegasus: A framework for mapping complex scientific workflows onto distributed systems[J]. Scientific Programming, 2005, 13(3): 219-237.

[17] TSOURAKAKIS C, APPEL A P, FALOUTSOS C, et al. HADI: Fast diameter estimation and mining in massive graphs with Hadoop[M]. Carnegie Mellon University, School of Computer Science, Machine Learning Department, 2008.

[18] LAUW H W, SHAFER J C, AGRAWAL R, et al. Homophily in the digital world: a live journal case study[J]. IEEE Internet Computing, 2010, 14(2): 15-23.

責(zé)任編輯：龍順潮

Efficient Transitivity Computing of Social Networks in MapReduce

LIGuo-qing1，2*,CHENGLin-feng1

(1.College of Science,China University of Mining and Technology，Xuzhou 221008；2.Jiangsu Union Technical Institute,Xuzhou 221008 China)

Research on transitivity of social networks is very important for analysis of community and node importance in social networks. In order to improve the performance of triangle counting for analyzing network transitivity, this paper proposed a parallel triangle counting algorithm in MapReduce environment. Firstly, we transformed the problem of network transitivity into the counting of triangles in a network. Secondly, while computing triangles in a network, we removed repeated triangles according to the degree constraint of nodes in a triangle, and implemented an efficient parallel triangle counting algorithm in MapReduce. Finally, we analyzed the time and space complexity of the proposed algorithm. Theoretical analysis and the experiments show that, our proposed approach has less memory usage and execution time compared with related work, and thus is more suitable for analyzing network transitivity for large-scale social networks.

social networks; triangle; parallel computing; clustering coefficient

2014-11-07

江蘇省教育教學(xué)改革立項(xiàng)重點(diǎn)課題項(xiàng)目(蘇教科院ZCZ32)

李國(guó)慶(1966— ),男，江蘇 徐州人，副教授.E-mail:xzcxlgq@126.com

TP311

A

1000-5900(2015)02-0102-06