基于有偏向的重啟隨機(jī)游走鏈路預(yù)測算法

呂亞楠，韓 華，賈承豐，瞿倩倩

(武漢理工大學(xué)理學(xué)院，武漢 430070)

0 引言

近年來，隨著復(fù)雜網(wǎng)絡(luò)在各領(lǐng)域的滲透，許多相關(guān)工作對復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)演化進(jìn)行研究，以期能全面理解復(fù)雜網(wǎng)絡(luò)的本質(zhì)特征[1]。其中鏈路預(yù)測作為研究網(wǎng)絡(luò)演化的一個(gè)分支，受到越來越多學(xué)者的關(guān)注。鏈路預(yù)測是根據(jù)靜態(tài)或動(dòng)態(tài)的網(wǎng)絡(luò)數(shù)據(jù)來預(yù)測網(wǎng)絡(luò)中兩個(gè)不相連的節(jié)點(diǎn)之間產(chǎn)生連邊的可能性，并觀察給定的方法對新鏈路出現(xiàn)的預(yù)測效果。鏈路預(yù)測方法在大多數(shù)領(lǐng)域中都有相關(guān)應(yīng)用，如生物系統(tǒng)中，探索蛋白質(zhì)之間的相互作用[2]；在線社交網(wǎng)絡(luò)中，推薦可能認(rèn)識的朋友[3]；航空網(wǎng)絡(luò)中，推斷影響網(wǎng)絡(luò)演化的重要因素[4]等。

當(dāng)前，基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的鏈路預(yù)測因其方法簡單且實(shí)際操作性強(qiáng)而引起大量研究。利用節(jié)點(diǎn)間相似性的方法假設(shè)：在網(wǎng)絡(luò)中，根據(jù)節(jié)點(diǎn)之間的拓?fù)涮卣鳎瑑蓚€(gè)節(jié)點(diǎn)之間的相似性越大，它們之間存在連邊的可能性就越大[5]。而且主要依賴于網(wǎng)絡(luò)結(jié)構(gòu)，像節(jié)點(diǎn)的度、聚集系數(shù)[6]、節(jié)點(diǎn)之間的路徑[7]、社團(tuán)結(jié)構(gòu)[8]等。根據(jù)所用結(jié)構(gòu)信息的不同，基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性預(yù)測算法可以分為如下三類：基于局部信息的相似性指標(biāo)、基于路徑的相似性指標(biāo)、基于隨機(jī)游走過程的相似性指標(biāo)?；诰植啃畔⒌南嗨菩灾笜?biāo)是指只通過節(jié)點(diǎn)局部信息，像節(jié)點(diǎn)的度、最近鄰居，計(jì)算得到的相似性指標(biāo)。這類指標(biāo)的優(yōu)勢在于計(jì)算復(fù)雜度低，適用大規(guī)模的網(wǎng)絡(luò)?；诼窂降南嗨菩灾笜?biāo)是利用要預(yù)測的兩個(gè)節(jié)點(diǎn)之間的路徑信息，像節(jié)點(diǎn)之間路徑數(shù)量，路徑中間節(jié)點(diǎn)的信息，計(jì)算得到的相似性指標(biāo)。這類指標(biāo)既有基于全局信息的路徑指標(biāo)，也有基于局部信息的路徑指標(biāo)，當(dāng)考慮多階路徑信息的貢獻(xiàn)時(shí)，計(jì)算復(fù)雜度相對較高?；陔S機(jī)游走的相似性指標(biāo)是基于隨機(jī)游走過程定義的，包括平均通勤時(shí)間指標(biāo)(ACT)[9]、有重啟的隨機(jī)游走指標(biāo)(RWR)[10]、SimRank指標(biāo)(SimR)[11]等。這類指標(biāo)大多數(shù)是基于全局信息的指標(biāo)，且這些指標(biāo)不僅僅在鏈路預(yù)測中應(yīng)用，在推薦系統(tǒng)[12]、排名[13]、社團(tuán)劃分[14]等也有應(yīng)用。

