基于拓?fù)溆行нB通路徑的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

李治成，吉立新，劉樹(shù)新，李 星，李勁松

(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001)

隨著網(wǎng)絡(luò)科學(xué)的發(fā)展，復(fù)雜網(wǎng)絡(luò)成為了重要的研究?jī)?nèi)容[1-5]。生活中的很多復(fù)雜系統(tǒng)都可以抽象為網(wǎng)絡(luò)來(lái)表示，不同類型的網(wǎng)絡(luò)如交通網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、蛋白質(zhì)作用關(guān)系網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等均是復(fù)雜網(wǎng)絡(luò)的研究對(duì)象。而鏈路預(yù)測(cè)作為復(fù)雜網(wǎng)絡(luò)的研究方向，旨在利用已有的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)現(xiàn)網(wǎng)絡(luò)中缺失的連邊、錯(cuò)誤的連邊和未來(lái)可能產(chǎn)生的連邊[6-8]。鏈路預(yù)測(cè)應(yīng)用于諸多領(lǐng)域，如在社交網(wǎng)絡(luò)中用于好友推薦[9]，生物網(wǎng)絡(luò)中用于發(fā)現(xiàn)未知的生物結(jié)構(gòu)[10]，以及引文網(wǎng)絡(luò)中發(fā)現(xiàn)科學(xué)家之間的合作關(guān)系[11]等。

當(dāng)前，鏈路預(yù)測(cè)的研究已經(jīng)取得較顯著的成果?；谕?fù)浣Y(jié)構(gòu)的鏈路預(yù)測(cè)方法因簡(jiǎn)單、高效而備受關(guān)注[12-14]，根據(jù)拓?fù)浣Y(jié)構(gòu)信息可將鏈路預(yù)測(cè)方法分為基于局部結(jié)構(gòu)、基于半局部結(jié)構(gòu)和基于全局結(jié)構(gòu)3 種方法[15]?；诰植拷Y(jié)構(gòu)信息的預(yù)測(cè)方法假設(shè)如果節(jié)點(diǎn)越相似，產(chǎn)生連接的可能性越大，其中以共同鄰居結(jié)構(gòu)為出發(fā)點(diǎn)已有較多的研究方法，AA 指標(biāo)對(duì)共同鄰居的大度節(jié)點(diǎn)進(jìn)行懲罰，CAR 方法考慮共同鄰居節(jié)點(diǎn)之間相互交互[15]。文獻(xiàn)[16]對(duì)資源分配指標(biāo)RA 進(jìn)行了改進(jìn)，提出擴(kuò)展的資源分配指標(biāo)。全局信息考慮網(wǎng)絡(luò)的全局結(jié)構(gòu)，例如考慮全局路徑的Katz 方法[17]，基于隨機(jī)游走的節(jié)點(diǎn)偏好性游走指標(biāo)(degree-biased random walk, DRW)[18]和有重啟的隨機(jī)游走指標(biāo)(random walk with restart,RWR)[19]等，全局方法預(yù)測(cè)結(jié)果優(yōu)于局部指標(biāo)，但因其時(shí)間復(fù)雜度高不適用于大型網(wǎng)絡(luò)。文獻(xiàn)[20]提出的局部路徑方法(local path, LP)在共同鄰居的基礎(chǔ)上考慮了三階鄰居所起的作用，在大部分網(wǎng)絡(luò)中預(yù)測(cè)結(jié)果與Katz 方法相近。目前已有大量的鏈路預(yù)測(cè)方法，但現(xiàn)存的方法忽略了預(yù)測(cè)節(jié)點(diǎn)對(duì)之間的連邊長(zhǎng)度和連邊上不同節(jié)點(diǎn)的影響力對(duì)相似性的貢獻(xiàn)。節(jié)點(diǎn)對(duì)之間的相似性不僅與路徑的長(zhǎng)度有關(guān)，還與路徑上的節(jié)點(diǎn)的影響力有關(guān)，節(jié)點(diǎn)影響力挖掘方法不同，連邊傳遞的有效性也將不同。此外，還需探討不同挖掘方法下節(jié)點(diǎn)影響力對(duì)相似性的貢獻(xiàn)。

