MapReduce背景下的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)分析

常雅文

(西安航空學(xué)院， 西安 710077)

0 引言

復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)由于在社交網(wǎng)絡(luò)、信息通信等社會(huì)方面的廣泛應(yīng)用，現(xiàn)已成為數(shù)據(jù)挖掘的主要研究方向，已成為學(xué)術(shù)界關(guān)注的熱點(diǎn)[1]。網(wǎng)絡(luò)鏈路預(yù)測(cè)作為一種預(yù)測(cè)方式主要是通過(guò)已知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)節(jié)點(diǎn)屬性等信息預(yù)測(cè)網(wǎng)絡(luò)中未產(chǎn)生連邊的節(jié)點(diǎn)產(chǎn)生連接的可能性[2]。傳統(tǒng)的鏈路預(yù)測(cè)算法以節(jié)點(diǎn)屬性為特點(diǎn)，譬如馬爾科夫鏈或機(jī)械學(xué)習(xí)等算法，盡管算法預(yù)測(cè)精度高，但由于計(jì)算復(fù)雜度高、計(jì)算中涉及的非普適性參數(shù)應(yīng)用的限制，導(dǎo)致算法使用受限[3-4]。另一類傳統(tǒng)鏈路算法則以網(wǎng)絡(luò)結(jié)構(gòu)為特點(diǎn)進(jìn)行最大似然估計(jì)，文獻(xiàn)[5]中介紹了一種網(wǎng)絡(luò)層次結(jié)構(gòu)為基礎(chǔ)的鏈路預(yù)測(cè)算法，并顯示該類算法在層次結(jié)構(gòu)明顯的網(wǎng)絡(luò)中具有較高的預(yù)測(cè)精度，但該類算法的計(jì)算復(fù)雜度高。

與傳統(tǒng)的鏈路預(yù)測(cè)算法相比，以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)的鏈路預(yù)測(cè)算法通用性強(qiáng)，且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)極易獲得。但在處理大規(guī)模復(fù)雜網(wǎng)絡(luò)鏈路時(shí)，由于算法復(fù)雜度和單臺(tái)計(jì)算機(jī)內(nèi)存限制，處理速度慢，且準(zhǔn)確性不足。MapReduce[6]作為Google公司2004年提出的可以并行處理海量數(shù)據(jù)的編程模式和任務(wù)調(diào)度模式，可以通過(guò)屏蔽底層實(shí)現(xiàn)細(xì)節(jié)減少并行編程復(fù)雜度，提高編程效率而具有廣泛應(yīng)用。基于MapReduce編程時(shí)，開(kāi)發(fā)人員只要考慮應(yīng)用程序本身特性，無(wú)需考慮集群處理，將其交由平臺(tái)處理。因此在MapReduce背景下進(jìn)行復(fù)制網(wǎng)絡(luò)鏈路預(yù)測(cè)分析具有重要的使用價(jià)值和意義。由于MapReduce模型并不允許任意讀取圖中的節(jié)點(diǎn)以及邊信息，因此本文基于節(jié)點(diǎn)局部信息的相似性指標(biāo)進(jìn)行復(fù)制鏈路預(yù)測(cè)分析。

1 MapReduce背景下的復(fù)雜鏈路預(yù)測(cè)算法

1.1 問(wèn)題描述

記G(V,E)為一個(gè)無(wú)向網(wǎng)絡(luò)，其中V和E分別代表節(jié)點(diǎn)集合和邊集合。總的節(jié)點(diǎn)記為數(shù)為N，則節(jié)點(diǎn)對(duì)數(shù)為U=N(N-1)/2。對(duì)于兩個(gè)節(jié)點(diǎn)，在相似性框架下，其產(chǎn)生鏈接的可能性與相似程度成正比，即相似程度越高，產(chǎn)生鏈接的可能性越大。同樣，給定度量節(jié)點(diǎn)相似性指標(biāo)，則復(fù)雜鏈路預(yù)測(cè)問(wèn)題會(huì)轉(zhuǎn)變成為一個(gè)無(wú)監(jiān)督學(xué)習(xí)問(wèn)題，即：對(duì)于給定的網(wǎng)絡(luò)數(shù)據(jù)集G，依據(jù)相似性指標(biāo)計(jì)算獲得網(wǎng)絡(luò)中每?jī)蓚€(gè)節(jié)點(diǎn)間的相似值，行程相似矩陣，依照相似值排序，獲得兩節(jié)點(diǎn)間產(chǎn)生鏈接的概率排序。本文定義的相似性鏈路預(yù)測(cè)在度量節(jié)點(diǎn)的相似性時(shí)，主要從網(wǎng)絡(luò)本身拓?fù)浣Y(jié)構(gòu)出發(fā)分析，未考慮其他由于網(wǎng)絡(luò)特殊性，譬如社交網(wǎng)絡(luò)中表示節(jié)點(diǎn)擁有用戶個(gè)性化興趣等，造成的節(jié)點(diǎn)自身屬性，這也是本文問(wèn)題描述與其他有監(jiān)督學(xué)習(xí)方法的區(qū)別。

