劉宇航，尹小慶，林 云

（1.重慶大學(xué) 機(jī)械與運(yùn)載工程學(xué)院，重慶 400044；2.重慶大學(xué) 管理科學(xué)與房地產(chǎn)學(xué)院，重慶 400044）

0 概述

鏈路預(yù)測是根據(jù)網(wǎng)絡(luò)中的已有節(jié)點(diǎn)信息來預(yù)測缺失的節(jié)點(diǎn)或鏈路，它是運(yùn)用微觀層面網(wǎng)絡(luò)演化機(jī)制進(jìn)行預(yù)測的重要方法。依據(jù)網(wǎng)絡(luò)特征提取角度的不同，現(xiàn)有鏈路預(yù)測可分為基于相似性、基于極大似然估計(jì)、基于概率模型、基于機(jī)器學(xué)習(xí)這4 類方法。其中，基于相似性的方法結(jié)構(gòu)較為簡單，同時(shí)普適性強(qiáng)且效率高。相似性方法是基于節(jié)點(diǎn)之間的接近程度（即2 個(gè)節(jié)點(diǎn)連接的概率大?。?］所定義，節(jié)點(diǎn)相似性可以通過分析節(jié)點(diǎn)屬性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息而得到。但是在實(shí)際應(yīng)用中，節(jié)點(diǎn)屬性信息往往很難獲得，并且信息的可利用率和可靠性都很低［2］。相比之下，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息非常容易獲得，并且一系列實(shí)證結(jié)果也表明其可靠性較高，因此，利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息獲取相似性被研究人員廣泛認(rèn)同［3］，對于一對節(jié)點(diǎn)x和y，可以利用網(wǎng)絡(luò)結(jié)構(gòu)信息計(jì)算它們的相似性分?jǐn)?shù)［4］。

目前，利用網(wǎng)絡(luò)結(jié)構(gòu)信息判斷節(jié)點(diǎn)相似性的方法可分為基于局部信息、基于全局信息、基于準(zhǔn)局部信息等方法。局部信息是指節(jié)點(diǎn)周圍有限的網(wǎng)絡(luò)結(jié)構(gòu)信息，如節(jié)點(diǎn)的度大小、節(jié)點(diǎn)的最近鄰居，因?yàn)樵擃惙椒ㄔ谟?jì)算相似度時(shí)只利用節(jié)點(diǎn)的局部拓?fù)湫畔⒍撬薪Y(jié)構(gòu)信息，所以計(jì)算復(fù)雜度低，適用于大型網(wǎng)絡(luò)，但與此同時(shí)，該類方法存在的缺陷是準(zhǔn)確度不夠。這類相似性方法的評估指標(biāo)主要有CN［5］、Salton［6］、Sorensen［7］、Jaccard［8］、AA［9］、RA［10］、PA［11］等。利用全局信息的方法考慮整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，使得鏈路預(yù)測更為靈活和準(zhǔn)確，但同時(shí)提高了時(shí)間復(fù)雜度，處理大型網(wǎng)絡(luò)時(shí)效率較低。這類相似性方法的評估指標(biāo)主要有Katz［12］、ACT［13］、RWR［14］、Cos+［15］等?；跍?zhǔn)局部信息的方法通過多跳路徑或局部隨機(jī)游走的方式，在局部信息的基礎(chǔ)上引入更多的拓?fù)湫畔?，相比于全局方法，其?jì)算復(fù)雜度較低，而相比于局部方法，其準(zhǔn)確度有所提升，該類方法綜合了局部方法和全局方法的優(yōu)勢。這類相似性方法的評估指標(biāo)有LP［16］、L3［17］等。

基于相似性的鏈路預(yù)測方法仍然不夠理想，特別是當(dāng)面對大型數(shù)據(jù)集時(shí)計(jì)算復(fù)雜度較高，而面對小型數(shù)據(jù)集時(shí)準(zhǔn)確度較低。局部方法受限于精準(zhǔn)度，而全局方法又受限于計(jì)算復(fù)雜度。因此，大量的準(zhǔn)局部方法被提出，它們結(jié)合局部方法和全局方法的優(yōu)勢來實(shí)現(xiàn)計(jì)算復(fù)雜度和精準(zhǔn)度的均衡。

