基于網絡資源流量的鏈路預測方法

劉宇航，尹小慶，林 云

（1.重慶大學 機械與運載工程學院，重慶 400044；2.重慶大學 管理科學與房地產學院，重慶 400044）

0 概述

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

目前，利用網絡結構信息判斷節點相似性的方法可分為基于局部信息、基于全局信息、基于準局部信息等方法。局部信息是指節點周圍有限的網絡結構信息，如節點的度大小、節點的最近鄰居，因為該類方法在計算相似度時只利用節點的局部拓撲信息而非所有結構信息，所以計算復雜度低，適用于大型網絡，但與此同時，該類方法存在的缺陷是準確度不夠。這類相似性方法的評估指標主要有CN［5］、Salton［6］、Sorensen［7］、Jaccard［8］、AA［9］、RA［10］、PA［11］等。利用全局信息的方法考慮整個網絡的拓撲結構信息，使得鏈路預測更為靈活和準確，但同時提高了時間復雜度，處理大型網絡時效率較低。這類相似性方法的評估指標主要有Katz［12］、ACT［13］、RWR［14］、Cos+［15］等。基于準局部信息的方法通過多跳路徑或局部隨機游走的方式，在局部信息的基礎上引入更多的拓撲信息，相比于全局方法，其計算復雜度較低，而相比于局部方法，其準確度有所提升，該類方法綜合了局部方法和全局方法的優勢。這類相似性方法的評估指標有LP［16］、L3［17］等。

基于相似性的鏈路預測方法仍然不夠理想，特別是當面對大型數據集時計算復雜度較高，而面對小型數據集時準確度較低。局部方法受限于精準度，而全局方法又受限于計算復雜度。因此，大量的準局部方法被提出，它們結合局部方法和全局方法的優勢來實現計算復雜度和精準度的均衡。

RSP［18］指標可以度量路徑與資源接收過程的交互關系，每個節點獲得一定的初始資源，然后路徑上的中間節點可以從它們的鄰居接收資源。大量實驗結果表明，RSP 指標性能表現良好。NCNLC［19］指標通過結合節點全局歸一化共同鄰居屬性與局部聚類系數來達到平衡全局和局部信息的目的，并將周圍鄰居節點的連接強度納入指標的考慮范圍。在時序仿真的預測過程中，NCNLC 表現出優越的性能，整合了全局和局部指標的優勢。通過短路徑連接另一個端點的強關系可以帶來更強的影響力，而通過長路徑連接的強關系只能帶來較弱的影響力，基于這一思想，SI 被提出［20］，其通過區分強影響和弱影響來模擬實驗的影響。PSI［21］的目標是通過整合局部路徑上的節點信息來提高現有基于路徑方法的準確性，它結合了Adamic Adar 和Katz 這2 種應用最廣泛的相似度指標的優點，而且性能更優。RA 方法利用共同鄰居節點進行資源傳輸分析，但其忽略了共同鄰居節點周圍的拓撲結構。TT［22］方法在RA 的基礎上進行改進，利用資源傳輸節點的拓撲緊密性，根據節點周圍拓撲集聚程度進行量化，并根據傳輸節點緊密性對共同鄰居傳輸資源量的影響來刻畫節點間的相似性。實驗結果表明，相比于基準方法，TT 方法所得指標的普適性更好，預測準確度更高。受端點之間資源交換的啟發，ERA［23］在RA 的基礎上進行改進，增加更長的路徑并通過參數調整不同網絡長路徑轉移的資源量，節點之間通過區分共同鄰居和非共同鄰居交互的資源量來衡量相似度。

