一種基于MH改進(jìn)的重啟隨機(jī)游走鏈路預(yù)測(cè)算法

呂 亮，何 敏，易 燦

(云南大學(xué) 信息學(xué)院，云南 昆明 650500)

當(dāng)今社會(huì)，復(fù)雜網(wǎng)絡(luò)無(wú)處不在[1]. 網(wǎng)絡(luò)由節(jié)點(diǎn)和連邊構(gòu)成：節(jié)點(diǎn)表示不同的事物；連邊表示事物間的聯(lián)系，即事物間的鏈路關(guān)系. 鏈路預(yù)測(cè)可以幫助學(xué)者們分析復(fù)雜網(wǎng)絡(luò)中事物間的聯(lián)接關(guān)系，因而得到了廣泛的研究[2].

鏈路預(yù)測(cè)是網(wǎng)絡(luò)科學(xué)和機(jī)器學(xué)習(xí)的基礎(chǔ)[3]，也是數(shù)據(jù)分析中一個(gè)重要的研究課題[4]. 鏈路預(yù)測(cè)對(duì)復(fù)雜網(wǎng)絡(luò)中潛在的或未被發(fā)現(xiàn)的鏈接進(jìn)行預(yù)測(cè)[5]，具有重要的理論價(jià)值和實(shí)際意義[6]. 在現(xiàn)實(shí)生活中，鏈路預(yù)測(cè)有著廣泛的應(yīng)用，例如好友推薦[7]、網(wǎng)絡(luò)重構(gòu)[8]、社區(qū)發(fā)現(xiàn)[9]等. 在解釋網(wǎng)絡(luò)演化的過(guò)程中，鏈路預(yù)測(cè)也起著重要作用[10]. 因此，如何提高鏈路預(yù)測(cè)的準(zhǔn)確性，成為研究復(fù)雜網(wǎng)絡(luò)的核心內(nèi)容之一. 基本的鏈路預(yù)測(cè)算法分為兩大類：一是基于節(jié)點(diǎn)相似性指標(biāo)[11]，二是基于機(jī)器學(xué)習(xí)算法[12].

基于節(jié)點(diǎn)相似性指標(biāo)的鏈路預(yù)測(cè)算法簡(jiǎn)單、實(shí)用，一直是研究的熱點(diǎn). 相似性理論認(rèn)為，網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)的結(jié)構(gòu)特征越相似，它們之間產(chǎn)生鏈接的可能性越大[13]. 近年來(lái)，機(jī)器學(xué)習(xí)算法的性能大幅提升，學(xué)者們將其引入鏈路預(yù)測(cè)以提高預(yù)測(cè)效果.其中，網(wǎng)絡(luò)表示學(xué)習(xí) (Network Presentation Learning，NPL)算法被大量應(yīng)用[14]. Mikolov等[15]提出的神經(jīng)網(wǎng)絡(luò)模型Word2vec在詞嵌入向量中取得良好效果；Perozzi等[16]提出的DeepWalk模型，利用隨機(jī)游走 (Random Walk，RW)進(jìn)行采樣，結(jié)合Word2vec模型，得到節(jié)點(diǎn)的向量表示，效果顯著. Gjoka等[17]借鑒MH (Metropolis-Hasting)算法，改變RW等概率采樣鄰居節(jié)點(diǎn)的策略，提出無(wú)偏采樣算法(Metropolis-Hasting Random Walk，MHRW)，其采樣的樣本集更能全面的表達(dá)原始網(wǎng)絡(luò)的結(jié)構(gòu)特征[18-19]. 王文濤等[20]基于MHRW算法，刪除自環(huán)率，設(shè)計(jì)出RLP-MHRW(Remove self-Loop Probability for MHRW)算法，提高了NLP的表示性能. 劉思等[21]利用DeepWalk模型，通過(guò)將節(jié)點(diǎn)表征到低維向量空間獲得節(jié)點(diǎn)的潛在相似性來(lái)進(jìn)行鏈路預(yù)測(cè). Jin等[22]提出有擴(kuò)展和監(jiān)督的重啟隨機(jī)游走 (Random Walk with Restart，RWR)算法，使隨機(jī)游走更具表現(xiàn)性，并將其應(yīng)用于排序和鏈路預(yù)測(cè). 呂亞楠等[23]考慮節(jié)點(diǎn)度值對(duì)粒子轉(zhuǎn)移概率的影響，提出有偏向的鏈路預(yù)測(cè)算法，提升了預(yù)測(cè)的AUC指標(biāo).