因此，本文分析了網(wǎng)絡(luò)在不同路徑長(zhǎng)度和節(jié)點(diǎn)影響力下對(duì)節(jié)點(diǎn)相似性的貢獻(xiàn)，提出基于拓?fù)溆行нB通路徑的鏈路預(yù)測(cè)方法。而節(jié)點(diǎn)在網(wǎng)絡(luò)中影響力的挖掘方法較多，為減少時(shí)間復(fù)雜度，本文主要從節(jié)點(diǎn)的出入度、半局部中心性和H-指數(shù)3 種中心性衡量指標(biāo)來(lái)量化節(jié)點(diǎn)的局部影響力，并使用相應(yīng)的方法來(lái)量化連邊的傳遞能力。通過(guò)在多種實(shí)際網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，驗(yàn)證了節(jié)點(diǎn)之間的相似性不僅與路徑長(zhǎng)度有關(guān)，還與節(jié)點(diǎn)影響力有關(guān)。

1 相關(guān)工作介紹

11) propflow[25]：該方法是一種有監(jiān)督的隨機(jī)游走方法，計(jì)算從源節(jié)點(diǎn)x開(kāi)始以一定步長(zhǎng)或更少的步長(zhǎng)到達(dá)節(jié)點(diǎn)y的概率。

2 基于拓?fù)溆行нB通路徑的有向網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

2.1 拓?fù)溥B通度的分析量化

傳統(tǒng)的鏈路預(yù)測(cè)方法研究中，認(rèn)為端點(diǎn)的影響力有助于連邊的形成，且影響力大的節(jié)點(diǎn)之間更傾向于連接[26]。而網(wǎng)絡(luò)中端點(diǎn)間實(shí)際通過(guò)路徑建立聯(lián)系，并通過(guò)建立的關(guān)系來(lái)傳遞影響力，從而發(fā)生相似性傳遞。而網(wǎng)絡(luò)中相似節(jié)點(diǎn)對(duì)之間往往存在多條路徑，路徑結(jié)構(gòu)的差異將影響相似性的傳遞。圖1給出了拓?fù)浣Y(jié)構(gòu)與信息傳輸路徑的示意圖。信息從多條路徑傳遞到y(tǒng)，結(jié)構(gòu)的差異將影響路徑連通度大小。對(duì)于相同長(zhǎng)度路徑，x→a→y和x→b→y，傳遞到y(tǒng)的信息與中繼節(jié)點(diǎn)有關(guān)，中繼節(jié)點(diǎn)的出入度不同，連邊的連通度也不同。對(duì)于不同長(zhǎng)度的路徑x→a→y和x→b→e→f→y，分別通過(guò)2 跳和4 跳到達(dá)，節(jié)點(diǎn)信息在傳遞過(guò)程中往往隨著長(zhǎng)度的增加而減少，不如短路徑傳遞的信息有效。而最終y獲取到的有效信息是多條路徑的疊加。因此，需要從拓?fù)浣Y(jié)構(gòu)對(duì)信息傳輸過(guò)程影響的角度，分析刻畫(huà) 拓?fù)渎窂降倪B通度。

圖1 網(wǎng)絡(luò)中信息傳輸過(guò)程分析示意圖

圖2 不同路徑長(zhǎng)度下相似性傳遞過(guò)程分析

