摘  要： 隨著社會網(wǎng)絡(luò)數(shù)據(jù)的增加,，社團(tuán)發(fā)現(xiàn)獲得來自學(xué)術(shù)界和工業(yè)界的大量關(guān)注，是因?yàn)樗诂F(xiàn)實(shí)世界中有許多的實(shí)際應(yīng)用,。格文-紐曼（Girvan-Newman,，GN）是現(xiàn)今最流行的算法之一，但在大型網(wǎng)絡(luò)上由于需要計(jì)算網(wǎng)絡(luò)中每對節(jié)點(diǎn)之間的最短路徑而產(chǎn)生了相應(yīng)的局限性,。為此,，利用MapReduce模型，提出了一種并行版本的GN算法來支持大規(guī)模網(wǎng)絡(luò)的新方法，稱之為最短路徑之間的MapReduce算法（Shortest Path Betweenness MapReduce Algorithm,，SPB-MRA）,。此外，還提出了一個近似技術(shù),，進(jìn)一步加快社區(qū)檢測過程,。在Hadoop上利用開源平臺MapReduce框架實(shí)現(xiàn)了SPB-MRA算法。結(jié)果表明,，隨著reducer數(shù)量的增加時間呈線性減小,，并且引入了一種近似技術(shù)可以忽略誤差。

　　關(guān)鍵詞： Hadoop,；MapReduce,；社區(qū)檢測；GN算法,；SPB-MRA

0 引言

　　社會網(wǎng)絡(luò)服務(wù)（SNS網(wǎng)站）,，如Facebook和Twitter，在實(shí)際生活中變得越來越流行,。因此分析社會網(wǎng)絡(luò)數(shù)據(jù)就成為各領(lǐng)域面對的最重要的問題之一,。在這些分析工作中，社會網(wǎng)絡(luò)數(shù)據(jù)的社團(tuán)發(fā)現(xiàn)在社會生活中有著實(shí)際的應(yīng)用,，因此獲得來自學(xué)術(shù)界和各行業(yè)的廣泛關(guān)注,。由格文和紐曼[1]提出格文-紐曼（GN）算法引入邊介數(shù)的概念，用來衡量中心性和網(wǎng)絡(luò)中邊緣的影響度,。雖然GN算法被廣泛應(yīng)用，但當(dāng)它支持大型網(wǎng)絡(luò)時,，由于需要計(jì)算每對節(jié)點(diǎn)之間的最短路徑而具有局限性,，而且節(jié)點(diǎn)對的數(shù)量也是有限制的。在大數(shù)據(jù)時代,，可用的數(shù)據(jù)量空前增長,，因此，數(shù)據(jù)分析是一種良好的可擴(kuò)展方法,，可以用來處理大型數(shù)據(jù)集,。MapReduce是一個用于處理大數(shù)據(jù)集的并行編程模型，分布式聚類算法在MapReduce中可擴(kuò)展性和易于使用的性質(zhì)[2-4]而得到廣泛的應(yīng)用,，這也是近年來在背后驅(qū)動分析大數(shù)據(jù)的動力,。本文提出了一個并行版本的GN算法，即SPB-MRA算法來支持大規(guī)模的網(wǎng)絡(luò),，并且提出了一種近似技術(shù)來進(jìn)一步加快社區(qū)檢測過程,。

1 背景

　　1.1 MapReduce和Hadoop[5]

　　MapReduce并行的方式是一個加工大規(guī)模數(shù)據(jù)的編程模型[2]。用戶可以輕松地通過編寫map和reduce兩個函數(shù)實(shí)現(xiàn)分布式并行處理的功能。map函數(shù)處理數(shù)據(jù)輸入和鍵值對<key,，value>,，reduce函數(shù)是把具有相同key的value值進(jìn)行合并后輸出。

　　1.2 GN算法

