李國慶， 程林鳳

(1.中國礦業(yè)大學 理學院，江蘇 徐州 221008;2.江蘇聯合職業(yè)技術學院，江蘇 徐州 221008)

高效的社會網絡傳遞性MapReduce并行計算方法*

李國慶1,2*， 程林鳳1

(1.中國礦業(yè)大學 理學院，江蘇 徐州 221008;2.江蘇聯合職業(yè)技術學院，江蘇 徐州 221008)

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

社會網絡；三角；并行計算；聚類系數

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

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

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

本文研究了MapReduce環(huán)境下的社會網絡傳遞性問題.由于網絡的傳遞性與網絡中的三角個數相關，本文通過過濾掉重復三角的方法來提高算法的性能.在三角的過濾過程中，本文基于節(jié)點的度數約束，實現了高效的三角計數方法，從而提高了分析社會網絡傳遞性的性能.

1 基于MapReduce的社會網絡傳遞性計算

1.1 問題描述

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

(1)

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

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

(2)

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

(3)

1.2 MapReduce迭代算法

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

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

算法1. 圖的三角個數統計

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

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

(4)

1.3 理論分析

下面對算法1的時間和空間復雜性進行理論分析.

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

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

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

2 實驗分析

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

實驗采用的數據集為LiveJournal[18]和Tencent*http://www.kddcup2012.org/兩個開放的數據集，這兩個數據集均為在線社交網絡數據集.LiveJournal數據集包含480萬個節(jié)點和6 900萬條邊無向邊，Tencent數據集包含1 000萬個用戶和300萬個關注行為.在Tencent數據集中，用戶間的關注關系是有向的，我們去除了邊的方向，將其視為一個無向的圖.在LiveJournal數據集中，平均聚類系數和三角個數是已知的，分別為0.312 3和2.8億.Tencent數據集的聚類系數和三角是未知的.

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

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

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

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

3 結束語

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

[1] 趙蓉英, 王靜. 社會網絡分析 (SNA) 研究熱點與前沿的可視化分析[J]. 圖書情報知識, 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] 陳克寒, 韓盼盼, 吳健. 基于用戶聚類的異構社交網絡推薦算法 [J]. 計算機學報, 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.

責任編輯：龍順潮

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

江蘇省教育教學改革立項重點課題項目(蘇教科院ZCZ32)

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

TP311

A

1000-5900(2015)02-0102-06