其次，節(jié)點(diǎn)間路徑的長(zhǎng)短雖然重要，但路徑中節(jié)點(diǎn)的差異性也決定了路徑能傳遞的信息多少，還需分析路徑連通度與中繼節(jié)點(diǎn)的關(guān)系。節(jié)點(diǎn)影響力描述了節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度，且節(jié)點(diǎn)影響力能夠決定節(jié)點(diǎn)在路徑中捕獲資源和信息的能力[27]，路徑中傳遞資源往往偏向于影響力大的節(jié)點(diǎn)。文獻(xiàn)[28]證實(shí)了在電力網(wǎng)絡(luò)中，節(jié)點(diǎn)的度與承受的電力負(fù)荷成正比，現(xiàn)實(shí)生活中“富者愈富”的現(xiàn)象也說(shuō)明影響力大的節(jié)點(diǎn)在網(wǎng)絡(luò)中占有優(yōu)勢(shì)[29]。在有向網(wǎng)絡(luò)中，相連節(jié)點(diǎn)之間的路徑連通度與中繼節(jié)點(diǎn)的出入邊的影響力有關(guān)。在圖3 所示的網(wǎng)絡(luò)結(jié)構(gòu)中，如果僅以節(jié)點(diǎn)出入度作為判斷節(jié)點(diǎn)影響力的大小，則節(jié)點(diǎn)z2具有較高影響力，節(jié)點(diǎn)x傳遞資源時(shí)偏向于z2，但由于影響力大的中繼節(jié)點(diǎn)能傳遞的連邊較多，最終能傳遞到相鄰節(jié)點(diǎn)y的資源較小，即中繼節(jié)點(diǎn)影響力低且路徑短的預(yù)測(cè)節(jié)點(diǎn)之間的連邊連通度較大。

圖3 中繼節(jié)點(diǎn)與路徑連通度的關(guān)系分析

可以看出，任意一條路徑信息傳輸?shù)挠行钥梢粤炕癁槁窂介L(zhǎng)度和路徑中節(jié)點(diǎn)影響力對(duì)信息傳遞能力的影響。然而，有向網(wǎng)絡(luò)中影響力的挖掘方法較多，不同網(wǎng)絡(luò)中，中心性衡量存在差異，因此，本文還分析了在不同節(jié)點(diǎn)度中心性指標(biāo)下對(duì)路徑連通度的貢獻(xiàn)。目前已有的中心性方法并不能完全挖掘節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力，為減少時(shí)間復(fù)雜度，主要利用局部結(jié)構(gòu)方法定義節(jié)點(diǎn)的重要程度，選取基于節(jié)點(diǎn)的度中心性、節(jié)點(diǎn)的半局部中心性和H-指數(shù)3 種中心性指標(biāo)量化節(jié)點(diǎn)的入邊和出邊影響力，并給出了相應(yīng)方法的路徑連通度的表達(dá)式，具體方法定義如下。

2.2 預(yù)測(cè)方法提出

為了從路徑有效性對(duì)信息傳輸影響的角度刻畫(huà)任意兩點(diǎn)間的相似性，將基于路徑傳輸影響因素分析節(jié)點(diǎn)間信息傳輸能力?！叭扔绊懥Α闭J(rèn)為人與人之間相互影響，且影響力的傳遞是在三度以內(nèi)，超出三度節(jié)點(diǎn)，影響力將會(huì)逐漸消失[31]，當(dāng)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間經(jīng)過(guò)三跳或者更多跳路徑時(shí)，相似性傳遞也將隨著路徑長(zhǎng)度的增加而無(wú)法有效的傳遞到目標(biāo)節(jié)點(diǎn)?！傲确指罾碚摗闭J(rèn)為世界上任何兩個(gè)陌生人之間的距離不超過(guò)6 個(gè)人，也就是說(shuō)，每個(gè)人最多通過(guò)6 個(gè)人就可以認(rèn)識(shí)世界上任何一個(gè)陌生人[32]。兼顧“三度影響力”和“六度分割理論”，將兩度節(jié)點(diǎn)和六度節(jié)點(diǎn)之間的路徑稱為拓?fù)溆行нB通路徑，并從信息傳遞的角度定義了相關(guān)方法。

3 衡量指標(biāo)和數(shù)據(jù)集介紹

3.1 衡量指標(biāo)