基本隨機(jī)游走相似性指標(biāo)僅考慮當(dāng)前節(jié)點(diǎn)的度對(duì)轉(zhuǎn)移概率的影響而忽略了鄰居節(jié)點(diǎn)的貢獻(xiàn)，影響鏈路預(yù)測(cè)效果. 因此，本文在MH的基礎(chǔ)上，提出一種改進(jìn)的重啟隨機(jī)游走鏈路預(yù)測(cè)算法 (Improved MH with RWR，IMRWR). 算法在定義節(jié)點(diǎn)間的轉(zhuǎn)移概率時(shí)，綜合考慮當(dāng)前節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的度對(duì)轉(zhuǎn)移概率的影響，并將節(jié)點(diǎn)的自環(huán)率按鄰居節(jié)點(diǎn)的度值加權(quán)分配給鄰居節(jié)點(diǎn)，以增大游走粒子轉(zhuǎn)移到與其更加相似的節(jié)點(diǎn)上的概率，從而獲得相似節(jié)點(diǎn)的隨機(jī)游走序列，提高預(yù)測(cè)的準(zhǔn)確性.

1 相關(guān)工作

1.1 鏈路預(yù)測(cè)問(wèn)題描述設(shè)網(wǎng)絡(luò)G=(V,E) 表示無(wú)向圖，其中V={v1,v2,···,vN}表示節(jié)點(diǎn)集合，E={ei1,j1,ei2,j2,···,eiH,jH}表示連邊集合，網(wǎng)絡(luò)中不允許有自連邊和重邊. 節(jié)點(diǎn)vi,vj∈V間的連邊記為(vi,vj)或eij，節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合記為Γ(i)，記ki為節(jié)點(diǎn)vi的度. 如圖1所示，V={1,2,3,4,5}，E={(1,2),(2,3),(3,4),(3,5),(4,5)}，Γ(3)=(2,4,5)，k3=3. 在進(jìn)行鏈路預(yù)測(cè)實(shí)驗(yàn)時(shí)，連邊集合E將被劃分成訓(xùn)練集ET和測(cè)試集EP兩部分，有E=ET∪EP，ET∩EP=?，同時(shí)，由節(jié)點(diǎn)對(duì)構(gòu)成的連邊 (vi,vj) 將被賦予一個(gè)分?jǐn)?shù)值sij.

圖1 簡(jiǎn)單網(wǎng)絡(luò)示意圖Fig. 1 The diagrammatic graph of a simple network

在自然語(yǔ)言處理 (Natural Language Processing，NLP)中[24]，用鄰接矩陣A來(lái)表示并存儲(chǔ)網(wǎng)絡(luò)G，A為N×N的非零對(duì)稱矩陣，其中，元素ai j定義為