RSP［18］指標(biāo)可以度量路徑與資源接收過程的交互關(guān)系，每個(gè)節(jié)點(diǎn)獲得一定的初始資源，然后路徑上的中間節(jié)點(diǎn)可以從它們的鄰居接收資源。大量實(shí)驗(yàn)結(jié)果表明，RSP 指標(biāo)性能表現(xiàn)良好。NCNLC［19］指標(biāo)通過結(jié)合節(jié)點(diǎn)全局歸一化共同鄰居屬性與局部聚類系數(shù)來達(dá)到平衡全局和局部信息的目的，并將周圍鄰居節(jié)點(diǎn)的連接強(qiáng)度納入指標(biāo)的考慮范圍。在時(shí)序仿真的預(yù)測過程中，NCNLC 表現(xiàn)出優(yōu)越的性能，整合了全局和局部指標(biāo)的優(yōu)勢。通過短路徑連接另一個(gè)端點(diǎn)的強(qiáng)關(guān)系可以帶來更強(qiáng)的影響力，而通過長路徑連接的強(qiáng)關(guān)系只能帶來較弱的影響力，基于這一思想，SI 被提出［20］，其通過區(qū)分強(qiáng)影響和弱影響來模擬實(shí)驗(yàn)的影響。PSI［21］的目標(biāo)是通過整合局部路徑上的節(jié)點(diǎn)信息來提高現(xiàn)有基于路徑方法的準(zhǔn)確性，它結(jié)合了Adamic Adar 和Katz 這2 種應(yīng)用最廣泛的相似度指標(biāo)的優(yōu)點(diǎn)，而且性能更優(yōu)。RA 方法利用共同鄰居節(jié)點(diǎn)進(jìn)行資源傳輸分析，但其忽略了共同鄰居節(jié)點(diǎn)周圍的拓?fù)浣Y(jié)構(gòu)。TT［22］方法在RA 的基礎(chǔ)上進(jìn)行改進(jìn)，利用資源傳輸節(jié)點(diǎn)的拓?fù)渚o密性，根據(jù)節(jié)點(diǎn)周圍拓?fù)浼鄢潭冗M(jìn)行量化，并根據(jù)傳輸節(jié)點(diǎn)緊密性對共同鄰居傳輸資源量的影響來刻畫節(jié)點(diǎn)間的相似性。實(shí)驗(yàn)結(jié)果表明，相比于基準(zhǔn)方法，TT 方法所得指標(biāo)的普適性更好，預(yù)測準(zhǔn)確度更高。受端點(diǎn)之間資源交換的啟發(fā)，ERA［23］在RA 的基礎(chǔ)上進(jìn)行改進(jìn)，增加更長的路徑并通過參數(shù)調(diào)整不同網(wǎng)絡(luò)長路徑轉(zhuǎn)移的資源量，節(jié)點(diǎn)之間通過區(qū)分共同鄰居和非共同鄰居交互的資源量來衡量相似度。

通過上述分析可以看出，準(zhǔn)局部指標(biāo)能夠結(jié)合局部指標(biāo)和全局指標(biāo)的優(yōu)勢，在計(jì)算復(fù)雜度較低的情況下達(dá)到較高的精準(zhǔn)度。受到網(wǎng)絡(luò)資源分配思想的啟發(fā)［24］，通過研究無標(biāo)度網(wǎng)絡(luò)中資源流量的動(dòng)態(tài)行為，設(shè)定網(wǎng)絡(luò)中的資源能夠自由流動(dòng)這一動(dòng)態(tài)機(jī)制，本文提出一種基于網(wǎng)絡(luò)資源流量的鏈路預(yù)測方法。為網(wǎng)絡(luò)設(shè)計(jì)一種資源流動(dòng)規(guī)則，賦予被預(yù)測節(jié)點(diǎn)對一定量的資源，使資源自由流動(dòng)，計(jì)算被預(yù)測節(jié)點(diǎn)對之間的雙向流量之和，從而得出相似性分?jǐn)?shù)，其中，流量之和越大，相似性分?jǐn)?shù)越高。該方法通過充分利用節(jié)點(diǎn)屬性信息、鄰域拓?fù)浣Y(jié)構(gòu)以及路徑因素，以提升鏈路預(yù)測的準(zhǔn)確度。

1 鏈路預(yù)測相關(guān)指標(biāo)

1.1 相似性指標(biāo)

相似性指標(biāo)用來衡量鏈路預(yù)測方法的準(zhǔn)確性，以及判斷鏈路存在的可能性。本文給出幾種常見的用于對比預(yù)測性能的基礎(chǔ)指標(biāo)，包括局部、準(zhǔn)局部以及全局指標(biāo)，分別為CN、Salton、Jaccard、AA、RA、LP、Katz，這7 個(gè)指標(biāo)將作為實(shí)驗(yàn)部分的對比參照指標(biāo)，具體信息如下：

1）CN 表示2 個(gè)節(jié)點(diǎn)之間共同鄰居節(jié)點(diǎn)的數(shù)目，計(jì)算公式如下：

其中：x和y分別代表網(wǎng)絡(luò)中2 個(gè)不同的節(jié)點(diǎn)；Γ（）表示節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)集合。

CN 等價(jià)于2 個(gè)節(jié)點(diǎn)間長度為2 的路徑數(shù)目：

2）Salton 又稱余弦相似性指標(biāo)，計(jì)算公式如下：

其中：k代表節(jié)點(diǎn)的度。

3）Jaccard 表示從節(jié)點(diǎn)對的任意一個(gè)節(jié)點(diǎn)的所有鄰居中選擇共同鄰居節(jié)點(diǎn)的概率，計(jì)算公式如下：