隨機(jī)游走作為研究網(wǎng)絡(luò)結(jié)構(gòu)和特性的一種方法，在基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性方法中得到廣泛關(guān)注。網(wǎng)絡(luò)中的隨機(jī)游走是指粒子從初始節(jié)點(diǎn)出發(fā)，以一定的概率隨機(jī)游走到它的鄰居節(jié)點(diǎn)，然后再以一定的概率隨機(jī)游走到鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，這樣一直游走下去，直到達(dá)到平穩(wěn)狀態(tài)?；陔S機(jī)游走的特性，Li Rong-Hua等人[15]認(rèn)為在真實(shí)網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的節(jié)點(diǎn)不僅傾向于連接度小的節(jié)點(diǎn)，而且也傾向于連接中心節(jié)點(diǎn)，提出一種最大熵隨機(jī)游走的鏈路預(yù)測算法，其中最大熵隨機(jī)游走包括了網(wǎng)絡(luò)節(jié)點(diǎn)的中心性。劉思等人[16]考慮到網(wǎng)絡(luò)結(jié)構(gòu)上不同鄰居節(jié)點(diǎn)間的相似性對轉(zhuǎn)移概率的作用，利用網(wǎng)絡(luò)表示學(xué)習(xí)算法的DeepWalk學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的潛在結(jié)構(gòu)特征，提出一種基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法。Jin Woojeong等人[17]發(fā)現(xiàn)有重啟的隨機(jī)游走對所有節(jié)點(diǎn)使用相同的重啟概率，限制了隨機(jī)游走的表現(xiàn)性，且重啟概率需要人為選擇，于是提出一種有監(jiān)督和拓展重新啟動(dòng)的隨機(jī)游走用于排序和鏈路預(yù)測，使得每個(gè)節(jié)點(diǎn)都對應(yīng)一個(gè)重啟概率。

在大多數(shù)的隨機(jī)游走過程中，粒子由當(dāng)前節(jié)點(diǎn)游走到下個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率都是相等的。但由網(wǎng)絡(luò)的度度相關(guān)性[18]可以看出，節(jié)點(diǎn)之間的連接不是隨機(jī)產(chǎn)生的，粒子在游走過程中會(huì)受到節(jié)點(diǎn)度值的影響。且現(xiàn)實(shí)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜多樣，粒子在游走過程中不一定是等概率的移動(dòng)，而是會(huì)以某種偏向進(jìn)行游走?；谏鲜鰡栴}，本文提出一種有偏向的重啟隨機(jī)游走方法用于鏈路預(yù)測，使粒子在游走的過程中偏向于移動(dòng)到與初始節(jié)點(diǎn)相似的節(jié)點(diǎn)上，進(jìn)而提高預(yù)測精度。本文主要工作如下：第一部分介紹鏈路預(yù)測的基本概念、經(jīng)典指標(biāo)及評價(jià)指標(biāo)；第二部分定義一種新的鏈路預(yù)測算法，即有偏向的重啟隨機(jī)游走算法；第三部分介紹數(shù)據(jù)集及相關(guān)參數(shù)，然后進(jìn)行實(shí)驗(yàn)，并對結(jié)果進(jìn)行分析；第四部分總結(jié)全文及進(jìn)一步工作。

1 基本概念

1.1 問題描述

圖1為一個(gè)簡單的無權(quán)無向網(wǎng)絡(luò)。根據(jù)上面的描述，可以看出網(wǎng)絡(luò)的節(jié)點(diǎn)集為V=(v1,v2,v3,v4,v5,v6)，連邊集為E=(e1,e2,e3,e4,e5,e6,e7)。若網(wǎng)絡(luò)用鄰接矩陣A表示，則為

圖1 一個(gè)簡單無權(quán)無向網(wǎng)絡(luò)示例

且各節(jié)點(diǎn)的度值為k1=k2=k3=3,k4=k6=2,k5=1。那么鏈路預(yù)測就是根據(jù)目前網(wǎng)絡(luò)的連邊信息，運(yùn)用給定的預(yù)測方法計(jì)算出網(wǎng)絡(luò)中尚未產(chǎn)生連邊的節(jié)點(diǎn)對v1和v4、v1和v6、v2和v5、v2和v6、v3和v4等產(chǎn)生連邊的可能性。

1.2 典型的鏈路預(yù)測算法