假定：①U為網(wǎng)絡(luò)中N個(gè)節(jié)點(diǎn)互連構(gòu)成的邊集合，則U中有 (N(N-1))/2 條邊；②B為不存在邊集，有B∈U，B?E；③W為未知邊集，有W∈U，W?ET且W=B∪EP. 由 圖1得，U={(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}，B={(1,3),(1,4),(1,5),(2,4),(2,5)}，鏈路預(yù)測(cè)即預(yù)測(cè)B中的邊未來(lái)會(huì)出現(xiàn)的概率大小. 圖2所示為邊集U,E,B,W,ET,EP的關(guān)系維恩圖.

圖2 邊集維恩圖Fig. 2 Venn diagram of edge set

1.2 RWR算法RWR[25]屬于基本的隨機(jī)游走相似性指標(biāo)，其假設(shè)游走粒子在每走一步時(shí)都按一定的概率返回初始節(jié)點(diǎn). 設(shè)粒子隨機(jī)選取下一個(gè)鄰居節(jié)點(diǎn)進(jìn)行游走的概率為c，則隨機(jī)返回初始節(jié)點(diǎn)的概率為 1-c，可得到網(wǎng)絡(luò)的轉(zhuǎn)移概率矩陣P，其中元素pij定義為

若初始時(shí)刻，游走粒子在節(jié)點(diǎn)vi處，則在t+1時(shí)刻，該粒子到達(dá)網(wǎng)絡(luò)中各節(jié)點(diǎn)的概率向量為

（3）式穩(wěn)態(tài)解為

其中，ei為粒子在節(jié)點(diǎn)vi處的初始狀態(tài)，其與I同為單位矩陣.

RWR相似性表達(dá)式為

其中，πi j為游走粒子從節(jié)點(diǎn)vi出發(fā)最終游走到節(jié)點(diǎn)vj的概率，πji表示反向概率.

由式(2)可知，在RWR方法中，游走粒子從節(jié)點(diǎn)vi轉(zhuǎn)移到鄰居節(jié)點(diǎn)vj的概率僅與當(dāng)前節(jié)點(diǎn)vi的度有關(guān).

2 基于改進(jìn)MH的IMRWR

在MH的基礎(chǔ)上，本文提出一種改進(jìn)的算法IMRWR，同時(shí)考慮當(dāng)前節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的度對(duì)轉(zhuǎn)移概率的影響，并將節(jié)點(diǎn)的自環(huán)率按鄰居節(jié)點(diǎn)的度值加權(quán)分配給鄰居節(jié)點(diǎn)，以增強(qiáng)轉(zhuǎn)移過(guò)程中表示出的節(jié)點(diǎn)相似性，再融合重啟隨機(jī)游走RWR相似性指標(biāo)進(jìn)行鏈路預(yù)測(cè).

2.1 MHRW算法基于MH算法的思想，Gjoka等結(jié)合RW提出無(wú)偏采樣算法MHRW[18]，其定義節(jié)點(diǎn)間的轉(zhuǎn)移概率rij為

rij表示從節(jié)點(diǎn)vi到其鄰居節(jié)點(diǎn)集合Γ(i)(包括自身節(jié)點(diǎn))中選取節(jié)點(diǎn)vj進(jìn)行采樣的轉(zhuǎn)移概率，當(dāng)vj=vi時(shí)，表示繼續(xù)采樣當(dāng)前節(jié)點(diǎn).

2.2 IMRWR算法思想在圖1的基礎(chǔ)上，根據(jù)式(6)計(jì)算出節(jié)點(diǎn)間的轉(zhuǎn)移概率，如圖3所示，自環(huán)率rii表示采樣當(dāng)前節(jié)點(diǎn)的概率. 然而，節(jié)點(diǎn)v1僅有一個(gè)鄰居v2，若從節(jié)點(diǎn)v1進(jìn)行采樣，下一個(gè)節(jié)點(diǎn)只能是v2，節(jié)點(diǎn)v1,v2間的轉(zhuǎn)移概率應(yīng)為r1,2=1. 但在MHRW中，節(jié)點(diǎn)v1的自環(huán)率高達(dá)0.5，自采樣概率偏高，干擾了深度采樣，從而影響游走粒子的轉(zhuǎn)移過(guò)程.

圖3 MHRW轉(zhuǎn)移概率圖Fig. 3 The transition probability graph of MHRW

為充分利用鄰居節(jié)點(diǎn)的度對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)間的轉(zhuǎn)移概率的作用效果，同時(shí)消除自環(huán)率的不利影響，增加節(jié)點(diǎn)間的轉(zhuǎn)移概率，使游走粒子能夠轉(zhuǎn)移到更加相似的節(jié)點(diǎn)上，以提高節(jié)點(diǎn)間的相似性. 本文利用MHRW算法，將當(dāng)前節(jié)點(diǎn)的自環(huán)率按鄰居節(jié)點(diǎn)的度值加權(quán)分配給鄰居節(jié)點(diǎn)，則節(jié)點(diǎn)間的轉(zhuǎn)移概率mi j為

其中，rii由式(6)中當(dāng)vi=vj時(shí)計(jì)算得到.