4）AA 對CN 指標(biāo)進(jìn)行改進(jìn)，旨在通過為連接較少的鄰居分配更多權(quán)重來提高共同鄰居的準(zhǔn)確性，其計(jì)算公式如下：

5）RA 由復(fù)雜網(wǎng)絡(luò)的資源配置過程所驅(qū)動(dòng)，考慮節(jié)點(diǎn)對的所有共同鄰居節(jié)點(diǎn)有且僅有一個(gè)單位資源，并將它平均分配給所有鄰居節(jié)點(diǎn)，從而進(jìn)行資源傳遞，其計(jì)算公式如下：

6）LP 又稱局部路徑指標(biāo)，在CN 的基礎(chǔ)上引入三階路徑指標(biāo)，并給予三階路徑一個(gè)懲罰因子，其計(jì)算公式如下：

7）Katz 指標(biāo)考慮節(jié)點(diǎn)對之間所有路徑的集合，路徑的長度以指數(shù)方式衰減，從而給較短路徑更多的權(quán)重。由于該指標(biāo)是基于整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，因此其計(jì)算成本通常比局部指標(biāo)高，而精確度往往也高于局部指標(biāo)。Katz 指標(biāo)的計(jì)算公式如下：

1.2 本文評價(jià)指標(biāo)

本文使用2 個(gè)公認(rèn)的鏈路預(yù)測常用指標(biāo)對預(yù)測精度進(jìn)行描述：

1）AUC，表示ROC 曲線下的面積［25］，是應(yīng)用最廣泛的鏈路預(yù)測性能評價(jià)指標(biāo)之一。AUC 表示隨機(jī)選擇的一個(gè)缺失連邊的相似性得分高于隨機(jī)選擇的一個(gè)不存在連邊的相似性得分的概率［26］。如果采用隨機(jī)選擇的方式，在多次獨(dú)立重復(fù)實(shí)驗(yàn)后，AUC的值應(yīng)當(dāng)是0.5。鏈路預(yù)測方法需要提高這個(gè)概率，即AUC 的值越大，說明該方法越精確。假設(shè)進(jìn)行n次取樣，則AUC 的計(jì)算公式如式（9）所示：

其中：n'代表測試集中邊分?jǐn)?shù)值大于不存在邊的分?jǐn)?shù)值的次數(shù)；n″表示兩者分?jǐn)?shù)值相等的次數(shù)。

2）Precision，表示前L條邊中有m條邊預(yù)測準(zhǔn)確的比例，即排在前L條的邊中有m條屬于測試集。與AUC 不同，Precision 只關(guān)心前L條邊是否預(yù)測準(zhǔn)確［27］，Precision 在某些特定情形下（如只關(guān)注排在前L條邊的預(yù)測準(zhǔn)確與否）比AUC 更有意義。Precision計(jì)算公式如下：

2 網(wǎng)絡(luò)資源流量方法

2.1 網(wǎng)絡(luò)資源流量評估方法

受到網(wǎng)絡(luò)資源分配的啟發(fā)，本文將節(jié)點(diǎn)對之間路徑上的中間節(jié)點(diǎn)作為資源傳輸?shù)拿浇椋ㄟ^計(jì)算節(jié)點(diǎn)對之間網(wǎng)絡(luò)資源流量的總和，提出一種RF（Resource Flow）方法以計(jì)算節(jié)點(diǎn)對的相似性。首先，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有一定單位的初始資源，且這個(gè)資源可以根據(jù)節(jié)點(diǎn)的度大小進(jìn)行傳輸，進(jìn)而將2 個(gè)節(jié)點(diǎn)之間的相似度計(jì)算轉(zhuǎn)變?yōu)? 個(gè)節(jié)點(diǎn)之間所有階路徑資源流量的計(jì)算，如果2 個(gè)節(jié)點(diǎn)之間資源流量越多，說明它們的聯(lián)系越緊密，則相似性越高。

如圖1 所示，假設(shè)該無向圖中存在15 個(gè)節(jié)點(diǎn)和15 條邊，節(jié)點(diǎn)1 和節(jié)點(diǎn)5 沒有直接相連，而是通過一條2 階路徑和一條3 階路徑相連，這2 條路徑經(jīng)過的中間節(jié)點(diǎn)被標(biāo)記為黑色。路徑資源流量方法的思想是：給予網(wǎng)絡(luò)中被預(yù)測的節(jié)點(diǎn)對（節(jié)點(diǎn)1 和節(jié)點(diǎn)5）一定單位的初始資源R，該資源會(huì)按照均分的原則傳輸?shù)焦?jié)點(diǎn)對的所有鄰居節(jié)點(diǎn)中，鄰居節(jié)點(diǎn)在接收資源后會(huì)繼續(xù)平均傳給其所有的鄰居節(jié)點(diǎn)。此時(shí)，初始資源R就會(huì)在網(wǎng)絡(luò)中進(jìn)行流動(dòng)，可以通過計(jì)算節(jié)點(diǎn)1 流向節(jié)點(diǎn)5 的初始資源流量和節(jié)點(diǎn)5 流向節(jié)點(diǎn)1的初始資源流量之和，得到節(jié)點(diǎn)對（節(jié)點(diǎn)1 和節(jié)點(diǎn)5）的相似性分?jǐn)?shù)。資源流量越多，說明這2 個(gè)節(jié)點(diǎn)越相似。

