常雅文

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

0 引言

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

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

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

1.1 問題描述

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

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

表1 基于節(jié)點信息的10種相似性指標

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

1.2 MapReduce 并行計算模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟三：將ET中點對用鄰接表表示；

步驟四：對于ET的鄰接表，利用相似性指標獲得兩兩點對的預(yù)測分數(shù)值(文件D)；

(1)

對于步驟四種中利用相似性指標獲得兩兩點對的預(yù)測分數(shù)值的方法如下。

Mapper

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

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

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

圖2 Mapper流程圖

Reducer

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

輸出：圖G(V,E)兩兩點對之間的預(yù)測分數(shù)值。

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

圖3 Reducer流程圖

2 實驗結(jié)果及分析

2.1 實驗設(shè)置

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

為6個網(wǎng)絡(luò)的相關(guān)拓撲特性，如表2所示。

表2 不同網(wǎng)絡(luò)基本拓撲特征比較

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

2.2 實驗結(jié)果

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

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

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

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

2.3 分析及討論

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

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

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

3 總結(jié)

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