由式(7)可知，游走粒子在選取鄰居節(jié)點(diǎn)進(jìn)行游走時(shí)，既考慮當(dāng)前節(jié)點(diǎn)的度，又考慮其鄰居節(jié)點(diǎn)的度對(duì)轉(zhuǎn)移概率的影響，同時(shí)除去了自環(huán)率，使游走粒子能夠轉(zhuǎn)移到網(wǎng)絡(luò)的更深處尋找更加相似的節(jié)點(diǎn). 如圖4所示，從節(jié)點(diǎn)v1到v2的轉(zhuǎn)移概率由原來(lái)的0.5提高到1，從節(jié)點(diǎn)v5到v3的轉(zhuǎn)移概率由原來(lái)的0.333提高到0.433. 可見(jiàn)，本文IMRWR算法利用鄰居節(jié)點(diǎn)的度信息增加了節(jié)點(diǎn)間的轉(zhuǎn)移概率，使游走粒子轉(zhuǎn)移到相似節(jié)點(diǎn)的概率增大.

圖4 IMRWR轉(zhuǎn)移概率圖Fig. 4 The transition probability graph of IMRWR

2.3 算法流程根據(jù)式(6)得到MHRW算法的網(wǎng)絡(luò)轉(zhuǎn)移概率矩陣R. MHRW算法步驟如下：

算法1MHRW算法

輸入：網(wǎng)絡(luò)的鄰接矩陣，重啟因子c

輸出：節(jié)點(diǎn)間的相似性分?jǐn)?shù)矩陣

步驟1初始化：i=1，轉(zhuǎn)移矩陣R←0N×N，相似 性分?jǐn)?shù)矩陣S←IN×N.

步驟2利用式(6)計(jì)算各節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間的轉(zhuǎn)移概率，得到網(wǎng)絡(luò)的真實(shí)轉(zhuǎn)移矩陣R.

步驟3若i＜=N，執(zhí)行下一步；否，執(zhí)行步驟6.

步驟4利用式計(jì)算節(jié)點(diǎn)vi與其他節(jié)點(diǎn)間的相似性分?jǐn)?shù)值sij，并實(shí)時(shí)更新S.

步驟5判斷S是否收斂，若不收斂，i++，執(zhí)行步驟3；否則，執(zhí)行步驟6.

步驟6輸出S.

根據(jù)式(7)得到本文IMRWR算法的網(wǎng)絡(luò)轉(zhuǎn)移概率矩陣M. IMRWR算法步驟如下：

算法2IMRWR算法

輸入：網(wǎng)絡(luò)的鄰接矩陣，重啟因子c

輸出：節(jié)點(diǎn)間的相似性分?jǐn)?shù)矩陣

步驟1初始化：i=1，轉(zhuǎn)移矩陣M←0N×N，相似性分?jǐn)?shù)矩陣S←IN×N.

步驟2利用式(7)計(jì)算各節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)間的轉(zhuǎn)移概率，得到網(wǎng)絡(luò)的真實(shí)轉(zhuǎn)移矩陣M.

步驟3若i＜=N，執(zhí)行下一步；否，執(zhí)行步驟6.

步驟4利用式計(jì)算節(jié)點(diǎn)vi與其他節(jié)點(diǎn)間的相似性分?jǐn)?shù)值sij，并實(shí)時(shí)更新S.

步驟5判斷S是否收斂，若不收斂，i++，執(zhí)行步驟3；否則，執(zhí)行步驟6.

步驟6輸出S.

2.4 S 收斂性證明(1)因?yàn)檗D(zhuǎn)移矩陣R、M均為非負(fù)矩陣，游走粒子可以轉(zhuǎn)移到網(wǎng)絡(luò)G的任意節(jié)點(diǎn)，0＜c＜1，則網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)vi,vj間的相似性分?jǐn)?shù)sij都能得到，所以R、M是不可約的；

(2)重啟隨機(jī)游走中，當(dāng)游走粒子轉(zhuǎn)移到某一節(jié)點(diǎn)后，能否再次轉(zhuǎn)移到該節(jié)點(diǎn)是不確定的，說(shuō)明粒子的轉(zhuǎn)移過(guò)程是非周期的；