圖1 資源流動(dòng)過程Fig.1 Resource flow process

2.2 網(wǎng)絡(luò)資源流量量化

本文對網(wǎng)絡(luò)資源流量量化作出如下定義：

定義1假設(shè)存在無向網(wǎng)絡(luò)G（V，E），網(wǎng)絡(luò)中共有n個(gè)節(jié)點(diǎn)，i表示節(jié)點(diǎn)序號。在初始情況下，賦予每個(gè)節(jié)點(diǎn)vi∈V的資源表示為：

定義2網(wǎng)絡(luò)分為動(dòng)態(tài)和靜態(tài)2 種狀態(tài)，在動(dòng)態(tài)時(shí)，網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)向自己的鄰居節(jié)點(diǎn)傳輸資源，而在靜態(tài)時(shí)不會(huì)傳輸。2 種狀態(tài)的集合表示為：

定義3在動(dòng)態(tài)網(wǎng)絡(luò)中，節(jié)點(diǎn)會(huì)向每個(gè)鄰居節(jié)點(diǎn)傳輸資源，傳輸?shù)馁Y源量統(tǒng)一按照均分的原則分配給每一個(gè)鄰居節(jié)點(diǎn)，即節(jié)點(diǎn)向每個(gè)鄰居節(jié)點(diǎn)傳輸?shù)攘康馁Y源。同時(shí)，節(jié)點(diǎn)也會(huì)接收來自鄰居節(jié)點(diǎn)傳輸?shù)馁Y源，接收量取決于鄰居節(jié)點(diǎn)的傳輸量。節(jié)點(diǎn)向其鄰居發(fā)送的資源和從鄰居處接收的資源分別如下：

其中：k是節(jié)點(diǎn)的度；z∈Γ(i)表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)；Ri→z∈Γ(i)表示vi向其鄰居發(fā)送的資源；Ri←z∈Γ(i)表示節(jié)點(diǎn)vi從其鄰居處接收的資源。

定義4為了表示路徑中節(jié)點(diǎn)對于資源量的傳輸作用，提出一個(gè)新的概念，即路徑節(jié)點(diǎn)n。給定一對節(jié)點(diǎn)（x，y），l為它們之間路徑的最大長度。假設(shè)在節(jié)點(diǎn)x到節(jié)點(diǎn)y之間的長度為1～l的路徑上存在一些中間節(jié)點(diǎn)，將這些節(jié)點(diǎn)定義為中間路徑節(jié)點(diǎn)。x和y之間的中間路徑節(jié)點(diǎn)可以用集合表示為：

在節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的某條路徑中，依次經(jīng)過m個(gè)節(jié)點(diǎn)，第1 個(gè)節(jié)點(diǎn)為1 階路徑節(jié)點(diǎn)，第2 個(gè)節(jié)點(diǎn)為2 階路徑節(jié)點(diǎn)，第m個(gè)節(jié)點(diǎn)為m階路徑節(jié)點(diǎn)。m取值為0～（l-1）范圍內(nèi)的正整數(shù)，當(dāng)m=0 時(shí)，代表2 個(gè)節(jié)點(diǎn)之間沒有任何一條路徑將它們相連。路徑節(jié)點(diǎn)的數(shù)目為路徑數(shù)目減1，即l-1。由vi到vj和由vj到vi，路徑節(jié)點(diǎn)索引值相加為m+1，即：

定義5在一個(gè)動(dòng)態(tài)網(wǎng)絡(luò)中，給定一對節(jié)點(diǎn)(x,y)，節(jié)點(diǎn)之間的路徑長度為l，它們之間流動(dòng)的資源總量可以通過2 個(gè)步驟進(jìn)行計(jì)算：首先，節(jié)點(diǎn)x和節(jié)點(diǎn)y分別將初始資源發(fā)送給鄰居；然后，在x和y之間路徑上的資源流將由中間路徑節(jié)點(diǎn)分別發(fā)送到其鄰居節(jié)點(diǎn)。每個(gè)中間路徑節(jié)點(diǎn)將從鄰居處接收資源，并將資源平均交付給下一個(gè)中間路徑節(jié)點(diǎn)，因此，在交付之前資源量是1/(k-1)。根據(jù)RF 指標(biāo)的定義，隨著路徑數(shù)的增加，資源流量經(jīng)過的路徑節(jié)點(diǎn)增多，初始資源會(huì)被不斷稀釋，稱其為路徑稀釋作用。資源流量計(jì)算過程如圖2 所示。