通過上述分析可以看出，準局部指標能夠結合局部指標和全局指標的優勢，在計算復雜度較低的情況下達到較高的精準度。受到網絡資源分配思想的啟發［24］，通過研究無標度網絡中資源流量的動態行為，設定網絡中的資源能夠自由流動這一動態機制，本文提出一種基于網絡資源流量的鏈路預測方法。為網絡設計一種資源流動規則，賦予被預測節點對一定量的資源，使資源自由流動，計算被預測節點對之間的雙向流量之和，從而得出相似性分數，其中，流量之和越大，相似性分數越高。該方法通過充分利用節點屬性信息、鄰域拓撲結構以及路徑因素，以提升鏈路預測的準確度。

1 鏈路預測相關指標

1.1 相似性指標

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

1）CN 表示2 個節點之間共同鄰居節點的數目，計算公式如下：

其中：x和y分別代表網絡中2 個不同的節點；Γ（）表示節點的所有鄰居節點集合。

CN 等價于2 個節點間長度為2 的路徑數目：

2）Salton 又稱余弦相似性指標，計算公式如下：

其中：k代表節點的度。

3）Jaccard 表示從節點對的任意一個節點的所有鄰居中選擇共同鄰居節點的概率，計算公式如下：

4）AA 對CN 指標進行改進，旨在通過為連接較少的鄰居分配更多權重來提高共同鄰居的準確性，其計算公式如下：

5）RA 由復雜網絡的資源配置過程所驅動，考慮節點對的所有共同鄰居節點有且僅有一個單位資源，并將它平均分配給所有鄰居節點，從而進行資源傳遞，其計算公式如下：

6）LP 又稱局部路徑指標，在CN 的基礎上引入三階路徑指標，并給予三階路徑一個懲罰因子，其計算公式如下：

7）Katz 指標考慮節點對之間所有路徑的集合，路徑的長度以指數方式衰減，從而給較短路徑更多的權重。由于該指標是基于整個網絡的拓撲結構，因此其計算成本通常比局部指標高，而精確度往往也高于局部指標。Katz 指標的計算公式如下：

1.2 本文評價指標

本文使用2 個公認的鏈路預測常用指標對預測精度進行描述：

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

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

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

2 網絡資源流量方法

2.1 網絡資源流量評估方法

受到網絡資源分配的啟發，本文將節點對之間路徑上的中間節點作為資源傳輸的媒介，通過計算節點對之間網絡資源流量的總和，提出一種RF（Resource Flow）方法以計算節點對的相似性。首先，網絡中的每個節點都有一定單位的初始資源，且這個資源可以根據節點的度大小進行傳輸，進而將2 個節點之間的相似度計算轉變為2 個節點之間所有階路徑資源流量的計算，如果2 個節點之間資源流量越多，說明它們的聯系越緊密，則相似性越高。

如圖1 所示，假設該無向圖中存在15 個節點和15 條邊，節點1 和節點5 沒有直接相連，而是通過一條2 階路徑和一條3 階路徑相連，這2 條路徑經過的中間節點被標記為黑色。路徑資源流量方法的思想是：給予網絡中被預測的節點對（節點1 和節點5）一定單位的初始資源R，該資源會按照均分的原則傳輸到節點對的所有鄰居節點中，鄰居節點在接收資源后會繼續平均傳給其所有的鄰居節點。此時，初始資源R就會在網絡中進行流動，可以通過計算節點1 流向節點5 的初始資源流量和節點5 流向節點1的初始資源流量之和，得到節點對（節點1 和節點5）的相似性分數。資源流量越多，說明這2 個節點越相似。

圖1 資源流動過程Fig.1 Resource flow process

2.2 網絡資源流量量化

本文對網絡資源流量量化作出如下定義：

定義1假設存在無向網絡G（V，E），網絡中共有n個節點，i表示節點序號。在初始情況下，賦予每個節點vi∈V的資源表示為：

定義2網絡分為動態和靜態2 種狀態，在動態時，網絡中的節點會向自己的鄰居節點傳輸資源，而在靜態時不會傳輸。2 種狀態的集合表示為：