(3)粒子轉(zhuǎn)移到某一節(jié)點(diǎn)后返回初始節(jié)點(diǎn)，有可能在一定的步長(zhǎng)內(nèi)再次轉(zhuǎn)移到該節(jié)點(diǎn)，但兩次轉(zhuǎn)移到同一節(jié)點(diǎn)的步長(zhǎng)可能相同也可能不同，說(shuō)明粒子的轉(zhuǎn)移過(guò)程具有不確定性.

由以上3點(diǎn)可得，本文IMRWR算法是各態(tài)歷經(jīng)的[26]，說(shuō)明本文算法收斂，所以S也收斂.

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

3.1 實(shí)驗(yàn)基準(zhǔn)方法前人已經(jīng)提出了許多經(jīng)典的相似性鏈路預(yù)測(cè)算法，這些算法常作為基準(zhǔn)方法與提出的新算法進(jìn)行比較. 本文從3種類型的相似性指標(biāo)中選取7種具有代表性的算法作為基準(zhǔn)方法：①基于局部相似性的CN[27]，HPI[28]，AA[29]，PA[30]指標(biāo)；②基于路徑相似性的Katz[31]指標(biāo)；③基于隨機(jī)游走相似性的RWR[25]，ACT[32]指標(biāo).

(1) 共同鄰居 (Common Neighbors，CN)指標(biāo)CN指標(biāo)為最基本的相似性指標(biāo)，其相似性定義為兩個(gè)節(jié)點(diǎn)間共同鄰居的數(shù)目. 其相似性表達(dá)式為

(2) 大度節(jié)點(diǎn)有利 (Hub Promoted Index，HPI)指標(biāo) HPI指標(biāo)是在CN指標(biāo)的基礎(chǔ)上，并考慮了兩個(gè)相連節(jié)點(diǎn)度的影響. 其相似性表達(dá)式為

(3) AA(Adamic-Adar)指標(biāo) AA指標(biāo)根據(jù)共同鄰居節(jié)點(diǎn)的度為每對(duì)節(jié)點(diǎn)賦予一個(gè)權(quán)重值. 其相似性表達(dá)式為

(4) 優(yōu)先鏈接 (Preferential Attachment，PA)指標(biāo) PA指標(biāo)認(rèn)為新鏈接的節(jié)點(diǎn)對(duì)[vi,vj] 間的連接概率正比于兩個(gè)節(jié)點(diǎn)度的乘積. 其相似性表達(dá)式為

(5) 全局路徑Katz指標(biāo) Katz指標(biāo)考慮了網(wǎng)絡(luò)的所有路徑，其相似性表達(dá)式為

式中的數(shù)值解可通過(guò)該網(wǎng)絡(luò)的拉普拉斯矩陣L的偽逆矩陣L+求得.

其相似性表達(dá)式為

其中，H為網(wǎng)絡(luò)的總邊數(shù)，表示矩陣L+中第i行j列的位置對(duì)應(yīng)的元素.

3.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)驗(yàn)證鏈路預(yù)測(cè)算法準(zhǔn)確性的評(píng)價(jià)指標(biāo)主要有3種，分別是AUC、精確度(Precision)和排序分(Ranking Score). 這3種指標(biāo)的側(cè)重點(diǎn)不同，其中AUC指標(biāo)能從整體上評(píng)價(jià)算法的準(zhǔn)確性[33]，一直作為最主要的評(píng)價(jià)指標(biāo)；精確度指標(biāo)只計(jì)算預(yù)測(cè)前X條邊中預(yù)測(cè)的準(zhǔn)確率[34]；排序分指標(biāo)只考慮測(cè)試邊的最終排序情況[35]. 本文選取AUC和排序分兩種評(píng)價(jià)指標(biāo)作為評(píng)測(cè)依據(jù).

(1) AUC指標(biāo) AUC指標(biāo)定義為在測(cè)試集EP中隨機(jī)選擇一條邊的分?jǐn)?shù)值大于從不存在邊集B中隨機(jī)選擇一條邊的分?jǐn)?shù)值的概率，隨機(jī)比較n次，若有n′次分?jǐn)?shù)值高，每高一次加1分，有n′′次分?jǐn)?shù)值相等，每等一次加 0.5 分. AUC值定義為