圖2 資源流量計(jì)算過程Fig.2 Resource traffic calculation process

假設(shè)節(jié)點(diǎn)x和節(jié)點(diǎn)y向相鄰節(jié)點(diǎn)傳輸R個(gè)單位的資源，節(jié)點(diǎn)間路經(jīng)上的總資源流量計(jì)算分為兩步：

1）第一步，計(jì)算節(jié)點(diǎn)x和節(jié)點(diǎn)y發(fā)送給鄰居的初始資源，即：

2）第二步，計(jì)算路徑長度為l-1 的中間路徑節(jié)點(diǎn)的貢獻(xiàn)值，即：

定義6給定一對節(jié)點(diǎn)(x,y)，l是它們之間路徑的最大長度。表示從節(jié)點(diǎn)x到節(jié)點(diǎn)y的長度 為m+1 的所有路徑個(gè)數(shù)。x、y之間所有中間路徑節(jié)點(diǎn)的貢獻(xiàn)即為x和y之間雙向流動(dòng)的資源之和，表示如下：

不同節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性不同，為了突顯這個(gè)特征，需要給每個(gè)節(jié)點(diǎn)分配不同的初始資源。一般地，節(jié)點(diǎn)的重要性用“中心性”來衡量。本文利用2 階局部指標(biāo)（即該節(jié)點(diǎn)與其他節(jié)點(diǎn)存在共同鄰居節(jié)點(diǎn)的比例）來進(jìn)行初始資源分配。如果網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)與其他n-1 個(gè)節(jié)點(diǎn)之間存在的共同鄰居數(shù)目越多，則認(rèn)為該節(jié)點(diǎn)越重要，給它分配更多的資源，用節(jié)點(diǎn)鄰居數(shù)與其余節(jié)點(diǎn)總數(shù)的比值來表示，即：

其中：Ri代表第i個(gè)節(jié)點(diǎn)的初始資源。

2.3 鏈路預(yù)測求解

本文算法的輸入變量是無向網(wǎng)絡(luò)，需要計(jì)算節(jié)點(diǎn)對（x，y）的相似性和中間路徑節(jié)點(diǎn)的階數(shù)l。輸入無向網(wǎng)絡(luò)G之后，首先將其轉(zhuǎn)換為鄰接矩陣的形式，以得到所有節(jié)點(diǎn)和連邊的信息，然后計(jì)算所有節(jié)點(diǎn)的初始資源和它們的度，得到2 個(gè)n維向量，數(shù)值對應(yīng)于每一個(gè)節(jié)點(diǎn)的資源和度。對于給定的節(jié)點(diǎn)對（x，y），使用深度優(yōu)先遍歷方法找出網(wǎng)絡(luò)中的所有路徑，假設(shè)網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn)，花費(fèi)的時(shí)間復(fù)雜度為O（n2）。這些路徑中的節(jié)點(diǎn)除了起點(diǎn)和終點(diǎn)之外都是中間節(jié)點(diǎn)。假設(shè)考慮1 階到l-1 階的所有中間節(jié)點(diǎn)的作用，并且遍歷出的所有路徑數(shù)為k，那么該過程的時(shí)間復(fù)雜度就為O（k（l-1）），因此，RF 算法總的時(shí)間復(fù)雜度為O（n2+k（l-1）），l的最大值為n-2，即x經(jīng)過除x、y節(jié)點(diǎn)之外的所有節(jié)點(diǎn)到達(dá)y，時(shí)間復(fù)雜度最高為O（n2+kn-3k）。RF 算法描述如下：

算法1RF 算法

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

為了評估本文所提鏈路預(yù)測算法RF 的性能，將其與目前最常用的7 種鏈路預(yù)測基準(zhǔn)方法進(jìn)行實(shí)驗(yàn)對比與分析。

3.1 數(shù)據(jù)集

實(shí)驗(yàn)使用來自真實(shí)世界的11 個(gè)不同的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集，這些數(shù)據(jù)集來源于多種不同的網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通信息網(wǎng)絡(luò)以及引文網(wǎng)絡(luò)等。11 個(gè)網(wǎng)絡(luò)數(shù)據(jù)集的具體信息如下：

1）NS［28］：科學(xué)引文合作網(wǎng)絡(luò)，代表論文之間的引用合作關(guān)系。

2）PB［29］：美國政客之間的博客交互網(wǎng)絡(luò)。

3）Yeast［30］：大型蛋白質(zhì)相互作用網(wǎng)絡(luò)，包含2375個(gè)節(jié)點(diǎn)和11 693 個(gè)鏈接。

4）Jazz［31］：爵士樂音樂家之間的合作網(wǎng)絡(luò)，代表音樂作品之間的合作關(guān)系。

5）Metabolic［32］：秀麗隱桿線蟲新陳代謝網(wǎng)絡(luò)。

6）BUP［33］：某政客博客網(wǎng)絡(luò)。