基于相似性的鏈路預(yù)測算法是根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)所定義，且常被作為基準(zhǔn)算法與所提出的新算法作對比?；谙嗨菩缘闹笜?biāo)一般可以分為基于局部信息和全局信息兩類。其中基于局部信息的預(yù)測算法有共同鄰居指標(biāo)(CN指標(biāo))、Salton指標(biāo)、Jaccard指標(biāo)、大度節(jié)點(diǎn)有利指標(biāo)(HPI指標(biāo))、大度節(jié)點(diǎn)不利指標(biāo)(HDI指標(biāo))、Adamic-Adar指標(biāo)(AA指標(biāo))、資源分配指標(biāo)(RA指標(biāo))等等。基于全局信息的預(yù)測算法，一般考慮網(wǎng)絡(luò)的所有路徑或者節(jié)點(diǎn)之間的所有結(jié)構(gòu)，其中包括Katz指標(biāo)、LHN-II指標(biāo)、平均通勤時(shí)間(ACT指標(biāo))、余弦相似性(Cos+指標(biāo))、有重啟的隨機(jī)游走(RWR指標(biāo))、SimRank指標(biāo)等等[5]。從上述類別中，分別選取以下6種經(jīng)典的鏈路預(yù)測算法作為基準(zhǔn)算法。

1)共同鄰居(CN)

共同鄰居指標(biāo)是最基礎(chǔ)的相似性指標(biāo)，對于未連邊的兩個(gè)節(jié)點(diǎn)x和y的相似性定義為它們共同鄰居節(jié)點(diǎn)的個(gè)數(shù)。用式(1)表示為

Sxy=|Γ(x)∩Γ(y)|

(1)

其中，Γ(x)為節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)集合，顯然，這里的Sxy就等于兩節(jié)點(diǎn)之間長度為2的路徑數(shù)目。

2)資源分配(RA)

資源分配指標(biāo)考慮網(wǎng)絡(luò)中沒有直接相連的兩個(gè)節(jié)點(diǎn)x和y，從節(jié)點(diǎn)x可以傳遞一些資源到節(jié)點(diǎn)y，在這個(gè)過程中，它們的共同鄰居成為傳遞的媒介，且每個(gè)媒介都將資源平均分配傳給它的鄰居，則節(jié)點(diǎn)x和y的相似度定義為

(2)

其中，kz為節(jié)點(diǎn)z的度值。

3)Katz指標(biāo)

Katz指標(biāo)考慮了網(wǎng)絡(luò)的所有路徑，其定義為

(3)

4)平均通勤時(shí)間(ACT)

(4)

5)有重啟的隨機(jī)游走(RWR)

假設(shè)隨機(jī)游走粒子在每走一步時(shí)都以一定概率返回初始位置。設(shè)粒子返回概率為1-c，P為網(wǎng)絡(luò)的馬爾科夫概率轉(zhuǎn)移矩陣，其元素為Pxy=1/kx表示節(jié)點(diǎn)x處的粒子下一步走到相鄰節(jié)點(diǎn)y的概率。某一粒子初始時(shí)刻在節(jié)點(diǎn)x處，則t+1時(shí)刻該粒子到達(dá)網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的概率向量為

πx(t+1)=c·PTπx(t)+(1-c)qx

(5)

其中，qx為初始狀態(tài)，它是一個(gè)N維列向量且僅有第x個(gè)元素為1，其他元素都為0。式(5)的穩(wěn)態(tài)解為πx=(1-c)(I-cPT)-1qx，其中元素πxy為從節(jié)點(diǎn)x出發(fā)的粒子最終有多少概率達(dá)到節(jié)點(diǎn)y，則RWR相似性定義為

Sxy=πxy+πyx

(6)

6)SimRank指標(biāo)(SimR)

SimRank指標(biāo)的基本假設(shè)是如果兩節(jié)點(diǎn)所連接的節(jié)點(diǎn)相似，那么這兩個(gè)節(jié)點(diǎn)就相似。用式(7)表示為

(7)

其中，假定Sxx=1，C∈[0,1]為相似性傳遞時(shí)的衰減參數(shù)。

1.3 評價(jià)指標(biāo)

為了測試算法的準(zhǔn)確性，一般將已知的連邊E分為兩部分：訓(xùn)練集ET和測試集EP。訓(xùn)練集ET作為實(shí)驗(yàn)時(shí)可觀察到的網(wǎng)絡(luò)信息，用于計(jì)算節(jié)點(diǎn)的相似性得分。測試集EP作為實(shí)驗(yàn)時(shí)要預(yù)測的網(wǎng)絡(luò)信息，用于對比實(shí)驗(yàn)預(yù)測的結(jié)果。這里，E=ET∪EP，且ET∩EP=?，令U為N(N-1)/2個(gè)節(jié)點(diǎn)對組成的全集，那么將屬于U但不屬于E的邊稱為不存在的邊，屬于U但不屬于ET的邊為未知邊。

