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

1 背景

　　1.1 MapReduce和Hadoop[5]

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

　　1.2 GN算法

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

2 算法

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

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

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

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

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

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

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

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

　　2.4 第四階段：刪除邊

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

3 性能試驗

　　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實現(xiàn)SPB-MRA。在亞巴遜彈性計算（Amazon EC2）利用m1.xlarge進行性能測試。Amazon EC2是由亞馬遜公司提供的Web服務(wù)，用戶可以租用其云電腦運行時所需要的相應(yīng)系統(tǒng)。

　　3.2 可擴展性

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

　　隨著reducer的數(shù)量增加到8，所用的時間呈線性減少。對于這些數(shù)據(jù)集來說，reducer的數(shù)量是足夠的，過多的reducer就會變得無效。可以看出，CA-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平臺上得到了實現(xiàn)。在亞馬遜的EC2上進行了實例SPB-MRA性能試驗，結(jié)果表明，隨著reducer數(shù)量的增加時間呈線性減少，并且逼近值技術(shù)的錯誤率可以忽略不計。未來的工作是進一步提高SPB-MAR的性能，引入額外的近似技術(shù)。

參考文獻

　　[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.