以局部信息為基礎(chǔ)的鏈路預(yù)測(cè)算法有10種，具體相似性指標(biāo)定義公式，如表1所示[7]。

表1 基于節(jié)點(diǎn)信息的10種相似性指標(biāo)

網(wǎng)絡(luò)節(jié)點(diǎn)表示為x，其節(jié)點(diǎn)的鄰居表示為Γ(x)，而k(x)=|Γ(x)|則代表節(jié)點(diǎn)的度，Sxy則代表點(diǎn)對(duì)(x,y)的相似性。相對(duì)于另外9種指標(biāo)，PA指標(biāo)不包含共同鄰居信息，為保證信息一致性，本文只考慮代表的指標(biāo)CN、RA和AA。

1.2 MapReduce 并行計(jì)算模型

目前關(guān)于MapReduce并行鏈路預(yù)測(cè)算法的應(yīng)用，主要在Hadoop平臺(tái)[8]上進(jìn)行。Hadoop屬于分布式系統(tǒng)平臺(tái)，包括分布式文件系統(tǒng)HFDS以及核心算法MapReduce。MapReduce包括兩個(gè)階段，即：Map階段和Reduce階段。Hadoop首先進(jìn)行輸入數(shù)據(jù)分片，將其形成多個(gè)小數(shù)據(jù)塊，然后Map執(zhí)行相關(guān)任務(wù)，Reduce則執(zhí)行將Map階段獲得中間結(jié)果匯總輸出。具體執(zhí)行過(guò)程，如圖1所示。

圖1 具有多reducer任務(wù)的MapReduce數(shù)據(jù)流

(1) 預(yù)處理：MapReduce首先調(diào)用類庫(kù)，將輸入文件等大小(64MB)劃分幾個(gè)分片；

(2) 分配任務(wù)：JobTracker(負(fù)責(zé)對(duì)整個(gè)作業(yè)執(zhí)行進(jìn)行調(diào)度，一個(gè)集群只含有一個(gè))為集群中空閑節(jié)點(diǎn)分配Map或Reduce任務(wù)；

(3) Map任務(wù)：Mapper讀取文件分片，并轉(zhuǎn)換成鍵值對(duì)，利用map函數(shù)進(jìn)行計(jì)算，獲得新鍵值對(duì)作為中間結(jié)果，緩存到當(dāng)前節(jié)點(diǎn)內(nèi)存；

(4) 確定緩存文件位置：周期性的將中間結(jié)果寫入Mapper對(duì)應(yīng)的本地硬盤，并將存儲(chǔ)地點(diǎn)發(fā)送給Reducer；

(5) 利用Reducer獲得Mapper拉取文件：利用位置信息，得到Mapper處拉取的文件。當(dāng)所有臨時(shí)結(jié)果被讀取完畢，將所有相同key中所有value合并成一個(gè)組，獲得鍵值對(duì)；

(6) Reduce任務(wù)：Reducer將所獲得的鍵值對(duì)進(jìn)行reduce運(yùn)算，獲得最終結(jié)果并將其輸出；

(7) 結(jié)束：當(dāng)所有Map和Reduce運(yùn)行完畢后，系統(tǒng)會(huì)通知用戶并進(jìn)行信息報(bào)告。

1.3 利用MapReduce 分析復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)