文中使用鏈路預(yù)測中評價(jià)準(zhǔn)確性認(rèn)可度高的指標(biāo)——AUC指標(biāo)。AUC指標(biāo)是從整體上衡量指標(biāo)的精確度，它是指在測試集中隨機(jī)選擇一條邊的分?jǐn)?shù)值比隨機(jī)選擇的一條不存在的邊的分?jǐn)?shù)值高的概率[19]。實(shí)驗(yàn)時(shí)，每次隨機(jī)從測試集中選取一條邊，再從不存在的邊中隨機(jī)選擇一條，如果測試集中的邊分?jǐn)?shù)值大于不存在的邊的分?jǐn)?shù)值，那么就加1分，如果兩個(gè)分?jǐn)?shù)值相等就加0.5分。這樣獨(dú)立比較n次，如果有n′次測試集中的邊分?jǐn)?shù)值大于不存在的邊分?jǐn)?shù)，有n″次兩分?jǐn)?shù)值相等，那么AUC指標(biāo)的定義為

(8)

顯然，如果所有分?jǐn)?shù)都是隨機(jī)產(chǎn)生的，AUC=0.5。

2 基于有偏向的重啟隨機(jī)游走鏈路預(yù)測

借鑒相關(guān)的有偏向隨機(jī)游走過程[20]，改變粒子在節(jié)點(diǎn)之間的轉(zhuǎn)移概率，使其在游走過程中具有一定的度偏向性，再利用有重啟的隨機(jī)游走過程，對網(wǎng)絡(luò)中未連邊的節(jié)點(diǎn)對進(jìn)行相似性計(jì)算，找到每個(gè)網(wǎng)絡(luò)最佳的度偏向調(diào)節(jié)系數(shù)值，以達(dá)到提高預(yù)測精度的目的。

2.1 有偏向的重啟隨機(jī)游走

有偏向隨機(jī)游走是指隨機(jī)游走粒子由當(dāng)前節(jié)點(diǎn)x以偏向轉(zhuǎn)移概率wxy游走到其鄰居節(jié)點(diǎn)y，然后再從節(jié)點(diǎn)y以偏向轉(zhuǎn)移概率wyz游走到節(jié)點(diǎn)y的其中一個(gè)鄰居節(jié)點(diǎn)z，重復(fù)這個(gè)過程，直至到達(dá)平穩(wěn)狀態(tài)。重啟隨機(jī)游走是指粒子在每一步游走的時(shí)候都以概率α移動(dòng)到下一個(gè)節(jié)點(diǎn)，或者以概率1-α跳回初始節(jié)點(diǎn)，這個(gè)過程類似于網(wǎng)頁排序算法PageRank。有偏向的重啟隨機(jī)游走是將這兩個(gè)過程進(jìn)行融合，即當(dāng)游走粒子從網(wǎng)絡(luò)中的某一個(gè)節(jié)點(diǎn)出發(fā)，每一步面臨兩個(gè)選擇，以概率α移動(dòng)到相鄰節(jié)點(diǎn)，或以概率1-α返回初始節(jié)點(diǎn)。當(dāng)以概率α移動(dòng)到相鄰節(jié)點(diǎn)的時(shí)候，此時(shí)會(huì)以偏向概率w選擇其中一個(gè)鄰居節(jié)點(diǎn)作為下一步移動(dòng)到的節(jié)點(diǎn)，然后重復(fù)以上過程，直至達(dá)到平穩(wěn)狀態(tài)。有偏向的重啟隨機(jī)游走既避免了有偏向隨機(jī)游走在未達(dá)到平穩(wěn)狀態(tài)時(shí)游走粒子發(fā)生終止現(xiàn)象，即游走粒子進(jìn)入死角，又解決了有重啟的隨機(jī)游走過程中節(jié)點(diǎn)之間等概率轉(zhuǎn)移的問題。

定義1度偏向轉(zhuǎn)移概率

