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

　　關鍵詞： Hadoop；MapReduce；社區檢測；GN算法；SPB-MRA

0 引言

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

1 背景

　　1.1 MapReduce和Hadoop[5]

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

　　1.2 GN算法

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

2 算法

　　SPB-MRA經歷了4個并行計算的階段，每個階段執行自己的map和reduce任務。在每次迭代中，第一階段會執行多次，而其他階段只執行一次。運行這4個階段直到結果的質量不再有所改進。在社團發現中每對節點由7個元素組成的元組構成，元組中包含網絡結構（例如鄰接表），這時最短路徑通過元組獲得。

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

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

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

　　2.2 第二階段：計算邊界數

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

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

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

　　2.4 第四階段：刪除邊

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

3 性能試驗

　　3.1 數據和環境

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

　　3.2 可擴展性

　　為了顯示SPA-MRA的可擴展性，經過一次迭代的同時reducer的數量從1變為32，結果如圖6和圖7所示。

　　隨著reducer的數量增加到8，所用的時間呈線性減少。對于這些數據集來說，reducer的數量是足夠的，過多的reducer就會變得無效。可以看出，CA-HepTh數據集的大小是CA-GrQc數據集的兩倍，而圖7中的曲線要比圖6中的曲線率先變得平緩。

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

4 結論

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

參考文獻

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