對(duì)于給定的鏈路預(yù)測(cè)方法，通過(guò)計(jì)算節(jié)點(diǎn)對(duì)之間的相似性得分來(lái)衡量未連接的節(jié)點(diǎn)對(duì)之間的相似性，本文通過(guò)AUC(area under receiver operating characteristic curve)、precision、排序分(ranking score,RS)來(lái)衡量預(yù)測(cè)精確度，將有向網(wǎng)絡(luò)G(V,E)的連邊E分為訓(xùn)練集ET和測(cè)試集EP，滿足EP∪ET=E，且EP∩ET=φ。

AUC 為隨機(jī)從測(cè)試集EP中隨機(jī)選取一條邊的分?jǐn)?shù)值比未連接邊的分?jǐn)?shù)值大的概率[33]。如果選取的測(cè)試邊的分?jǐn)?shù)值有n′條大于未連接邊的分?jǐn)?shù)值，則加n′分，若分?jǐn)?shù)值相等的有n′′條 ，則加 0.5n′′分，AUC 的計(jì)算公式表達(dá)為：

式中：λ為預(yù)測(cè)的響應(yīng)值； α0 為常系數(shù)；αi為線性系數(shù)；αii為二次方系數(shù)；αij為相互作用系數(shù)；χi，χj 為實(shí)驗(yàn)因素。

1) FWEW[35]：生活在Everglasdes Gramininoids的濕季生物構(gòu)成的食物鏈網(wǎng)絡(luò)，節(jié)點(diǎn)表示物種，連邊表示物種之間的捕食關(guān)系；

2) High-school (HIG)[36]：描述美國(guó)伊利諾伊州某高中男生間建立的朋友關(guān)系網(wǎng)絡(luò)。數(shù)據(jù)集中每個(gè)用戶被問(wèn)誰(shuí)是朋友，A→B表示用戶A認(rèn)為B是A的朋友；

3.2 網(wǎng)絡(luò)數(shù)據(jù)介紹

本文選取了不同類型的有向網(wǎng)絡(luò)用于預(yù)測(cè)驗(yàn)證，數(shù)據(jù)集介紹如下：

3) Residence_hall (RES)[36]：澳大利亞國(guó)立大學(xué)朋友關(guān)系網(wǎng)絡(luò)，與HIG 類似；

4) CollegeMessage (CM)[36]：一個(gè)由加州大學(xué)歐文分校構(gòu)成的郵件網(wǎng)絡(luò)構(gòu)成的社交網(wǎng)絡(luò)；

5) Political_blogs (PB)[37]：美國(guó)政治博客網(wǎng)絡(luò)，節(jié)點(diǎn)表示網(wǎng)頁(yè)，連邊表示網(wǎng)頁(yè)之間的連邊關(guān)系；

6) Scimet[38]：引用“科學(xué)計(jì)量學(xué)”的論文引文網(wǎng)絡(luò)，節(jié)點(diǎn)表示論文，連邊表示論文引用關(guān)系；

7) SmaGri2[38]：一個(gè)由Small & Griffith and Descendants 相關(guān)的論文引用網(wǎng)絡(luò)，節(jié)點(diǎn)表示論文，連邊表示引用關(guān)系；

8) Air traffic control (AIR)[36]：由美國(guó)國(guó)家聯(lián)邦航空局飛行數(shù)據(jù)中心構(gòu)建的航空網(wǎng)絡(luò)，節(jié)點(diǎn)表示機(jī)場(chǎng)或者服務(wù)中心，連邊表示飛行路線。

表1 使用網(wǎng)絡(luò)數(shù)據(jù)參數(shù)說(shuō)明

上述的網(wǎng)絡(luò)具體參數(shù)特征如表1 所示，包括網(wǎng)絡(luò)類型Type、節(jié)點(diǎn)數(shù)|V|、 邊數(shù)|E|、最大入度MID、最大出度MOD、平均度 〈k〉、 平均距離 〈d〉、聚類系數(shù)C。實(shí)驗(yàn)中，設(shè)置訓(xùn)練集和測(cè)試集所占的比例為9:1，每個(gè)實(shí)驗(yàn)結(jié)果均為50 次實(shí)驗(yàn)結(jié)果的均值。

