摘 要： 隨著社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的增加，社團(tuán)發(fā)現(xiàn)獲得來(lái)自學(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ò)中每對(duì)節(jié)點(diǎn)之間的最短路徑而產(chǎn)生了相應(yīng)的局限性。為此，利用MapReduce模型，提出了一種并行版本的GN算法來(lái)支持大規(guī)模網(wǎng)絡(luò)的新方法，稱之為最短路徑之間的MapReduce算法（Shortest Path Betweenness MapReduce Algorithm，SPB-MRA）。此外，還提出了一個(gè)近似技術(shù)，進(jìn)一步加快社區(qū)檢測(cè)過(guò)程。在Hadoop上利用開(kāi)源平臺(tái)MapReduce框架實(shí)現(xiàn)了SPB-MRA算法。結(jié)果表明，隨著reducer數(shù)量的增加時(shí)間呈線性減小，并且引入了一種近似技術(shù)可以忽略誤差。
關(guān)鍵詞： Hadoop；MapReduce；社區(qū)檢測(cè)；GN算法；SPB-MRA
0 引言
社會(huì)網(wǎng)絡(luò)服務(wù)（SNS網(wǎng)站），如Facebook和Twitter，在實(shí)際生活中變得越來(lái)越流行。因此分析社會(huì)網(wǎng)絡(luò)數(shù)據(jù)就成為各領(lǐng)域面對(duì)的最重要的問(wèn)題之一。在這些分析工作中，社會(huì)網(wǎng)絡(luò)數(shù)據(jù)的社團(tuán)發(fā)現(xiàn)在社會(huì)生活中有著實(shí)際的應(yīng)用，因此獲得來(lái)自學(xué)術(shù)界和各行業(yè)的廣泛關(guān)注。由格文和紐曼[1]提出格文-紐曼（GN）算法引入邊介數(shù)的概念，用來(lái)衡量中心性和網(wǎng)絡(luò)中邊緣的影響度。雖然GN算法被廣泛應(yīng)用，但當(dāng)它支持大型網(wǎng)絡(luò)時(shí)，由于需要計(jì)算每對(duì)節(jié)點(diǎn)之間的最短路徑而具有局限性，而且節(jié)點(diǎn)對(duì)的數(shù)量也是有限制的。在大數(shù)據(jù)時(shí)代，可用的數(shù)據(jù)量空前增長(zhǎng)，因此，數(shù)據(jù)分析是一種良好的可擴(kuò)展方法，可以用來(lái)處理大型數(shù)據(jù)集。MapReduce是一個(gè)用于處理大數(shù)據(jù)集的并行編程模型，分布式聚類算法在MapReduce中可擴(kuò)展性和易于使用的性質(zhì)[2-4]而得到廣泛的應(yīng)用，這也是近年來(lái)在背后驅(qū)動(dòng)分析大數(shù)據(jù)的動(dòng)力。本文提出了一個(gè)并行版本的GN算法，即SPB-MRA算法來(lái)支持大規(guī)模的網(wǎng)絡(luò)，并且提出了一種近似技術(shù)來(lái)進(jìn)一步加快社區(qū)檢測(cè)過(guò)程。
1 背景
1.1 MapReduce和Hadoop[5]
MapReduce并行的方式是一個(gè)加工大規(guī)模數(shù)據(jù)的編程模型[2]。用戶可以輕松地通過(guò)編寫map和reduce兩個(gè)函數(shù)實(shí)現(xiàn)分布式并行處理的功能。map函數(shù)處理數(shù)據(jù)輸入和鍵值對(duì)<key，value>，reduce函數(shù)是把具有相同key的value值進(jìn)行合并后輸出。
1.2 GN算法
GN算法是分裂的分層聚類算法，利用邊界數(shù)[1]的概念。在提出的三種計(jì)算邊界數(shù)的方法中計(jì)算最短路徑的結(jié)果是最好的。邊界數(shù)是指經(jīng)過(guò)兩個(gè)節(jié)點(diǎn)之間的最短距離的值。由于社團(tuán)是由一些“組間”邊界松散地鏈接而成的，在不同社團(tuán)之間所有最短路都必須經(jīng)過(guò)這些“組間”邊，這些邊連接起來(lái)的社團(tuán)的邊界數(shù)將會(huì)很大，因此，社團(tuán)可以通過(guò)不斷檢測(cè)來(lái)排除這些邊。從每對(duì)節(jié)點(diǎn)中最獲得最短路徑，所以GN算法的代價(jià)是非常高的。
2 算法
SPB-MRA經(jīng)歷了4個(gè)并行計(jì)算的階段，每個(gè)階段執(zhí)行自己的map和reduce任務(wù)。在每次迭代中，第一階段會(huì)執(zhí)行多次，而其他階段只執(zhí)行一次。運(yùn)行這4個(gè)階段直到結(jié)果的質(zhì)量不再有所改進(jìn)。在社團(tuán)發(fā)現(xiàn)中每對(duì)節(jié)點(diǎn)由7個(gè)元素組成的元組構(gòu)成，元組中包含網(wǎng)絡(luò)結(jié)構(gòu)（例如鄰接表），這時(shí)最短路徑通過(guò)元組獲得。
targetid表示一個(gè)目的節(jié)點(diǎn)的最短路徑且最初設(shè)置為sourceid。sourceid表示最短路徑源節(jié)點(diǎn)且最初設(shè)置為targetid。distance表示最短路徑的長(zhǎng)度，初值為0，每次迭代過(guò)程中更新第一階段的distance值。status表示一個(gè)特定的路徑的狀態(tài)。a表示積極的（active）；i表示不積極的（inactive），意味著最短的路徑已檢測(cè)到。weight表示從sourceid到targetid最短路徑的數(shù)目且最初設(shè)置為1。pathinfo表示最短路徑經(jīng)過(guò)的節(jié)點(diǎn)的列表，初始值為空。adjlist表示targetid中相鄰的節(jié)點(diǎn)的列表。
2.1 第一階段：找到所有節(jié)點(diǎn)對(duì)之間的最短路徑
在第一階段，采取Zeng Zengfeng等人[6]提出的由一種多源消息傳遞模型的方法來(lái)計(jì)算每對(duì)節(jié)點(diǎn)之間的最短路徑。在map階段中輸入一個(gè)元組，若它的status是i，無(wú)需后續(xù)操作；若status是a，則改成i，距離加1并將targetid增加到pathinfo中；該元組被送到reduce階段。通過(guò)給在鄰接表中的每個(gè)點(diǎn)分配targetid即可生成新的元組。這些新生成的元組其status被設(shè)置為a，鄰接表被設(shè)置為空，并且其他元素被設(shè)定為那些發(fā)送前的元組的狀態(tài)，如圖1所示。
2.2 第二階段：計(jì)算邊界數(shù)
在第二階段，計(jì)算網(wǎng)絡(luò)中每對(duì)節(jié)點(diǎn)之間的邊界數(shù)。在map階段，整體根據(jù)最短路徑的sourceid和targerid的數(shù)目（即權(quán)重）被劃分成某條最短路徑上的邊。在reduce階段，每個(gè)邊由每個(gè)最短路徑的分量相加得到，如圖2所示。
2.3 第三階段：選擇要?jiǎng)h除的邊緣
在第三階段，kiter邊按邊界數(shù)選擇。kiter是由用戶作為調(diào)節(jié)參數(shù)而指定的。在map階段，不需要進(jìn)行后續(xù)操作。在reduce階段，邊按照邊界數(shù)的遞減順序排序，并且top-kiter邊緣被選定。只要運(yùn)行一個(gè)reducer即可得到一個(gè)整體的排序結(jié)果，如圖3所示。
2.4 第四階段：刪除邊
在第四階段，把網(wǎng)絡(luò)中在第三階段選擇的邊刪除，但在下一次迭代中，一個(gè)新的元組集合的生成表明需要重新計(jì)算刪除邊的邊界數(shù)。注意，如果一個(gè)最短路徑包含被去除邊，邊界值就會(huì)改變，那么邊界數(shù)將會(huì)發(fā)生變化。在map階段，如果第二階段分組中的targetid影響到第三階段邊緣的選擇，如果刪除相應(yīng)節(jié)點(diǎn)來(lái)表示新的網(wǎng)絡(luò)結(jié)構(gòu)，則它的鄰接表就會(huì)更新，其他的元組在下一次迭代中初始化，如圖4所示。在reduce階段，在鄰接表里的元組都會(huì)有一個(gè)更新的值，這些元組將作為下一次第一階段中的輸入而提供數(shù)據(jù)，如圖5所示。
3 性能試驗(yàn)
3.1 數(shù)據(jù)和環(huán)境
采用來(lái)自于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)行性能測(cè)試。Amazon EC2是由亞馬遜公司提供的Web服務(wù)，用戶可以租用其云電腦運(yùn)行時(shí)所需要的相應(yīng)系統(tǒng)。
3.2 可擴(kuò)展性
為了顯示SPA-MRA的可擴(kuò)展性，經(jīng)過(guò)一次迭代的同時(shí)reducer的數(shù)量從1變?yōu)?2，結(jié)果如圖6和圖7所示。
隨著reducer的數(shù)量增加到8，所用的時(shí)間呈線性減少。對(duì)于這些數(shù)據(jù)集來(lái)說(shuō)，reducer的數(shù)量是足夠的，過(guò)多的reducer就會(huì)變得無(wú)效。可以看出，CA-HepTh數(shù)據(jù)集的大小是CA-GrQc數(shù)據(jù)集的兩倍，而圖7中的曲線要比圖6中的曲線率先變得平緩。
為了顯示SPA-MRA近似值的精度，在不同的kiter值下測(cè)量F-score[8]的值，如表1所示。其中，kiter表示一次迭代中要?jiǎng)h除邊緣的數(shù)量。在表1中，雖然一次性刪除40條邊F-score值只減少了10%，但是它證明4次提速卻只有10%的誤差。
4 結(jié)論
本文提出了一個(gè)并行版本的GN算法即SPB-MRA來(lái)支持大規(guī)模的網(wǎng)絡(luò)，并利用MapReduce模型在Hadoop平臺(tái)上得到了實(shí)現(xiàn)。在亞馬遜的EC2上進(jìn)行了實(shí)例SPB-MRA性能試驗(yàn)，結(jié)果表明，隨著reducer數(shù)量的增加時(shí)間呈線性減少，并且逼近值技術(shù)的錯(cuò)誤率可以忽略不計(jì)。未來(lái)的工作是進(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.