定義3在動態網絡中，節點會向每個鄰居節點傳輸資源，傳輸的資源量統一按照均分的原則分配給每一個鄰居節點，即節點向每個鄰居節點傳輸等量的資源。同時，節點也會接收來自鄰居節點傳輸的資源，接收量取決于鄰居節點的傳輸量。節點向其鄰居發送的資源和從鄰居處接收的資源分別如下：

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

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

在節點vi到節點vj的某條路徑中，依次經過m個節點，第1 個節點為1 階路徑節點，第2 個節點為2 階路徑節點，第m個節點為m階路徑節點。m取值為0～（l-1）范圍內的正整數，當m=0 時，代表2 個節點之間沒有任何一條路徑將它們相連。路徑節點的數目為路徑數目減1，即l-1。由vi到vj和由vj到vi，路徑節點索引值相加為m+1，即：

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

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

假設節點x和節點y向相鄰節點傳輸R個單位的資源，節點間路經上的總資源流量計算分為兩步：

1）第一步，計算節點x和節點y發送給鄰居的初始資源，即：

2）第二步，計算路徑長度為l-1 的中間路徑節點的貢獻值，即：

定義6給定一對節點(x,y)，l是它們之間路徑的最大長度。表示從節點x到節點y的長度 為m+1 的所有路徑個數。x、y之間所有中間路徑節點的貢獻即為x和y之間雙向流動的資源之和，表示如下：

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

其中：Ri代表第i個節點的初始資源。

2.3 鏈路預測求解

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

算法1RF 算法

3 實驗結果與分析

為了評估本文所提鏈路預測算法RF 的性能，將其與目前最常用的7 種鏈路預測基準方法進行實驗對比與分析。

3.1 數據集

實驗使用來自真實世界的11 個不同的復雜網絡數據集，這些數據集來源于多種不同的網絡，如社交網絡、生物網絡、交通信息網絡以及引文網絡等。11 個網絡數據集的具體信息如下：

1）NS［28］：科學引文合作網絡，代表論文之間的引用合作關系。

2）PB［29］：美國政客之間的博客交互網絡。

3）Yeast［30］：大型蛋白質相互作用網絡，包含2375個節點和11 693 個鏈接。

4）Jazz［31］：爵士樂音樂家之間的合作網絡，代表音樂作品之間的合作關系。

5）Metabolic［32］：秀麗隱桿線蟲新陳代謝網絡。

6）BUP［33］：某政客博客網絡。

7）UAL［34］：飛機交通系統網絡。

8）INF［35］：展覽中觀眾面對面接觸的網絡。

9）SMG［36］：不同研究領域作者的論文合作網絡。

10）Celegans［37］：秀麗隱桿線蟲的神經網絡。

11）EML［38］：羅維拉大學成員之間的電子郵件交互網絡。

11 個網絡的基本拓撲信息具體如表1 所示。

表1 11 個真實世界網絡的基本拓撲信息Table 1 Basic topology information of eleven real-world networks

3.2 不同參數情況下的RF 預測精確度

考慮到RF 的時間復雜度過高會大幅提高對比實驗的難度，此外，針對路徑信息的方法，利用2 階路徑和3 階路徑的信息最為準確，從4 階之后準確度開始下降［39］。因此，本文只考慮1 階、2 階、3 階的中間路徑節點，通過設置l值為4 來降低時間復雜度，最終時間復雜度為O（n2+3k），從而在計算復雜度不高的同時最大化地提升準確度。首先，只利用RF 算法計算11 個網絡中的AUC 和Precision，橫向對比RF 在利用不同階數的路徑節點時的性能表現。本節與下一節的實驗中統一設置訓練集與測試集的比例為9∶1。

表2 不同參數情況下RF 在11 個網絡中的AUC 表現Table 2 AUC performance of RF in eleven networks under different parameters

表3 不同參數情況下RF 在11 個網絡中的Precision 表現Table 3 Precision performance of RF in eleven networks under different parameters