　　GN算法是分裂的分層聚類算法,，利用邊界數(shù)[1]的概念,。在提出的三種計(jì)算邊界數(shù)的方法中計(jì)算最短路徑的結(jié)果是最好的。邊界數(shù)是指經(jīng)過兩個節(jié)點(diǎn)之間的最短距離的值,。由于社團(tuán)是由一些“組間”邊界松散地鏈接而成的,，在不同社團(tuán)之間所有最短路都必須經(jīng)過這些“組間”邊，這些邊連接起來的社團(tuán)的邊界數(shù)將會很大,，因此,，社團(tuán)可以通過不斷檢測來排除這些邊。從每對節(jié)點(diǎn)中最獲得最短路徑,，所以GN算法的代價(jià)是非常高的,。

2 算法

　　SPB-MRA經(jīng)歷了4個并行計(jì)算的階段，每個階段執(zhí)行自己的map和reduce任務(wù),。在每次迭代中,，第一階段會執(zhí)行多次，而其他階段只執(zhí)行一次,。運(yùn)行這4個階段直到結(jié)果的質(zhì)量不再有所改進(jìn),。在社團(tuán)發(fā)現(xiàn)中每對節(jié)點(diǎn)由7個元素組成的元組構(gòu)成，元組中包含網(wǎng)絡(luò)結(jié)構(gòu)（例如鄰接表）,，這時最短路徑通過元組獲得,。

　　targetid表示一個目的節(jié)點(diǎn)的最短路徑且最初設(shè)置為sourceid。sourceid表示最短路徑源節(jié)點(diǎn)且最初設(shè)置為targetid,。distance表示最短路徑的長度,，初值為0，每次迭代過程中更新第一階段的distance值,。status表示一個特定的路徑的狀態(tài),。a表示積極的（active）；i表示不積極的（inactive）,，意味著最短的路徑已檢測到,。weight表示從sourceid到targetid最短路徑的數(shù)目且最初設(shè)置為1。pathinfo表示最短路徑經(jīng)過的節(jié)點(diǎn)的列表,，初始值為空,。adjlist表示targetid中相鄰的節(jié)點(diǎn)的列表。

　　2.1 第一階段：找到所有節(jié)點(diǎn)對之間的最短路徑

　　在第一階段,，采取Zeng Zengfeng等人[6]提出的由一種多源消息傳遞模型的方法來計(jì)算每對節(jié)點(diǎn)之間的最短路徑,。在map階段中輸入一個元組,，若它的status是i，無需后續(xù)操作,；若status是a,，則改成i，距離加1并將targetid增加到pathinfo中,；該元組被送到reduce階段,。通過給在鄰接表中的每個點(diǎn)分配targetid即可生成新的元組。這些新生成的元組其status被設(shè)置為a,，鄰接表被設(shè)置為空,，并且其他元素被設(shè)定為那些發(fā)送前的元組的狀態(tài)，如圖1所示,。

　　2.2 第二階段：計(jì)算邊界數(shù)

　　在第二階段,，計(jì)算網(wǎng)絡(luò)中每對節(jié)點(diǎn)之間的邊界數(shù)。在map階段,，整體根據(jù)最短路徑的sourceid和targerid的數(shù)目（即權(quán)重）被劃分成某條最短路徑上的邊,。在reduce階段，每個邊由每個最短路徑的分量相加得到,，如圖2所示,。

　　2.3 第三階段：選擇要刪除的邊緣

　　在第三階段，kiter邊按邊界數(shù)選擇,。kiter是由用戶作為調(diào)節(jié)參數(shù)而指定的,。在map階段，不需要進(jìn)行后續(xù)操作,。在reduce階段,，邊按照邊界數(shù)的遞減順序排序，并且top-kiter邊緣被選定,。只要運(yùn)行一個reducer即可得到一個整體的排序結(jié)果,，如圖3所示。

　　2.4 第四階段：刪除邊

　　在第四階段,，把網(wǎng)絡(luò)中在第三階段選擇的邊刪除，但在下一次迭代中,，一個新的元組集合的生成表明需要重新計(jì)算刪除邊的邊界數(shù),。注意，如果一個最短路徑包含被去除邊,，邊界值就會改變,，那么邊界數(shù)將會發(fā)生變化。在map階段,，如果第二階段分組中的targetid影響到第三階段邊緣的選擇,，如果刪除相應(yīng)節(jié)點(diǎn)來表示新的網(wǎng)絡(luò)結(jié)構(gòu),，則它的鄰接表就會更新，其他的元組在下一次迭代中初始化,，如圖4所示,。在reduce階段，在鄰接表里的元組都會有一個更新的值,，這些元組將作為下一次第一階段中的輸入而提供數(shù)據(jù),，如圖5所示。