根據(jù)馬爾科夫鏈過程[21]可知，下一時(shí)刻節(jié)點(diǎn)的游走只與當(dāng)前節(jié)點(diǎn)的狀態(tài)有關(guān)?；诙扔衅螂S機(jī)游走過程中，當(dāng)前節(jié)點(diǎn)移動(dòng)到下一節(jié)點(diǎn)時(shí)，與當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)度值成比例，即kβ，其中β是度偏向調(diào)節(jié)參數(shù)，從β值的大小可以看出游走粒子在網(wǎng)絡(luò)中是偏向于度大的節(jié)點(diǎn)游走還是度小的節(jié)點(diǎn)游走以及偏向的程度。

網(wǎng)絡(luò)中基于度有偏向隨機(jī)游走的轉(zhuǎn)移概率定義[20]為

(9)

定義2有偏向的重啟隨機(jī)游走指標(biāo)

將定義1中每個(gè)節(jié)點(diǎn)的度偏向轉(zhuǎn)移概率用于有重啟隨機(jī)游走中，改變節(jié)點(diǎn)之間的等概率轉(zhuǎn)移矩陣，進(jìn)而得到有偏向的重啟隨機(jī)游走指標(biāo)(Biased random walk with restart，簡稱BRWR指標(biāo))。某一粒子初始時(shí)刻在節(jié)點(diǎn)x處，則t+1時(shí)刻該粒子到達(dá)網(wǎng)絡(luò)各個(gè)節(jié)點(diǎn)的概率向量為

πx(t+1)=α·WTπx(t)+(1-α)qx

(10)

其中，W為式(9)的度偏向轉(zhuǎn)移概率矩陣，1-α為重啟概率，qx表示初始狀態(tài)，它是一個(gè)N維列向量且僅有第x個(gè)元素為1，其他元素都為0。當(dāng)t→∞時(shí)，由馬爾科夫鏈的平穩(wěn)狀態(tài)[21]可知即使再經(jīng)過一步狀態(tài)轉(zhuǎn)移，其狀態(tài)概率仍保持不變，即Π=WTΠ，因此得到式(10)穩(wěn)態(tài)解為

πx=(1-α)(I-αWT)-1qx

(11)

那么BRWR相似性指標(biāo)為

(12)

其中，元素πxy為從節(jié)點(diǎn)x出發(fā)的粒子最終有多少概率達(dá)到節(jié)點(diǎn)y。

2.2 算法流程

本算法首先通過設(shè)定β的一個(gè)取值范圍，將范圍內(nèi)各個(gè)不同的β值代入算法中，經(jīng)過循環(huán)計(jì)算，觀察β取值對預(yù)測結(jié)果的影響(具體情況參見3.2)，找到最佳度偏向調(diào)節(jié)參數(shù)βopt，再將βopt值代入BRWR算法中，得到節(jié)點(diǎn)之間的相似性得分。在最佳的βopt值下，BRWR算法主要流程如下：

算法 BRWR

輸入 網(wǎng)絡(luò)的鄰接矩陣A=[aij]，重啟概率1-α，最佳度偏向調(diào)節(jié)參數(shù)βopt。

輸出 節(jié)點(diǎn)的相似性得分矩陣S=[sij]。

1)初始化偏向轉(zhuǎn)移矩陣W←0N×N，節(jié)點(diǎn)相似性得分矩陣S←IN×N；

2)利用式(9)計(jì)算網(wǎng)絡(luò)中各節(jié)點(diǎn)間的偏向轉(zhuǎn)移概率并更新歸一化的偏向轉(zhuǎn)移矩陣W；

3) Fori= 1 toNdo

4) WhileS不收斂do

5)πx=(1-α)(I-αWT)-1qx； //計(jì)算節(jié)點(diǎn)x與其余各節(jié)點(diǎn)的相似性值

6) End While；

7) End for；

8) ReturnS。

2.3 算法收斂性

定理1BRWR算法是收斂的。

2)當(dāng)隨機(jī)游走過程遍歷到某一節(jié)點(diǎn)后，因?yàn)殡S機(jī)游走過程中存在重啟概率，所以再次遍歷到這個(gè)節(jié)點(diǎn)時(shí)，所需的步數(shù)是不確定的，故整個(gè)隨機(jī)游走過程是非周期的。