從圖3、圖4 可以得出如下結論：

圖3 不同參數情況下RF 在11 個網絡中的AUC 對比Fig.3 AUC comparison of RF in eleven networks under different parameters

圖4 不同參數情況下RF 在11 個網絡中的Precision 對比Fig.4 Precision comparison of RF in eleven networks under different parameters

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

2）對比RF 利用多階路徑節點時的精準度情況。RF-1+2 在6 個數據集中AUC 表現最佳，但Precision只在3 個數據集中表現最佳；RF-2+3 在5 個數據集中AUC 表現最佳，在7 個數據集中Precision 表現最佳；RF-1+3 的AUC 表現最差，未在任何數據集中超過RF-1+2 和RF-2+3，其Precision 也只在1 個數據集中超過了RF-1+2、RF-2+3；RF-1+2+3 在11 個數據集中AUC 和Precision 的表現超過了其他所有的6 種情況，RF-1+2+3 僅利用了4 個階數的路徑節點，其利用網絡拓撲信息的程度最高，雖然計算復雜度會提升，但能保證結果較優。

基于以上分析，本文得到RF 的最優指標設置為RF-opt=RF-1+2+3，在后續實驗中，會以RF-opt 的數據與其他基準指標進行對比。

3.3 預測精度對比分析

為了驗證RF 指標的預測精度，本文將其與上文提到的7 個基準指標在11 個網絡中進行對比，包括5 個局部指標（CN、Salton、Jaccard、AA、RA）、1 個準局部指標（LP）以及1 個全局指標（Katz）。表4 展示各指標在11 個網絡中的AUC 值對比情況，最優結果加粗表示。從表4 可以看出，RF 指標在7 個數據集中表現最優，雖然RF 只利用了準局部信息，但是其表現并不遜于全局指標Katz，Katz 只在2 個數據集中表現最優。在基于局部信息的相似性指標中，CN、Salton、Jaccard 和AA 指標在不同網絡中表現相近，不如準局部和全局指標。RA 指標由于利用了網絡資源的機制，相比于其他4 種局部指標表現更優，在Metabolic 數據集中達到了最優效果。RF 指標除了在個別數據集中表現不如RA、LP 和Katz，在其他數據集中表現均為最優，相比于全局指標，RF 作為準局部指標，其在預測精度上更有優勢。

表4 100 次獨立實驗下的平均AUC 值對比Table 4 Comparison of average AUC values under 100 independent experiments

表5 所示為各指標在11 個網絡中的Precision值對比。從表5 可以看出，RF 指標在8 個數據集中表現最優，在Yeast 和SMG 數據集中其表現遠超其他指標。準局部指標LP 和全局指標Katz 表現良好，普遍優于局部指標，分別在EML 和UAL 數據集中達到最優，這在AUC 和Precision 中都表現出了同樣的結果，說明準局部指標和全局指標挖掘了更多的網絡信息，因此，它們的精準度高于局部指標。

表5 100 次獨立實驗下的平均Precision 值對比Table 5 Comparison of average Precision values under 100 independent experiments

綜上所述，相比于其他7 種基準指標，RF 指標能夠達到更優的預測精準度，原因主要有以下3 點：

1）相比于局部指標CN、Salton、Jaccard、AA 和RA，RF 指標對于共同鄰居節點的利用程度更高。

2）相比于準局部指標LP，RF 利用了更多的網絡信息，考慮到了路徑節點本身的度大小對于鏈路預測貢獻不同的情況。

3）全局指標Katz 很少利用高階路徑信息，并且予以非常大的懲罰因數，導致添加了很多數值較小的噪聲，提高了計算復雜度。RF 只從1 階、2 階、3 階路徑節點出發，避免了噪聲信息，同時降低了計算復雜度，因此，其精確度表現更優。

3.4 RF 算法魯棒性測試

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

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

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

4 結束語

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