7）UAL［34］：飛機(jī)交通系統(tǒng)網(wǎng)絡(luò)。

8）INF［35］：展覽中觀眾面對面接觸的網(wǎng)絡(luò)。

9）SMG［36］：不同研究領(lǐng)域作者的論文合作網(wǎng)絡(luò)。

10）Celegans［37］：秀麗隱桿線蟲的神經(jīng)網(wǎng)絡(luò)。

11）EML［38］：羅維拉大學(xué)成員之間的電子郵件交互網(wǎng)絡(luò)。

11 個(gè)網(wǎng)絡(luò)的基本拓?fù)湫畔⒕唧w如表1 所示。

表1 11 個(gè)真實(shí)世界網(wǎng)絡(luò)的基本拓?fù)湫畔able 1 Basic topology information of eleven real-world networks

3.2 不同參數(shù)情況下的RF 預(yù)測精確度

考慮到RF 的時(shí)間復(fù)雜度過高會(huì)大幅提高對比實(shí)驗(yàn)的難度，此外，針對路徑信息的方法，利用2 階路徑和3 階路徑的信息最為準(zhǔn)確，從4 階之后準(zhǔn)確度開始下降［39］。因此，本文只考慮1 階、2 階、3 階的中間路徑節(jié)點(diǎn)，通過設(shè)置l值為4 來降低時(shí)間復(fù)雜度，最終時(shí)間復(fù)雜度為O（n2+3k），從而在計(jì)算復(fù)雜度不高的同時(shí)最大化地提升準(zhǔn)確度。首先，只利用RF 算法計(jì)算11 個(gè)網(wǎng)絡(luò)中的AUC 和Precision，橫向?qū)Ρ萊F 在利用不同階數(shù)的路徑節(jié)點(diǎn)時(shí)的性能表現(xiàn)。本節(jié)與下一節(jié)的實(shí)驗(yàn)中統(tǒng)一設(shè)置訓(xùn)練集與測試集的比例為9∶1。

表2 不同參數(shù)情況下RF 在11 個(gè)網(wǎng)絡(luò)中的AUC 表現(xiàn)Table 2 AUC performance of RF in eleven networks under different parameters

表3 不同參數(shù)情況下RF 在11 個(gè)網(wǎng)絡(luò)中的Precision 表現(xiàn)Table 3 Precision performance of RF in eleven networks under different parameters

從圖3、圖4 可以得出如下結(jié)論：

圖3 不同參數(shù)情況下RF 在11 個(gè)網(wǎng)絡(luò)中的AUC 對比Fig.3 AUC comparison of RF in eleven networks under different parameters

圖4 不同參數(shù)情況下RF 在11 個(gè)網(wǎng)絡(luò)中的Precision 對比Fig.4 Precision comparison of RF in eleven networks under different parameters

1）對比RF 利用單階路徑節(jié)點(diǎn)時(shí)的精準(zhǔn)度情況。RF-1 在4 個(gè)數(shù)據(jù)集中AUC 表現(xiàn)最佳，在3 個(gè)數(shù)據(jù)集中Precision 表現(xiàn)最佳；RF-2 在5個(gè)數(shù)據(jù)集中AUC 表現(xiàn)最佳，AUC 表現(xiàn)情況良好，在7 個(gè)數(shù)據(jù)集中Precision 表現(xiàn)最佳；RF-3 在2個(gè)數(shù)據(jù)集中AUC 表 現(xiàn)最佳，AUC 表現(xiàn)情況較差，Precision 只在1 個(gè)數(shù)據(jù)集中超過了RF-1、RF-2。因此，如果RF 算法只利用3 階路徑節(jié)點(diǎn)，則其AUC 和Precision 的精準(zhǔn)度將遠(yuǎn)低于RF-1、RF-2。RF-2的表現(xiàn)良好，超過了RF-1，這意味著資源在3 階路徑中的傳輸精度高于2 階路徑，這打破了以往指標(biāo)對于共同鄰居的精度普遍高于3 階路徑這一共識，這一點(diǎn)在文獻(xiàn)［17，40-41］中進(jìn)行了證實(shí)，本文也進(jìn)一步驗(yàn)證了這個(gè)情況。

2）對比RF 利用多階路徑節(jié)點(diǎn)時(shí)的精準(zhǔn)度情況。RF-1+2 在6 個(gè)數(shù)據(jù)集中AUC 表現(xiàn)最佳，但Precision只在3 個(gè)數(shù)據(jù)集中表現(xiàn)最佳；RF-2+3 在5 個(gè)數(shù)據(jù)集中AUC 表現(xiàn)最佳，在7 個(gè)數(shù)據(jù)集中Precision 表現(xiàn)最佳；RF-1+3 的AUC 表現(xiàn)最差，未在任何數(shù)據(jù)集中超過RF-1+2 和RF-2+3，其Precision 也只在1 個(gè)數(shù)據(jù)集中超過了RF-1+2、RF-2+3；RF-1+2+3 在11 個(gè)數(shù)據(jù)集中AUC 和Precision 的表現(xiàn)超過了其他所有的6 種情況，RF-1+2+3 僅利用了4 個(gè)階數(shù)的路徑節(jié)點(diǎn)，其利用網(wǎng)絡(luò)拓?fù)湫畔⒌某潭茸罡撸m然計(jì)算復(fù)雜度會(huì)提升，但能保證結(jié)果較優(yōu)。