4 實(shí)驗(yàn)分析

為了驗(yàn)證路徑的有效傳播在鏈路預(yù)測(cè)方法中的作用，在8 個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)首先分析路徑中節(jié)點(diǎn)影響力與拓?fù)渎窂接行нB通的關(guān)系，并對(duì)不同路徑長(zhǎng)度下的有效連通度進(jìn)行對(duì)比。

4.1 中心度方法之間對(duì)比分析

圖4 為EPD、EPLC、EPH 在8 個(gè)真實(shí)網(wǎng)絡(luò)中的AUC 性能曲線，本文取節(jié)點(diǎn)之間最長(zhǎng)的路徑為10，以驗(yàn)證節(jié)點(diǎn)之間的有效路徑連通度是否在6 步以內(nèi)。首先對(duì)比不同的網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)中心度量化方法之間的差異度，根據(jù)曲線變化可以看出EPLC的預(yù)測(cè)結(jié)果波動(dòng)性較大，在有的網(wǎng)絡(luò)中表現(xiàn)較好，有的網(wǎng)絡(luò)中表現(xiàn)較差，在EPD 和EPH 表現(xiàn)相對(duì)較好，且EPH 優(yōu)于EPD。因此，相比于節(jié)點(diǎn)度中心、節(jié)點(diǎn)的半局部中心的中心衡量指標(biāo)，H-指數(shù)更適用于量化節(jié)點(diǎn)的影響力。信息在傳遞過(guò)程中，并不是所有量化方法都能準(zhǔn)確衡量出節(jié)點(diǎn)的影響力，H-指數(shù)考慮鄰居節(jié)點(diǎn)個(gè)數(shù)的同時(shí)，還考慮了鄰居節(jié)點(diǎn)的質(zhì)量，能有效計(jì)算連邊傳遞的相似性，因此該方法表現(xiàn)較好且穩(wěn)定。EPD 僅根據(jù)節(jié)點(diǎn)的出入度量化節(jié)點(diǎn)的影響力，并不能充分挖掘節(jié)點(diǎn)的重要程度。EPLC 在EPD 的基礎(chǔ)上考慮了局部鄰居節(jié)點(diǎn)的數(shù)目，近似地計(jì)算了節(jié)點(diǎn)在全局網(wǎng)絡(luò)中的相對(duì)作用大小，但應(yīng)用于鏈路預(yù)測(cè)的時(shí)候，預(yù)測(cè)精度較低，且穩(wěn)定性較差。

圖4 不同中心度方法之間AUC 對(duì)比分析