利用MapReduce并行計(jì)算模型實(shí)現(xiàn)排除基于節(jié)點(diǎn)局部信息的CN、AA、RA相似性指標(biāo)，這3種指標(biāo)應(yīng)用到了節(jié)點(diǎn)的共同鄰居信息，因此，在并行算法上具有一致性，基于MapReduce并行計(jì)算模型的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)算法步驟如下：

輸入：G(V,E)的邊集E(文件A)；

輸出：AUC值(曲線下面積，通過(guò)AUC超過(guò)0.5的大小衡量鏈路預(yù)測(cè)算法的準(zhǔn)確性)。

步驟一：得到網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N，并將網(wǎng)絡(luò)邊集E分割形成訓(xùn)練集ET(文件B)和測(cè)試集EP(文件C)。

步驟二：獲得ET和EP中邊個(gè)數(shù)，獲得ET中所有節(jié)點(diǎn)度。

步驟三：將ET中點(diǎn)對(duì)用鄰接表表示；

步驟四：對(duì)于ET的鄰接表，利用相似性指標(biāo)獲得兩兩點(diǎn)對(duì)的預(yù)測(cè)分?jǐn)?shù)值(文件D)；

(1)

對(duì)于步驟四種中利用相似性指標(biāo)獲得兩兩點(diǎn)對(duì)的預(yù)測(cè)分?jǐn)?shù)值的方法如下。

Mapper

輸入：圖G(V,E)的鄰接表；

輸出：圖G(V,E)兩兩點(diǎn)對(duì)之間的共同鄰居。

具體流程圖，如圖2所示。

圖2 Mapper流程圖

Reducer

輸入：圖G(V,E)兩兩點(diǎn)對(duì)之間的共同鄰居；

輸出：圖G(V,E)兩兩點(diǎn)對(duì)之間的預(yù)測(cè)分?jǐn)?shù)值。

具體流程圖，如圖3所示。

圖3 Reducer流程圖

2 實(shí)驗(yàn)結(jié)果及分析

2.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證MapReduce并行鏈路算法的精確度，本文選用6個(gè)不同類型的網(wǎng)絡(luò)，包括社交網(wǎng)絡(luò)、信息網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等，與3種其他鏈路預(yù)算進(jìn)行對(duì)比。選用的數(shù)據(jù)集有[10]：Jazz網(wǎng)絡(luò)，爵士樂(lè)音樂(lè)家的一個(gè)合作網(wǎng)絡(luò)，節(jié)點(diǎn)數(shù)為198個(gè)，其中每個(gè)節(jié)點(diǎn)代表一個(gè)音樂(lè)家，節(jié)點(diǎn)之間的邊代表音樂(lè)家之間的合作關(guān)系；Celegans網(wǎng)絡(luò)由watts等人匯編，屬于生物網(wǎng)絡(luò)類型，節(jié)點(diǎn)總數(shù)為297，每個(gè)節(jié)點(diǎn)代表一個(gè)神經(jīng)元，邊則表示神經(jīng)元突觸； Yeast屬于酵母菌蛋白質(zhì)交互(PPI)網(wǎng)絡(luò)，屬于生物網(wǎng)絡(luò)，一個(gè)節(jié)點(diǎn)代表一個(gè)酵母菌蛋白質(zhì)，邊代表蛋白質(zhì)間的相互作用；Power網(wǎng)絡(luò)屬于電力網(wǎng)絡(luò)，節(jié)點(diǎn)表示發(fā)電站、中轉(zhuǎn)站等，邊代表高壓傳輸線；Router網(wǎng)絡(luò)作為一種信息網(wǎng)絡(luò)，代表了路由器層面的計(jì)算機(jī)網(wǎng)絡(luò)，節(jié)點(diǎn)表示路由器，邊代表路由器之間的物理通信線路；USAir作為美國(guó)一個(gè)航空網(wǎng)絡(luò)的數(shù)據(jù)集，節(jié)點(diǎn)表示航空港，邊表示航線，該網(wǎng)絡(luò)包括兩千多條邊，屬于信息網(wǎng)絡(luò)類型。

為6個(gè)網(wǎng)絡(luò)的相關(guān)拓?fù)涮匦裕绫?所示。

表2 不同網(wǎng)絡(luò)基本拓?fù)涮卣鞅容^