AUC值在0～1之間，值越大的鏈路預(yù)測(cè)方法準(zhǔn)確性越高. 若所有的分?jǐn)?shù)sij都隨機(jī)產(chǎn)生，AUC≈0.5.

(2) 排序分(Ranking Score)指標(biāo) 排序分指標(biāo)只考慮測(cè)試邊e∈EP最終排列的位置，由1.1節(jié)定義可知，未知邊集合為W，設(shè)re為測(cè)試邊e在排序中的排名，則這條測(cè)試邊的排序分定義為

遍歷所有的測(cè)試邊，得到整個(gè)系統(tǒng)的排序分指標(biāo)為

排序分指標(biāo)與AUC指標(biāo)不同，分?jǐn)?shù)值越小預(yù)測(cè)越準(zhǔn)確.

3.3 實(shí)驗(yàn)數(shù)據(jù)集本文選取了7個(gè)不同領(lǐng)域、不同規(guī)模且具代表性的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，這些數(shù)據(jù)集均為無(wú)向網(wǎng)絡(luò). 數(shù)據(jù)集包括美國(guó)航空網(wǎng)絡(luò)(USAir)數(shù)據(jù)集、政治書(shū)籍網(wǎng)絡(luò)(PolBooks)數(shù)據(jù)集和電子郵件網(wǎng)絡(luò)(E-mail)數(shù)據(jù)集等. 7個(gè)數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)特征如表1. 其中，N表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，H表示網(wǎng)絡(luò)的邊數(shù)，〈K〉表示網(wǎng)絡(luò)的平均度，〈C〉 表示網(wǎng)絡(luò)的平均聚集系數(shù)，D表示網(wǎng)絡(luò)的相對(duì)直徑. 由表1可知，在給出的數(shù)據(jù)集中，Karate、Dolphin 、PolBooks為相對(duì)小規(guī)模網(wǎng)絡(luò)，C.elegens 、USAir 為相對(duì)中小規(guī)模網(wǎng)絡(luò)，E-mail、PolBlogs為相對(duì)大規(guī)模網(wǎng)絡(luò).

表1 各數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)特征Tab. 1 Network structure features of each dataset

3.4 實(shí)驗(yàn)結(jié)果分析實(shí)驗(yàn)參數(shù)設(shè)置：重啟因子c=0.85， 網(wǎng)絡(luò)測(cè)試集劃分比例 η=EP/E=10%. 每個(gè)數(shù)據(jù)集上獨(dú)立重復(fù)實(shí)驗(yàn) 50 次，評(píng)價(jià)指標(biāo)采用AUC和排序分，取平均值. 本文與7種基準(zhǔn)方法比較了AUC指標(biāo)，與MHRW、RWR算法比較了排序分指標(biāo). 實(shí)驗(yàn)結(jié)果如表2、表3及圖5、圖6所示. 表2比較了本文方法與各基準(zhǔn)算法在7個(gè)數(shù)據(jù)集上預(yù)測(cè)結(jié)果的AUC值. 表3比較了IMRWR算法與MHRW、RWR算法在7個(gè)數(shù)據(jù)集上預(yù)測(cè)結(jié)果的排序分. 圖5給出了同一類型的基準(zhǔn)方法在7個(gè)數(shù)據(jù)集上預(yù)測(cè)結(jié)果的AUC直方圖. 圖6給出了本文方法與基準(zhǔn)方法在7個(gè)數(shù)據(jù)集上預(yù)測(cè)結(jié)果的AUC折線圖和排序分折線圖.