不同游走步數(shù)下，AUC 表現(xiàn)各不相同，說(shuō)明不同路徑長(zhǎng)度下對(duì)節(jié)點(diǎn)的相似性貢獻(xiàn)不同。當(dāng)游走長(zhǎng)度為2 時(shí)，計(jì)算的是粒子從源節(jié)點(diǎn)出發(fā)兩步到達(dá)目標(biāo)節(jié)點(diǎn)的相似度，從預(yù)測(cè)結(jié)果中可以看出，大部分網(wǎng)絡(luò)中的AUC 預(yù)測(cè)精度并不是很高。在CM 網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)中節(jié)點(diǎn)具有較高的平均度，和節(jié)點(diǎn)之間平均距離較大，當(dāng)網(wǎng)絡(luò)中具有較多大度節(jié)點(diǎn)時(shí)并不能促進(jìn)相似節(jié)點(diǎn)產(chǎn)生，當(dāng)路徑長(zhǎng)度為2～4 時(shí)，EPD 方法沒(méi)有準(zhǔn)確對(duì)連邊的連通度進(jìn)行衡量，在計(jì)算節(jié)點(diǎn)之間的相似性得分的時(shí)候，增加了干擾信息，造成EPD 方法在網(wǎng)絡(luò)中隨著路徑的增長(zhǎng)預(yù)測(cè)精度下降，但當(dāng)路徑長(zhǎng)度大于4 時(shí)候，路徑的連通度變得微乎其微，因此，路徑長(zhǎng)度為4 之后預(yù)測(cè)精度逐漸趨于穩(wěn)定。而在Air 航空網(wǎng)絡(luò)中平均距離較大，當(dāng)一個(gè)機(jī)場(chǎng)有多條路徑可達(dá)一個(gè)機(jī)場(chǎng)時(shí)，說(shuō)明該機(jī)場(chǎng)可能是一個(gè)大型國(guó)際機(jī)場(chǎng)，目標(biāo)節(jié)點(diǎn)越重要，與其產(chǎn)生連接的可能性越大，所以AUC 結(jié)果會(huì)增加。可以看出，在所有網(wǎng)絡(luò)中，3 種節(jié)點(diǎn)量化節(jié)點(diǎn)重要性的方法均隨著路徑長(zhǎng)度的增加而改變，在大部分網(wǎng)絡(luò)中，當(dāng)路徑長(zhǎng)度達(dá)到6 時(shí)基本趨于穩(wěn)定。因此，節(jié)點(diǎn)之間的拓?fù)渎窂接行нB通路徑在2 度和6 度節(jié)點(diǎn)之間。

4.2 不同預(yù)測(cè)方法對(duì)比分析

基于不同中心度量化節(jié)點(diǎn)影響力的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)游走的步長(zhǎng)為6 時(shí)AUC 值趨于穩(wěn)定，為了便于與其他鏈路預(yù)測(cè)方法進(jìn)行對(duì)比分析，同時(shí)兼顧六度分割理論，EPD、EPLC、EPH 游走的步長(zhǎng)l值均為6，使用AUC、precision、排序分3 種衡量指標(biāo)進(jìn)行評(píng)價(jià)。

4.2.1 AUC 實(shí)驗(yàn)對(duì)比分析

表2 給出了AUC 的對(duì)比分析，Katz.01 表示調(diào)節(jié)參數(shù)α 的取值為0.01，LRW_3 中3 表示游走的步數(shù)為3。通過(guò)對(duì)比分析可以得出，基于H-指數(shù)量化的方法表現(xiàn)較好，在Scimet、SmaGri2、AIR 網(wǎng)絡(luò)中EPD、EPLC 均比EPH 差，說(shuō)明在一些網(wǎng)絡(luò)中影響力的有效傳播與連邊的量化方式相關(guān)，并不是所有的量化方法都能有效量化連邊影響力。4 種局部指標(biāo)DCN、DAA、DRA、DPA 考慮的網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單，在各種類型的網(wǎng)絡(luò)中表現(xiàn)差異較大。而LP在共同鄰居(DCN)的基礎(chǔ)上考慮了三階路徑所起的作用，有較大的改進(jìn)。全局方法Katz 因考慮全局網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息均表現(xiàn)最好。而隨機(jī)游走方法局部隨機(jī)游走和有疊加效應(yīng)的隨機(jī)游走方法在不同的網(wǎng)絡(luò)中表現(xiàn)差距較大，在規(guī)模相對(duì)較大的網(wǎng)絡(luò)Scimet 中表現(xiàn)較好，小規(guī)模網(wǎng)絡(luò)中預(yù)測(cè)的AUC 值幾乎接近于0，而ACT 方法在所有預(yù)測(cè)方法中是最差的，說(shuō)明相似性在傳遞過(guò)程中并不一定能傳遞到目標(biāo)節(jié)點(diǎn)，且該方法時(shí)間復(fù)雜度較高。Bifan 在食物鏈方法中預(yù)測(cè)精度較高，超過(guò)了考慮全局信息的Katz 方法，而此網(wǎng)絡(luò)結(jié)構(gòu)并不適用于其他類型的網(wǎng)絡(luò)，說(shuō)明食物鏈網(wǎng)絡(luò)在演化過(guò)程中產(chǎn)生較多的Bifan 結(jié)構(gòu)，能有效提升食物鏈網(wǎng)絡(luò)中的預(yù)測(cè)精度。