3)當(dāng)圖中任意一個(gè)節(jié)點(diǎn)被遍歷后，都可能在一定步數(shù)內(nèi)再次遍歷這個(gè)節(jié)點(diǎn)，且再次遍歷之前經(jīng)過的步數(shù)是不完全相同的。

由以上3點(diǎn)，可得出BRWR算法是各態(tài)歷經(jīng)的[22]，故此算法是收斂的。

2.4 復(fù)雜度分析

定理2BRWR算法的時(shí)間復(fù)雜度為O(N3)。

證明：因?yàn)樵趖→∞時(shí)，BRWR算法會(huì)達(dá)到穩(wěn)態(tài)，此時(shí)借助穩(wěn)態(tài)解πx=(1-α)(I-αWT)-1qx，可以看出要求出矩陣I-αWT的逆，那么一般求一個(gè)N×N矩陣的逆或偽逆的時(shí)間復(fù)雜度為O(N3)[23]，故此算法的時(shí)間復(fù)雜度為O(N3)。

3 實(shí)驗(yàn)結(jié)果與分析

本文將實(shí)驗(yàn)分為兩大部分，一是利用AUC評價(jià)指標(biāo)，觀察β值的變化對預(yù)測結(jié)果的影響，進(jìn)而確定最佳βopt的值；二是在最佳βopt值下，BRWR指標(biāo)與6個(gè)經(jīng)典鏈路預(yù)測指標(biāo)作對比，觀察BRWR指標(biāo)的預(yù)測效果。實(shí)驗(yàn)借助Matlab 2014作為實(shí)驗(yàn)工具，平均進(jìn)行30次獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)時(shí)隨機(jī)劃分訓(xùn)練集和測試集，其中訓(xùn)練集所占比例為90%。

3.1 數(shù)據(jù)集及相關(guān)參數(shù)

為了測試提出算法的有效性，采用6個(gè)具有代表性的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集[24]，忽略網(wǎng)絡(luò)連邊的權(quán)重與方向，數(shù)據(jù)集包括：美國航空網(wǎng)絡(luò)(USAir)、爵士樂手網(wǎng)絡(luò)(Jazz)、線蟲新陳代謝網(wǎng)絡(luò)(Metabolic)、佛羅里達(dá)生態(tài)系統(tǒng)食物鏈網(wǎng)絡(luò)(FWFW)、線蟲神經(jīng)網(wǎng)絡(luò)(C.elegans)、美國政治博客網(wǎng)絡(luò)(P-Blogs)。數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)特征如表1，其中N為節(jié)點(diǎn)數(shù)，M為連邊數(shù)，〈K〉為平均度，〈C〉為平均聚集系數(shù)，R為匹配系數(shù)。

表1 各數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)特征

3.2 不同β值下BRWR指標(biāo)的AUC值變化

針對6個(gè)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)，首先分析了不同網(wǎng)絡(luò)中度偏向調(diào)節(jié)參數(shù)β對BRWR指標(biāo)預(yù)測結(jié)果的影響，這里固定α=0.85，β步長取0.01，測試集與訓(xùn)練集的比例為1:9。圖2顯示了不同β值下所有網(wǎng)絡(luò)的AUC值變化曲線。相比β=0(即無偏向隨機(jī)游走)，指標(biāo)都有不同程度地提高其預(yù)測精度，且在合適的參數(shù)下均可以取得最大預(yù)測精度，說明基于度有偏向的隨機(jī)游走過程對鏈路預(yù)測有影響。在取得最大精度值后AUC值變化曲線都會(huì)呈現(xiàn)不同程度的下降，其中USAir、Jazz、Metabolic、C.elegans網(wǎng)絡(luò)在取得最大精度值后曲線下降較快，在一定程度上說明粒子在這些網(wǎng)絡(luò)中游走時(shí)，偏向游走到度大節(jié)點(diǎn)的程度越大，預(yù)測的準(zhǔn)確度越低。

圖2 不同β值下BRWR指標(biāo)的預(yù)測結(jié)果