基于以上分析，本文得到RF 的最優(yōu)指標(biāo)設(shè)置為RF-opt=RF-1+2+3，在后續(xù)實(shí)驗(yàn)中，會(huì)以RF-opt 的數(shù)據(jù)與其他基準(zhǔn)指標(biāo)進(jìn)行對比。

3.3 預(yù)測精度對比分析

為了驗(yàn)證RF 指標(biāo)的預(yù)測精度，本文將其與上文提到的7 個(gè)基準(zhǔn)指標(biāo)在11 個(gè)網(wǎng)絡(luò)中進(jìn)行對比，包括5 個(gè)局部指標(biāo)（CN、Salton、Jaccard、AA、RA）、1 個(gè)準(zhǔn)局部指標(biāo)（LP）以及1 個(gè)全局指標(biāo)（Katz）。表4 展示各指標(biāo)在11 個(gè)網(wǎng)絡(luò)中的AUC 值對比情況，最優(yōu)結(jié)果加粗表示。從表4 可以看出，RF 指標(biāo)在7 個(gè)數(shù)據(jù)集中表現(xiàn)最優(yōu)，雖然RF 只利用了準(zhǔn)局部信息，但是其表現(xiàn)并不遜于全局指標(biāo)Katz，Katz 只在2 個(gè)數(shù)據(jù)集中表現(xiàn)最優(yōu)。在基于局部信息的相似性指標(biāo)中，CN、Salton、Jaccard 和AA 指標(biāo)在不同網(wǎng)絡(luò)中表現(xiàn)相近，不如準(zhǔn)局部和全局指標(biāo)。RA 指標(biāo)由于利用了網(wǎng)絡(luò)資源的機(jī)制，相比于其他4 種局部指標(biāo)表現(xiàn)更優(yōu)，在Metabolic 數(shù)據(jù)集中達(dá)到了最優(yōu)效果。RF 指標(biāo)除了在個(gè)別數(shù)據(jù)集中表現(xiàn)不如RA、LP 和Katz，在其他數(shù)據(jù)集中表現(xiàn)均為最優(yōu)，相比于全局指標(biāo)，RF 作為準(zhǔn)局部指標(biāo)，其在預(yù)測精度上更有優(yōu)勢。

表4 100 次獨(dú)立實(shí)驗(yàn)下的平均AUC 值對比Table 4 Comparison of average AUC values under 100 independent experiments

表5 所示為各指標(biāo)在11 個(gè)網(wǎng)絡(luò)中的Precision值對比。從表5 可以看出，RF 指標(biāo)在8 個(gè)數(shù)據(jù)集中表現(xiàn)最優(yōu)，在Yeast 和SMG 數(shù)據(jù)集中其表現(xiàn)遠(yuǎn)超其他指標(biāo)。準(zhǔn)局部指標(biāo)LP 和全局指標(biāo)Katz 表現(xiàn)良好，普遍優(yōu)于局部指標(biāo)，分別在EML 和UAL 數(shù)據(jù)集中達(dá)到最優(yōu)，這在AUC 和Precision 中都表現(xiàn)出了同樣的結(jié)果，說明準(zhǔn)局部指標(biāo)和全局指標(biāo)挖掘了更多的網(wǎng)絡(luò)信息，因此，它們的精準(zhǔn)度高于局部指標(biāo)。

表5 100 次獨(dú)立實(shí)驗(yàn)下的平均Precision 值對比Table 5 Comparison of average Precision values under 100 independent experiments

綜上所述，相比于其他7 種基準(zhǔn)指標(biāo)，RF 指標(biāo)能夠達(dá)到更優(yōu)的預(yù)測精準(zhǔn)度，原因主要有以下3 點(diǎn)：

1）相比于局部指標(biāo)CN、Salton、Jaccard、AA 和RA，RF 指標(biāo)對于共同鄰居節(jié)點(diǎn)的利用程度更高。

2）相比于準(zhǔn)局部指標(biāo)LP，RF 利用了更多的網(wǎng)絡(luò)信息，考慮到了路徑節(jié)點(diǎn)本身的度大小對于鏈路預(yù)測貢獻(xiàn)不同的情況。

3）全局指標(biāo)Katz 很少利用高階路徑信息，并且予以非常大的懲罰因數(shù)，導(dǎo)致添加了很多數(shù)值較小的噪聲，提高了計(jì)算復(fù)雜度。RF 只從1 階、2 階、3 階路徑節(jié)點(diǎn)出發(fā)，避免了噪聲信息，同時(shí)降低了計(jì)算復(fù)雜度，因此，其精確度表現(xiàn)更優(yōu)。