表2 AUC 結(jié)果分析

縱向?qū)Ρ确治霭l(fā)現(xiàn)在航空網(wǎng)絡(luò)AIR 數(shù)據(jù)集上，Katz.01 時(shí)預(yù)測(cè)精度較高，而LP 方法預(yù)測(cè)結(jié)果與其相差接近0.2，說(shuō)明在該網(wǎng)絡(luò)中，路徑越長(zhǎng)，航班之間直飛的可能性越大。而改進(jìn)后的EPD、EPH 預(yù)測(cè)結(jié)果與Katz.01 相差不大，考慮路徑的異構(gòu)性確實(shí)能促進(jìn)節(jié)點(diǎn)對(duì)之間的相似。在DCN 基礎(chǔ)上改進(jìn)的DAA 指標(biāo)，在RES 和AIR 網(wǎng)絡(luò)中預(yù)測(cè)精度提高較大，大度節(jié)點(diǎn)在這兩個(gè)網(wǎng)絡(luò)中抑制節(jié)點(diǎn)對(duì)之間的相似連接，而在其余網(wǎng)絡(luò)中預(yù)測(cè)結(jié)果均無(wú)改進(jìn)。對(duì)于大部分網(wǎng)絡(luò)，PA 方法結(jié)果具有較高的預(yù)測(cè)精度，很好的解釋了“富者愈富”的現(xiàn)象，節(jié)點(diǎn)更傾向于和大度節(jié)點(diǎn)相連接。而本文方法針對(duì)不同的網(wǎng)絡(luò)結(jié)構(gòu)，路徑的有效連通度并不相同，在各種連邊量化的方法中EPH 方法具有較高的預(yù)測(cè)精度，所有網(wǎng)絡(luò)均具有較好的表現(xiàn)，能較好地量化節(jié)點(diǎn)對(duì)之間的連邊的連通度，也進(jìn)一步說(shuō)明有效的鄰居節(jié)點(diǎn)確實(shí)能提高節(jié)點(diǎn)之間的相似性。

4.2.2 precision 結(jié)果分析

表3 給出了precision 的結(jié)果，可以看出，預(yù)測(cè)結(jié)果與AUC 結(jié)果差不多，食物鏈網(wǎng)絡(luò)中依舊bifan 結(jié)構(gòu)最高，4 種局部結(jié)構(gòu)中，PA 在食物鏈網(wǎng)絡(luò)中表現(xiàn)較好，LP 和Katz 方法的預(yù)測(cè)精度較為接近；3 種隨機(jī)游走方法ACT、LRW_3、SRW_3預(yù)測(cè)準(zhǔn)確度較低，但在社交網(wǎng)絡(luò)中表現(xiàn)較好，而在大型網(wǎng)絡(luò)中預(yù)測(cè)精度幾乎為0；在小規(guī)模網(wǎng)絡(luò)的社交網(wǎng)絡(luò)RES、HIG 預(yù)測(cè)結(jié)果較好，可能隨機(jī)游走的指標(biāo)在大規(guī)模網(wǎng)絡(luò)中更適合AUC。在CM 網(wǎng)絡(luò)中，相比Katz0.01 預(yù)測(cè)精度提升了1%，且時(shí)間復(fù)雜度遠(yuǎn)小于Katz。在CN 基礎(chǔ)上改進(jìn)的AA、RA 指標(biāo)，在引文網(wǎng)絡(luò)Scimet、Smagri2 和航空網(wǎng)絡(luò)中精度較差，引文網(wǎng)絡(luò)和航空網(wǎng)絡(luò)節(jié)點(diǎn)的度與重要程度成正比，重要節(jié)點(diǎn)并不會(huì)抑制網(wǎng)絡(luò)連邊的L 形成。考慮了有效路徑連通度之后，EPH 的precision結(jié)果在除了生物網(wǎng)絡(luò)之外的所有網(wǎng)絡(luò)中表現(xiàn)均較好，說(shuō)明節(jié)點(diǎn)的影響力不僅與節(jié)點(diǎn)自身有關(guān)，還與鄰居節(jié)點(diǎn)的重要性相關(guān)，在量化鄰居節(jié)點(diǎn)重要性的基礎(chǔ)上，EPH 方法能有效計(jì)算路徑的連通度。