由表2可知，與各基準(zhǔn)方法相比，本文IMRWR算法在7個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的AUC值均為最高，相較于MHRW算法也有提升. 由圖5(a)知，在局部相似性指標(biāo)CN、HPI、AA、PA中，AA指標(biāo)不僅考慮了共同鄰居，而且認(rèn)為共同鄰居中度小的節(jié)點(diǎn)對(duì)相似性的貢獻(xiàn)更大，因此其在局部相似性指標(biāo)中表現(xiàn)相對(duì)較好. 由圖5(b)知，Katz為路徑相似性指標(biāo)，因此其在考慮路徑的航空網(wǎng)絡(luò)USAir數(shù)據(jù)集上的AUC值最高，若將它應(yīng)用于路徑的預(yù)測(cè)會(huì)有很好的效果. RWR、ACT均為隨機(jī)游走相似性指標(biāo)，其中，RWR表現(xiàn)最佳，與RWR算法相比，本文IMRWR算法在AUC指標(biāo)上平均提升2.00%，最高提升可達(dá)3.98%. 同時(shí)，IMRWR算法在小規(guī)模數(shù)據(jù)集的AUC值提升比大于大規(guī)模數(shù)據(jù)集的提升比，說(shuō)明本文算法更有利于改善小數(shù)據(jù)集鏈路預(yù)測(cè)效果，并且AUC值隨著數(shù)據(jù)集規(guī)模增大而增大，說(shuō)明本文算法對(duì)大規(guī)模數(shù)據(jù)集上的鏈路預(yù)測(cè)同樣有效.

表2 在不同的基準(zhǔn)方法下各數(shù)據(jù)集的 AUC 值Tab. 2 The AUC value of each data set under different benchmark methods

表3 各數(shù)據(jù)集在不同的基準(zhǔn)方法下排序分值Tab. 3 The ranking score value of each data set under different benchmark methods

圖5 局部相似性指標(biāo)（a）與路徑相似性指標(biāo)（b）比較直方圖Fig. 5 The comparison histogram of local similarity index (a) and path similarity index (b)

圖6 AUC指標(biāo)（a）與排序分指標(biāo)（b）比較折線圖Fig. 6 The comparison line chart of AUC index (a) and Ranking Score index (b)

由表3知，IMRWR算法在7個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的排序分均比MHRW、RWR算法低，與RWR算法相比，平均下降0.99%，最高下降1.92%，也說(shuō)明了IMRWR算法可提升預(yù)測(cè)準(zhǔn)確性. 由圖6(a)可知，同一算法在不同類型的數(shù)據(jù)集上AUC值波動(dòng)明顯，且同一數(shù)據(jù)集利用不同的預(yù)測(cè)方法得到的預(yù)測(cè)結(jié)果相差較大，說(shuō)明不同的預(yù)測(cè)方法有著各自側(cè)重的預(yù)測(cè)數(shù)據(jù)集. 而本文算法與其他算法相比，在7個(gè)數(shù)據(jù)集的AUC值波動(dòng)相對(duì)平緩，說(shuō)明本文算法有著更加穩(wěn)定的預(yù)測(cè)性能. 且由圖6(b)可知，IMRWR算法與RWR算法的預(yù)測(cè)結(jié)果走勢(shì)基本相同，說(shuō)明IMRWR算法有著一定的魯棒性.

4 結(jié)束語(yǔ)

本文針對(duì)重啟隨機(jī)游走相似性指標(biāo)忽略鄰居節(jié)點(diǎn)的度對(duì)轉(zhuǎn)移概率產(chǎn)生影響，提出一種改進(jìn)MH的重啟隨機(jī)游走鏈路預(yù)測(cè)算法IMRWR. 該算法在定義網(wǎng)絡(luò)節(jié)點(diǎn)間的轉(zhuǎn)移概率時(shí)，綜合考慮了當(dāng)前節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的度對(duì)粒子轉(zhuǎn)移過(guò)程的影響，并將自環(huán)率按鄰居節(jié)點(diǎn)的度值加權(quán)分配給鄰居節(jié)點(diǎn)，從而使游走粒子能夠轉(zhuǎn)移到更加相似的節(jié)點(diǎn)上，以提高隨機(jī)游走獲得的節(jié)點(diǎn)序列中各節(jié)點(diǎn)的相似性. 實(shí)驗(yàn)結(jié)果表明，本文所提算法在AUC指標(biāo)和排序分指標(biāo)上均有改善，在AUC指標(biāo)上平均提升2.00%，最高提升3.98%；在排序分指標(biāo)上平均下降0.99%，最高下降1.92%，提升了鏈路預(yù)測(cè)的準(zhǔn)確性.下一步，我們將考慮結(jié)合邊權(quán)值對(duì)轉(zhuǎn)移概率的貢獻(xiàn)，研究有權(quán)網(wǎng)絡(luò)的鏈路預(yù)測(cè)性能.