BRWR指標(biāo)的AUC最大值均高于β=0時(shí)的預(yù)測值，這表明有偏向性的隨機(jī)游走確實(shí)能夠提高鏈路預(yù)測的預(yù)測精度。同樣，相比β=1時(shí)，即類似于優(yōu)先連接[25]，最大的AUC值也明顯更高，側(cè)面表達(dá)出粒子在這些網(wǎng)路中不偏向于游走到度大的節(jié)點(diǎn)。而且在這6個(gè)網(wǎng)絡(luò)中，從每個(gè)網(wǎng)絡(luò)的最優(yōu)β值可以看出，β值在(-1,0)之間，表明粒子偏向于游走到度小的節(jié)點(diǎn)，正如Adamic-Adar指標(biāo)[26]的思想，度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)。這里β<0也相當(dāng)于對網(wǎng)絡(luò)中度大節(jié)點(diǎn)進(jìn)行懲罰。實(shí)際應(yīng)用中可在一定范圍內(nèi)調(diào)節(jié)β值，可以提高預(yù)測精度。

3.3 與其他典型相似性指標(biāo)對比

為了進(jìn)一步說明有偏向隨機(jī)游走過程的可行性及BRWR指標(biāo)的有效性，以下將與經(jīng)典的相似性指標(biāo)進(jìn)行對比性分析，各個(gè)相似性指標(biāo)的AUC結(jié)果對比如表2所示?？梢钥闯觯?個(gè)實(shí)際網(wǎng)絡(luò)中，相比CN、RA、Katz、ACT、SimR、RWR指標(biāo)，BRWR指標(biāo)對預(yù)測精度都有一定程度的提高。CN、RA指標(biāo)屬于局部相似性指標(biāo)，由于RA指標(biāo)在共同鄰居節(jié)點(diǎn)的基礎(chǔ)上為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)重值，所以在局部相似性指標(biāo)中RA指標(biāo)的預(yù)測精確相對好。Katz、ACT、SimR、RWR指標(biāo)屬于全局指標(biāo)，其中Katz指標(biāo)是考慮節(jié)點(diǎn)之間的所有路徑，ACT、SimR、RWR指標(biāo)都是基于隨機(jī)游走過程，且RWR指標(biāo)在這些全局指標(biāo)中表現(xiàn)最好。若以RWR指標(biāo)為基準(zhǔn)，由表2觀察到BRWR指標(biāo)相較RWR指標(biāo)，其預(yù)測精確度平均提升了2.24%，且C.elegans網(wǎng)絡(luò)的AUC值提高了3.97%。由定理2可知BRWR指標(biāo)的時(shí)間復(fù)雜度為O(N3)，和RWR指標(biāo)的時(shí)間復(fù)雜度一樣，那么在時(shí)間復(fù)雜度相同的情況下，可以看出BRWR指標(biāo)的預(yù)測準(zhǔn)確度比RWR指標(biāo)更好，說明有偏向性的重啟隨機(jī)游走對鏈路預(yù)測是有效和可行的。

表2 不同指標(biāo)下AUC值對比

4 結(jié)論

本文在有重啟的隨機(jī)游走算法的基礎(chǔ)上，考慮了網(wǎng)絡(luò)節(jié)點(diǎn)度值對轉(zhuǎn)移概率的影響，提出一種基于有偏向的重啟隨機(jī)游走鏈路預(yù)測算法。首先利用有偏向性的隨機(jī)游走過程得到節(jié)點(diǎn)之間的度偏向轉(zhuǎn)移概率，然后將度偏向轉(zhuǎn)移概率融合到有重啟的隨機(jī)游走過程中，最后通過對AUC值的多次計(jì)算找到最佳的度偏向調(diào)節(jié)參數(shù)，從而得到最優(yōu)的AUC值。實(shí)驗(yàn)結(jié)果表明，有偏向性的游走能夠提高連邊的預(yù)測精度，且相比其他經(jīng)典算法，有偏向的重啟隨機(jī)游走鏈路預(yù)測算法的預(yù)測效果更加準(zhǔn)確。在下一步的研究中，可以嘗試一種同時(shí)調(diào)節(jié)度偏向調(diào)節(jié)參數(shù)和重啟概率的隨機(jī)游走在鏈路預(yù)測問題上的應(yīng)用，在各個(gè)網(wǎng)絡(luò)中找出最佳的度偏向調(diào)節(jié)參數(shù)和重啟概率，使預(yù)測精度有進(jìn)一步的提升。且鏈路預(yù)測中對網(wǎng)絡(luò)隨機(jī)游走過程有影響的因素不止節(jié)點(diǎn)度值，那么在能提高預(yù)測精度的前提下，可進(jìn)一步探究出還有哪些因素影響隨機(jī)游走過程。