表3 precision 結(jié)果分析

4.2.3 排序分結(jié)果分析

表4 為排序分的實(shí)驗(yàn)結(jié)果，與AUC、precison預(yù)測(cè)結(jié)果不同，該衡量指標(biāo)的預(yù)測(cè)結(jié)果越小，精度越高，即預(yù)測(cè)結(jié)果越排在前，證明方法的可行性越好。從表4 的預(yù)測(cè)結(jié)果中可以看出，EPH 方法表現(xiàn)的結(jié)果依舊較好，局部指標(biāo)CN、AA、RA 預(yù)測(cè)結(jié)果較為接近，因?yàn)檫@3 種方法網(wǎng)絡(luò)結(jié)構(gòu)相同。在不同的度中心衡量方法中，EPLC 的預(yù)測(cè)結(jié)果最差，說(shuō)明該方法并不能有效量化路徑連通度，考慮的網(wǎng)絡(luò)結(jié)構(gòu)不適合應(yīng)用于該鏈路預(yù)測(cè)中。而隨機(jī)游走方法LRW_3、SRW_3 偏差較大，在SmaGri2、AIR 網(wǎng)絡(luò)，排序結(jié)果均錯(cuò)誤，可能與取的游走方向和步數(shù)有關(guān)。相比于局部方法，PA 排序結(jié)果較好，對(duì)大部分網(wǎng)絡(luò)能準(zhǔn)確地將連邊出現(xiàn)的概率進(jìn)行排序。在所改進(jìn)的方法中，EPLC 在EPD 的基礎(chǔ)上考慮了節(jié)點(diǎn)在局部結(jié)構(gòu)中的相對(duì)重要性，排序結(jié)果較差。綜合對(duì)比，在局部網(wǎng)絡(luò)結(jié)構(gòu)中，使用H-指數(shù)量化路徑中節(jié)點(diǎn)影響力的方法最為有效。

表4 排序分結(jié)果分析

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

近年來(lái)，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相似性的鏈路預(yù)測(cè)方法備受學(xué)者關(guān)注，已提出了較多方法。大部分方法將節(jié)點(diǎn)的度構(gòu)建為節(jié)點(diǎn)的影響力，影響力越大，與之產(chǎn)生連接的可能性越大，但連邊的建立本質(zhì)上與路徑的有效性連通有關(guān)，路徑上中繼節(jié)點(diǎn)的影響力將影響連邊的建立。本文將節(jié)點(diǎn)影響力應(yīng)用于有向網(wǎng)絡(luò)鏈路預(yù)測(cè)中，通過(guò)多種方法量化路徑的連通能力。在多個(gè)實(shí)際網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，結(jié)果表明，對(duì)于相同的游走步數(shù)，用基于H-指數(shù)更適合表示節(jié)點(diǎn)的影響力，能有效量化路徑的有效連通度，而當(dāng)有多條路徑可達(dá)目標(biāo)節(jié)點(diǎn)時(shí)，3 階以上路徑對(duì)節(jié)點(diǎn)之間的相似性傳遞貢獻(xiàn)較小。本文所提出的方法說(shuō)明路徑的有效連通度不僅與路徑長(zhǎng)度有關(guān)，還與路徑上的節(jié)點(diǎn)影響力有關(guān)。此外，該預(yù)測(cè)方法能應(yīng)用于大型網(wǎng)絡(luò)，能有效地揭示連邊的形成機(jī)理和網(wǎng)絡(luò)的演化機(jī)制。