3.4 RF 算法魯棒性測試

為了更準(zhǔn)確地驗(yàn)證RF 的性能，將訓(xùn)練集劃分比例從0.5 調(diào)整到0.9，步長設(shè)為0.1，對8 個(gè)算法在11 個(gè)網(wǎng)絡(luò)中的表現(xiàn)進(jìn)行可視化，從而測試所有指標(biāo)的魯棒性，實(shí)驗(yàn)結(jié)果如圖5、圖6 所示。從圖5 可以看出，當(dāng)訓(xùn)練集比例從0.5 上升到0.9 時(shí)，AUC 值呈現(xiàn)上升趨勢，當(dāng)訓(xùn)練集比例增加時(shí)，隨著網(wǎng)絡(luò)已知信息的增加，所有方法的AUC 值隨之上升。在訓(xùn)練集比例的變化過程中，局部指標(biāo)的斜率變化往往大于準(zhǔn)局部和全局指標(biāo)，魯棒性最差。在所有指標(biāo)中，Katz在NS、PB、Yeast 數(shù)據(jù)集中AUC 基本沒有波動(dòng)，魯棒性較好。RF 指標(biāo)僅次于Katz 指標(biāo)，在多個(gè)數(shù)據(jù)集中波動(dòng)不大，并且都優(yōu)于其他指標(biāo)。從圖6 可以看出，所有方法的Precision 值總體呈現(xiàn)下降趨勢，說明隨著訓(xùn)練集比例的升高，測試集比例減小，所有節(jié)點(diǎn)預(yù)測準(zhǔn)確的概率降低。與AUC 結(jié)果不同，RF 的Precision 魯棒性在所有指標(biāo)中表現(xiàn)最好，在總體波動(dòng)不大的情況下還能保持較高的數(shù)值。在EML 數(shù)據(jù)集中，RF 的Precision 波動(dòng)較大，不過波動(dòng)情況仍然低于其他指標(biāo)，而在INF 中，LP 和Katz 出現(xiàn)較大的波動(dòng)，RF 能夠保持穩(wěn)定，此外，RF 在Celegans 中不僅波動(dòng)最小，而且始終優(yōu)于其他指標(biāo)。

圖5 不同訓(xùn)練集比例下的AUC 魯棒性測試結(jié)果Fig.5 AUC robustness test results under different proportion of training sets

圖6 不同訓(xùn)練集比例下的Precision 魯棒性測試結(jié)果Fig.6 Precision robustness test results under different proportion of training sets

4 結(jié)束語

鏈路預(yù)測方法受到拓?fù)浣Y(jié)構(gòu)復(fù)雜特征和系統(tǒng)動(dòng)力學(xué)要素的制約，使得局部方法效率較低，全局方法則面臨維數(shù)災(zāi)難問題。網(wǎng)絡(luò)資源分配機(jī)制雖然能夠在一定程度上實(shí)現(xiàn)資源的合理分配，但是忽略了傳輸路徑節(jié)點(diǎn)的有效性和傳輸方向問題。此外，在當(dāng)今的復(fù)雜網(wǎng)絡(luò)研究中，數(shù)據(jù)集規(guī)模越來越大，對鏈路預(yù)測方法的效率和精度提出了更高的要求。為了解決上述問題，本文從準(zhǔn)局部指標(biāo)和資源流動(dòng)角度出發(fā)，提出一種基于網(wǎng)絡(luò)流量的鏈路預(yù)測方法。定義網(wǎng)絡(luò)中初始資源的生成和資源流動(dòng)機(jī)制，計(jì)算雙向資源流量以精確刻畫節(jié)點(diǎn)對之間的相似性，在此基礎(chǔ)上提出相似性指標(biāo)和鏈路預(yù)測算法RF。實(shí)驗(yàn)結(jié)果表明，將雙向資源流量作為相似性的匹配度，可以使得預(yù)測精度顯著提升，從而證實(shí)了資源傳輸機(jī)制的有效性。雖然本文的網(wǎng)絡(luò)流量研究在上述方面具有一定的改進(jìn)意義，但仍然存在局限性。由于算法復(fù)雜度的限制，網(wǎng)絡(luò)更高階的拓?fù)湫畔o法得到利用，且在初始資源分配的過程中，本文算法仍然采用較為樸素的公共近鄰思想進(jìn)行分配。下一步將優(yōu)化算法流程以利用更高階節(jié)點(diǎn)信息進(jìn)行鏈路預(yù)測，同時(shí)，利用神經(jīng)網(wǎng)絡(luò)或網(wǎng)絡(luò)嵌入技術(shù)對初始資源分配權(quán)重，以及將本文算法應(yīng)用于加權(quán)網(wǎng)絡(luò)、有向網(wǎng)絡(luò)和大型網(wǎng)絡(luò)中，也是今后的研究方向。