其中聚類系數(shù)表示網(wǎng)絡(luò)聚類特性描述指標(biāo)，聚類系數(shù)越大，代表網(wǎng)絡(luò)社團(tuán)的特征越明顯；網(wǎng)絡(luò)直徑代表所有節(jié)點(diǎn)對(duì)的直線距離最大值；平均刻度表示節(jié)點(diǎn)度數(shù)的平均值。節(jié)點(diǎn)數(shù)越多，則平均度越小，代表網(wǎng)絡(luò)越稀疏，節(jié)點(diǎn)之間聯(lián)系不緊密，因此聚類系數(shù)低，網(wǎng)絡(luò)直徑大。

2.2 實(shí)驗(yàn)結(jié)果

對(duì)復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)效果采用AUC指標(biāo)進(jìn)行評(píng)估，在式(1)中，將復(fù)雜網(wǎng)絡(luò)分為訓(xùn)練集和測(cè)試集，兩者比例為9∶1，通過(guò)訓(xùn)練集計(jì)算獲得各網(wǎng)絡(luò)中每?jī)晒?jié)點(diǎn)之間的相似度分?jǐn)?shù)后，每次隨機(jī)從測(cè)試集和不存在的邊集中分別選取一條邊進(jìn)行比較。若測(cè)試集中邊的相似度分?jǐn)?shù)值超過(guò)不存在邊的相似度分?jǐn)?shù)值，加1分；若兩個(gè)相似度分?jǐn)?shù)值相等，則加0.5分，以上獨(dú)立比較N次。假設(shè)所有分?jǐn)?shù)均隨機(jī)產(chǎn)生，則獲得的AUC=0.5，各種并行鏈路算法獲得AUC值超過(guò)0.5的程度衡量了算法比隨機(jī)選擇準(zhǔn)確的程度。

為不同鏈路預(yù)測(cè)算法的AUC評(píng)價(jià)結(jié)果，如表3所示。

表3 不同鏈路預(yù)測(cè)算法的AUC值

由此可見(jiàn)，在選取的6個(gè)不同類型的真實(shí)網(wǎng)絡(luò)中，基于共同鄰居的相似性算法基本都獲得了0.8以上的鏈路預(yù)測(cè)AUC效果。將MapReduce背景下的復(fù)雜網(wǎng)絡(luò)預(yù)測(cè)所得的AUC值與文獻(xiàn)[11]中基于節(jié)點(diǎn)相似性的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)所得AUC結(jié)果對(duì)比發(fā)現(xiàn)：MapReduce背景下的復(fù)雜網(wǎng)絡(luò)預(yù)測(cè)所得的AUC值與普通條件下基于節(jié)點(diǎn)相似性的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)所得AUC基本保持一致，誤差在0.035，屬于可接受范圍內(nèi)。

2.3 分析及討論

實(shí)驗(yàn)中觀察到如下現(xiàn)象：針對(duì)不同網(wǎng)絡(luò)，每個(gè)算法的效果差距較大，對(duì)于CN算法，AUC結(jié)果從0.86到0.95不等，性能差異高達(dá)11%；并且每個(gè)算法其性能差異是以同樣的規(guī)律波動(dòng)，網(wǎng)絡(luò)平均度對(duì)應(yīng)的各個(gè)算法性能差異示意圖，如圖4所示。

圖4 網(wǎng)絡(luò)平均度對(duì)應(yīng)的各算法性能

結(jié)果顯示：選取的各個(gè)參照算法的性能基本上是按照同樣的規(guī)律在波動(dòng)，這顯示共同鄰居越多，相似性越大。

3 總結(jié)

針對(duì)MapReduce的特點(diǎn)，發(fā)現(xiàn)其可以有效規(guī)避傳統(tǒng)并行鏈路算法存在的計(jì)算機(jī)復(fù)雜度高和單個(gè)計(jì)算機(jī)內(nèi)存現(xiàn)在問(wèn)題，將MapReduce應(yīng)用于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)分析具有重要的意義。本文主要基于MapReduce背景下進(jìn)行復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)分析，結(jié)果顯示：MapReduce背景下的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)分析有效，且選取的各個(gè)參照算法的性能基本上是按照同樣的規(guī)律在波動(dòng)。