3 性能試驗(yàn)

　　3.1 數(shù)據(jù)和環(huán)境

　　采用來自于Stanford Large Network Dataset Collection[7]上的ca-GrQc和ca-HepTH兩組數(shù)據(jù)集,，使用Java 1.6.0和Hadoop 1.0.4實(shí)現(xiàn)SPB-MRA,。在亞巴遜彈性計(jì)算（Amazon EC2）利用m1.xlarge進(jìn)行性能測試。Amazon EC2是由亞馬遜公司提供的Web服務(wù),，用戶可以租用其云電腦運(yùn)行時所需要的相應(yīng)系統(tǒng),。

　　3.2 可擴(kuò)展性

　　為了顯示SPA-MRA的可擴(kuò)展性，經(jīng)過一次迭代的同時reducer的數(shù)量從1變?yōu)?2,，結(jié)果如圖6和圖7所示,。

　　隨著reducer的數(shù)量增加到8，所用的時間呈線性減少,。對于這些數(shù)據(jù)集來說,，reducer的數(shù)量是足夠的，過多的reducer就會變得無效,?？梢钥闯觯珻A-HepTh數(shù)據(jù)集的大小是CA-GrQc數(shù)據(jù)集的兩倍,，而圖7中的曲線要比圖6中的曲線率先變得平緩,。

　　為了顯示SPA-MRA近似值的精度，在不同的kiter值下測量F-score[8]的值,，如表1所示,。其中，kiter表示一次迭代中要刪除邊緣的數(shù)量,。在表1中,，雖然一次性刪除40條邊F-score值只減少了10%，但是它證明4次提速卻只有10%的誤差,。

4 結(jié)論

　　本文提出了一個并行版本的GN算法即SPB-MRA來支持大規(guī)模的網(wǎng)絡(luò),，并利用MapReduce模型在Hadoop平臺上得到了實(shí)現(xiàn)。在亞馬遜的EC2上進(jìn)行了實(shí)例SPB-MRA性能試驗(yàn),，結(jié)果表明,，隨著reducer數(shù)量的增加時間呈線性減少，并且逼近值技術(shù)的錯誤率可以忽略不計(jì),。未來的工作是進(jìn)一步提高SPB-MAR的性能,，引入額外的近似技術(shù),。

參考文獻(xiàn)

　　[1] NEWMAN M E， GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E,， 2004,，69（2）：026113-1-026113-15.

　　[2] DEAN J， GHEMAWAT S. MapReduce： simplified data processing on large clusters[C]. Communications of the ACM,， 2008,，51（1）：107-113.

　　[3] CHAIKEN R， JENKINS B,，  LARSON P.-A°,， et al. Scope： easy and efficient parallel processing of massive data sets[C].Proceedings of the VLDB Endowment， 2008,，1（2）：1265-1276.

　　[4] COHEN J,， DOLAN B， DUNLAP M,， et al. Mad skills： new analysis practices for big data[C]. Proceedings of the VLDB Endowment,， 2009，2（2）：1481-1492.

　　[5] Hadoop Apache. Software Foundation.(2013-08-01）[2014-07-01].http：//hadoop.apache.org.

　　[6] Zeng Zengfeng,， Wu Bin,， Zhang Tiantian. A multi-source message passing model to improve the parallelism efficiency of graph mining on MapReduce[C]. Proceedings of 2012 IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum（IPDPSW），2012：2019-2025.

　　[7] Stanford large network dataset collection[EB/OL].[2013-08-01]. http：//snap. stanford.edu/data.

　　[8] Han Jiamei,， KAMBER M,， Pei Jian. Data mining： concepts and techniques（2nd edition）. Morgan Kaufmann， 2006.