基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法

李巧麗 韓華 李秋暉 曾茜

摘要：為解決現(xiàn)有的基于相似性的鏈路預測方法忽略了最優(yōu)路徑在節(jié)點間傳遞相似性的能力的問題，提出一種基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法。首先，分析節(jié)點間最優(yōu)路徑對信息傳輸能力的影響，進而對節(jié)點間緊密中心性進行定義；其次，依據(jù)最優(yōu)路徑數(shù)和中心性構建相似度傳輸矩陣，綜合節(jié)點間局部信息和全局屬性衡量節(jié)點間相似度。最后，將所提方法與其他相似性指標，在6個真實網(wǎng)絡上進行實證對比研究。結果表明，所提算法預測精度較高，且算法更加穩(wěn)定。

關鍵詞：復雜網(wǎng)絡；鏈路預測；最優(yōu)路徑；相似度傳輸矩陣；相似性度量；中心性

中圖分類號： TP393; N94文獻標識碼： A

收稿日期：2021-10-23；修回日期：2021-12-07

基金項目：國家自然科學基金青年科學基金（111701435）；國家自然科學基金（12071364）

第一作者：李巧麗（1991-），女，河南平輿人，碩士，主要研究方向為復雜網(wǎng)絡動力學、鏈路預測。

通信作者：韓華（1975-），女，山東煙臺人，博士，教授，主要研究方向為復雜性分析與評價、經(jīng)濟控制與決策。

Link Prediction Method Based on Optimal Path Similarity Transfer Matrix

LI Qiaoli， HAN Hua， LI Qiuhui， ZENG Xi

（Department of Science， Wuhan University of Technology， Wuhan 430070， China）

Abstract：The current similarity-based link prediction methods ignore the ability of the optimal path to transfer similarity between nodes. To solve this problem， a link prediction method based on the optimal path similarity transmission matrix is proposed. Firstly， the influence of the optimal path between nodes on the information transmission capacity is analyzed， then the tight centrality between nodes is defined; secondly， the number of optimal paths and centrality is used to construct the similarity transmission matrix， and the local information between nodes and global attributes are integrated to evaluate the similarity between nodes. Finally， the proposed method is compared with other similarity-based algorithms in six real networks. The results show that the proposed algorithm has more accurate prediction accuracy and is more stable.

Key words： complex networks; link prediction; optimal path; similarity transfer matrix; similarity measurement; centrality

0 引言

隨著網(wǎng)絡科學理論研究成果不斷涌現(xiàn)，復雜網(wǎng)絡已經(jīng)成為分析和挖掘復雜系統(tǒng)的強有力工具。而鏈路預測作為復雜網(wǎng)絡的重要研究方向，旨在借助網(wǎng)絡中已知的數(shù)據(jù)信息挖掘網(wǎng)絡中未知的連邊關系^[1-2]。鏈路預測的研究在眾多領域發(fā)揮著重要價值，從理論上來說，可以幫助我們更好地理解網(wǎng)絡演化機制及網(wǎng)絡動力學行為^[3]；從應用上來說，當前社交網(wǎng)絡上的用戶拓展、電信網(wǎng)絡上的詐騙源頭識別、電商網(wǎng)絡上的客戶精準營銷等^[4-5]都是鏈路預測在現(xiàn)實網(wǎng)絡中的典型應用。

目前，許多經(jīng)典的鏈路預測算法被提出，其中基于相似性的鏈路預測算法應用領域最為廣泛。通常包括基于節(jié)點鄰居的方法（如共同鄰居指標（Common Neighbors，CN）^[6]、Adamic-Adar（AA）指標^[7]、RA指標（Resource Allocation））^[3]）和基于路徑的方法（如局部路徑（LP）指標^[3]、Katz指標^[8]）兩大類。此外，近年來學者們認為用單一的節(jié)點鄰居信息來描述節(jié)點間的相似性是片面的，嘗試從多個角度來刻畫節(jié)點間的相似性，將節(jié)點的重要性和高階路徑信息應用到鏈路預測中。例如，Wu等^[9]發(fā)現(xiàn)共鄰節(jié)點的影響力越大，對節(jié)點間相似性的貢獻越小，因此，利用共鄰節(jié)點的重要性排序得分對節(jié)點間的相似度進行加權，提出一種基于重要節(jié)點識別的廣義鏈路預測方法。但該方法只利用了二階路徑信息，沒有進一步挖掘更高階的路徑信息。Kumar等^[10]將傳統(tǒng)的聚類系數(shù)概念擴展到高階路徑上^[11]，進一步提取了網(wǎng)絡的拓撲結構信息，并利用擴展的聚類系數(shù)概念進行鏈路預測。文獻[12]從資源傳輸?shù)慕嵌瘸霭l(fā)，試圖通過懲罰共同鄰居來限制信息通過共鄰節(jié)點產(chǎn)生的“泄露”，并利用高階路徑作為判別特征，提出了基于高階路徑相似度的鏈路預測指標。

近幾年，一些學者從節(jié)點間最短路徑出發(fā)提出了一些新的預測鏈路的方法。例如，Yang等^[13]針對待預測端點對之間不存在共同鄰居這一問題，結合節(jié)點間的二階路徑數(shù)和最短路徑度量節(jié)點間的相似性，實驗結果表明，該方法在預測無共同鄰居的節(jié)點對的缺失鏈接方面取得了很好的效果。Ahmad等^[14]考慮到節(jié)點的共同鄰居和中心性兩個重要屬性特征，在共同鄰居的基礎上，定義了節(jié)點間的緊密中心性，并將共同鄰居和中心性進行線性耦合，提出了CCPA指標，有效地解決了CN指標計算結果為0或相似度分數(shù)區(qū)分不大導致的預測精度有限的問題。另外，在節(jié)點重要性研究方面，文獻[15]從信息傳輸?shù)慕嵌瘸霭l(fā)，分析節(jié)點和三階內(nèi)鄰居節(jié)點的相互作用，通過節(jié)點和關聯(lián)節(jié)點間的最短路徑長度和最短路徑數(shù)度量節(jié)點間的相互影響，提出一種新的節(jié)點重要性識別方法，理論依據(jù)是最短路徑數(shù)和最短路徑長度在節(jié)點間影響力傳輸?shù)倪^程中發(fā)揮著重要作用。

節(jié)點間最優(yōu)路徑（無權網(wǎng)絡最優(yōu)路徑等價于最短路徑）是網(wǎng)絡中信息傳輸最直接、最有效的路徑。信息總是優(yōu)先選擇最優(yōu)路徑傳輸，以最大化減少信息沿著路徑傳輸過程中發(fā)生的“耗散”，使兩端節(jié)點接收到更多信息量，從而兩端節(jié)點更相似。實際上，節(jié)點間相似性影響與最優(yōu)路徑數(shù)和最優(yōu)路徑長度密切關聯(lián)，因此，本文從信息傳輸?shù)慕嵌瘸霭l(fā)，利用最優(yōu)路徑作為判別特征，從節(jié)點間最優(yōu)路徑長度對信息傳輸能力的影響和節(jié)點中心性兩個角度，定義節(jié)點間緊密中心性函數(shù)，再依據(jù)最優(yōu)路徑數(shù)和中心性構建相似度傳輸矩陣，綜合節(jié)點對間的局部信息和全局屬性刻畫節(jié)點對之間的相似度，提出一種基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法。該算法考慮了六階（六度分割理論）范圍內(nèi)的最優(yōu)路徑信息，相比于CCPA算法，利用了更高階的路徑信息，簡稱為HOP-LP算法。

1 相關研究

1.1 問題描述

給定一個無向網(wǎng)絡，用一個二元序對G=（V，E）表示，包含V=N個節(jié)點和E=M條邊。對于網(wǎng)絡中所有的節(jié)點，所有可能產(chǎn)生連邊的兩點集合Ω=V×V。網(wǎng)絡G的鄰接矩陣用A=（a_ij）_N×N（u，v∈V）表示，假設A中的元素a_uv=1，代表節(jié)點對（u，v）之間有連邊。給定一種鏈路預測算法，為網(wǎng)絡中每一對不存在的連邊賦予一個分數(shù)S_xy。一般的鏈路預測框架是根據(jù)節(jié)點間的相似度賦予分數(shù)值，因此，將所有S_xy降序排列，排在最前面的邊存在的可能性更大。

1.2 基準算法

1）共同鄰居（CN）：通過節(jié)點對之間的共鄰節(jié)點的個數(shù)刻畫節(jié)點u和v的相似性，即

其中，Γ（u）為節(jié)點u的鄰居集合，｜｜表示集合的勢。

2）AA指標：是一種基于共享特征的相似性度量方法，對度大的共鄰節(jié)點進行懲罰，則節(jié)點u和v的相似度定義為

其中，k_ω為節(jié)點ω的度值。

3）局部路徑（LP）：為局部和全局指標在預測精度和時間復雜度之間的折衷方法，是一種半局部鏈路預測方法，即

其中，ε為調(diào)節(jié)參數(shù)，該指標可以擴展為

其中，n為最大階數(shù)。隨著n的增加，該指標計算復雜度會增加。

4）Katz指標：該指標實際上是一種最短路徑方法，考慮了兩個節(jié)點間所有的路徑數(shù)，并根據(jù)路徑長度的不同采取分級懲罰，則該指標表示為

其中，β為路徑權重調(diào)節(jié)參數(shù)，|path^〈l〉_u，v|為節(jié)點間路徑長度為l的路徑數(shù)。

5）共同鄰居和距離（CND）：該算法基于網(wǎng)絡的兩個重要結構特征（共同鄰居和距離），對未連邊的兩個節(jié)點u和v的相似性用式（6）表示：

其中，CN_uv為節(jié)點u和v的共同鄰居數(shù)，d_uv為節(jié)點間距離。

6）CCPA指標：Ahmad等^[14]基于節(jié)點的共同鄰居和中心性兩個重要屬性特征，定義了兩個節(jié)點間的緊密中心性，并將共同鄰居和緊密中心性進行線性耦合，則該指標定義為

其中，α為調(diào)節(jié)權重參數(shù)，d_uv為節(jié)點間最短路徑。

7）平均通勤時間（ACT）^[16]：基于隨機游走定義的相似性指標，表示一個粒子從節(jié)點u游走到節(jié)點v所需走的平均步數(shù)，即

其中，l⁺_uv為網(wǎng)絡的拉普拉斯矩陣中第u行第v列對應的元素值。

8）COS+指標^[17]：即余弦相似性指標，基于隨機游走，在矩陣L⁺上計算兩個向量間的相似度，具體表示為

其中，l⁺_uv=υ^T_uυ_y。

2 基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法

復雜網(wǎng)絡的節(jié)點間通過路徑發(fā)生相互作用，路徑是信息在網(wǎng)絡中得以順利流動的通道。文獻^[18]表明最優(yōu)路徑長度與最優(yōu)路徑數(shù)在節(jié)點間信息傳輸?shù)倪^程中發(fā)揮著重要作用。根據(jù)空間自相關理論^[19]，個體間的傳輸能力與距離成反比，最優(yōu)路徑越長，傳輸能力越弱。同時還與節(jié)點間的最優(yōu)路徑數(shù)有關，最優(yōu)路徑數(shù)越多，傳輸能力越強。假設節(jié)點x和z之間的最優(yōu)路徑長度l_xz和節(jié)點y和z之間的最優(yōu)路徑長度l_yz相等，但節(jié)點x到z之間的長度為l_xz的路徑數(shù)遠多于節(jié)點y到z之間的長度為l_yz的路徑數(shù)，則節(jié)點x到z間的傳輸能力更強。

如圖1所示，首先，節(jié)點8到節(jié)點2的最優(yōu)路徑長度（節(jié)點間距離）為2，最優(yōu)路徑數(shù)（二階路徑數(shù)）為1；節(jié)點4到節(jié)點2的最優(yōu)路徑長度為2，最優(yōu)路徑數(shù)為3，相比于前者，后者的最優(yōu)路徑數(shù)更多，故節(jié)點間傳輸能力更強。另一方面，節(jié)點8到節(jié)點7和節(jié)點4到7的最優(yōu)路徑長度都為3，但從圖1中可以看出，后者的三階最優(yōu)路徑數(shù)明顯多于前者，因此，后者節(jié)點之間信息傳輸能力較強，兩端節(jié)點接收到的信息量更多，從而相互連接的可能性更大。基于以上分析，下文首先基于最優(yōu)路徑特征定義節(jié)點間的緊密中心性，其次，給出最優(yōu)路徑數(shù)的代數(shù)算法，最后，將最優(yōu)路徑數(shù)和中心性進行線性耦合構建相似度傳輸矩陣，進而給出節(jié)點間相似性的度量指標。

2.1 節(jié)點間緊密中心性的量化

節(jié)點中心性即節(jié)點在網(wǎng)絡中的相對重要性，其表征有度中心性、介數(shù)中心性和接近中心性^[18]。其中，接近中心性是指任意節(jié)點對間的平均最短路徑。基于此，我們從節(jié)點間最優(yōu)路徑長度對信息傳輸能力的影響和節(jié)點中心性兩個角度，給出節(jié)點對間的緊密中心性函數(shù)，表示為

其中，l_uv為節(jié)點u和v之間的最優(yōu)路徑長度。

2.2 最優(yōu)路徑數(shù)的代數(shù)算法

圖1為一個無向圖，它的鄰接矩陣為對稱矩陣。假設a_uv為A中的元素，則在圖1中表示節(jié)點u到節(jié)點v之間有連邊，又由于圖1中不存在自環(huán)和重邊，所以A中的元素只能為0或1。那么a_uv可以理解為：由u點到v點經(jīng)過一條邊，有a_uv種走法。同理，將其推廣到A²。記B=A²，則B中的元素b_uv表示節(jié)點u出發(fā)到達節(jié)點v走兩條邊有b_uv種走法。

通過上述過程，記Q=A^m，Q中的元素q_uv代表的就是從u到v走m條邊的路徑數(shù)，但這里有重復路徑，從圖1可以看出，節(jié)點1到2的最優(yōu)路徑長度為1，但計算1到2之間的三階路徑時把長度為1的路徑重復計算在內(nèi)（1到2來回走三次），實際圖1中并不存在1到2的長度為3的路徑。為了消除重復路徑，這里假設節(jié)點u和v不同，令m=l_uv，l_uv為節(jié)點u和v之間的最優(yōu)路徑長度，則q_uv為節(jié)點間最優(yōu)路徑數(shù)。

2.3 節(jié)點間相似度傳輸矩陣構建

針對最優(yōu)路徑促進節(jié)點間信息傳輸有效性的情況，本文基于最優(yōu)路徑對傳輸過程的影響因素分析節(jié)點間的信息傳輸能力?！傲确指罾碚摗闭J為世界上任何兩個不相識的人之間的距離不超過6個人^[20]。因此，本文在計算最優(yōu)路徑數(shù)時考慮六階范圍內(nèi)的相似度影響，構建節(jié)點間的相似度傳輸能力矩陣，記為F_C：

其中，π_uv為傳輸能力分配參數(shù)，當節(jié)點u與v間的最優(yōu)路徑為六階范圍內(nèi)時π_uv=1，否則為0；對角線上的1表示節(jié)點到自身的傳輸能力為1。F_C（u，v）代表節(jié)點u到節(jié)點v的傳輸能力?？梢钥闯?，節(jié)點之間的最優(yōu)路徑數(shù)越多，最優(yōu)路徑越短，則節(jié)點對間的信息傳輸能力越強，兩端節(jié)點接收到的信息量越多，從而兩端節(jié)點越相似。因此，可以由節(jié)點對間傳輸能力定義節(jié)點間的相似性。

定義1 基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法（HOP-LP）：根據(jù)節(jié)點間最優(yōu)路徑對信息傳輸能力的影響量化節(jié)點間緊密中心性，結合節(jié)點間緊密中心性和最優(yōu)路徑數(shù)來度量節(jié)點間的相似性。HOP-LP的指標為

其中，式（13）中的前一項表示節(jié)點間的最優(yōu)路徑數(shù)（最高階數(shù)為6），α為調(diào)節(jié)參數(shù)，用于調(diào)節(jié)最優(yōu)路徑數(shù)和中心性的權重，取值范圍為0，1。

2.4 算法流程

首先通過設定α的取值范圍，將范圍內(nèi)不同的α值代入算法，通過循環(huán)計算，觀察不同α值對預測結果的影響，找出最佳參數(shù)α_opt，最佳參數(shù)α_opt即為算法衡量指標達到最優(yōu)值時對應的參數(shù)取值（具體情況參見4.1節(jié)和4.2節(jié)）。其次，將α_opt代入HOP-LP算法中，輸出節(jié)點間的相似度分數(shù)。在最佳的α_opt下，HOP-LP算法的詳細步驟為：

輸入：網(wǎng)絡鄰接矩陣A=（a_uv）_N×N（u，v∈V），最佳參數(shù)α_opt

輸出：網(wǎng)絡節(jié)點相似性得分矩陣

1）初始化最短距離矩陣Dis←O_N×N，節(jié)點相似性得分矩陣S←I_N×N；

2）利用A計算節(jié)點對（u，v）之間的最短路徑矩陣Dis=[l_uv] //Dijkstra算法；

6）生成相應的節(jié)點相似性得分矩陣。

本文基于以下假設對算法的復雜度進行分析，即大多數(shù)網(wǎng)絡都為稀疏的（平均度〈k〉較?。?sup>[21]，計算最優(yōu)路徑數(shù)時考慮的最優(yōu)路徑的最大長度設為l_max=6，超過最高階路徑則認為最優(yōu)路徑數(shù)對刻畫節(jié)點對間相似性不產(chǎn)生影響。HOP-LP算法的關鍵是計算網(wǎng)絡中所有節(jié)點對間的最短路徑矩陣Dis=[l_uv]，最短路徑可以使用Dijkstra算法進行有效計算。Dijkstra算法可以采用網(wǎng)絡的鄰接列表和優(yōu)先隊列進行優(yōu)化，優(yōu)化后的時間復雜度為Ο（MlogN）。由于要為每對節(jié)點計算最短路徑，故Dijkstra算法的總時間復雜度約為Ο（MNlogN）。而計算最優(yōu)路徑數(shù)的時間復雜度約為Ο（N/〈k〉⁶），因此，HOP-LP算法的總時間復雜度約為Ο（MNlogN）。

3 實驗條件介紹

3.1 算法衡量標準

為了測試指標的預測性能，將目標網(wǎng)絡中的連邊集合E劃分為訓練集E^T和測試集E^P，E=E^T∪E^P，且E^T∩E^P=。其中，訓練集被認為試驗時已知的網(wǎng)絡信息，測試集被認為是試驗時要預測的網(wǎng)絡信息，用于測試算法的準確度。

AUC（Area Under the Curve）指標可以理解為分別從測試集E^P和不存在的邊集U-E中隨機選取一條邊，測試集中邊的分數(shù)比不存在的邊的分數(shù)更高的概率^[22]。實驗時，計測試集中邊的分數(shù)值高于不存在的邊分數(shù)的情況為n′，兩者分數(shù)相同的情況為n″，AUC指標可以表示為

其中，n為獨立比較的次數(shù)，顯然，隨機預測下AUC≈0.5。

AUC更側重于從整理上衡量算法的準確度，在不同的復雜網(wǎng)絡鏈路預測問題中，還會有其他的要求。例如，在社交網(wǎng)絡推薦系統(tǒng)中，要求算法能精準地推薦“people may you know”就能滿足需求。因此，Precision衡量指標（后文簡略為Pre）也應列入指標性能評價中，其關注的是前L個預測邊中預測準確的比例^[23]，表示為

其中，l為預測分數(shù)值排在前L個的連邊中出現(xiàn)在測試集E^P中的個數(shù)。在本文中，對小于1 000個節(jié)點的網(wǎng)絡選取L=20，對大于1 000個節(jié)點的網(wǎng)絡選取L=100。

3.2 網(wǎng)絡數(shù)據(jù)

本文選取了6個不同的真實網(wǎng)絡數(shù)據(jù)集：Dolphins^[24]，Polbook^[13]，Circuit^[25]，USAir^[26]，Netscience^[27]，Hamster^[28]。1）Dolphins網(wǎng)絡：生活在新西蘭神奇灣的海豚關系網(wǎng)絡；2）Polbook網(wǎng)絡：關于美國政治書籍的電商網(wǎng)絡，節(jié)點表示Amazon.com線上銷售的書籍，邊代表同一買家頻繁共同購買的書籍；3）Circuit網(wǎng)絡：一個電子電路系統(tǒng)網(wǎng)絡，其中節(jié)點是電子元件（如電容器、二極管等），連邊是電線；4）USAir網(wǎng)絡：關于美國航空運輸系統(tǒng)的網(wǎng)絡；5）Netscience網(wǎng)絡：在網(wǎng)絡科學領域發(fā)表過論文的科學家之間的合作關系網(wǎng)絡；6）Hamster網(wǎng)絡：有關hamsterster.com網(wǎng)頁用戶之間的朋友關系網(wǎng)絡。上述網(wǎng)絡數(shù)據(jù)集的拓撲特征參數(shù)如表2所列。其中，N與M分別代表節(jié)點數(shù)與邊數(shù)，〈k〉為節(jié)點平均度，〈d〉為網(wǎng)絡平均路徑，C為網(wǎng)絡集聚系數(shù)。文中選取各個網(wǎng)絡數(shù)據(jù)集的20%作為測試集，其余的80%作為訓練集。

4 實驗結果及分析

為了評估本文所提算法的性能，采用AUC和Pre兩個衡量指標對其進行測試和分析。實驗中，每個AUC和Pre結果均為500次獨立實驗結果的均值。

4.1 AUC結果及分析

對于6個真實網(wǎng)絡，首先分析了不同網(wǎng)絡中參數(shù)α對預測結果的影響。圖2展示了不同網(wǎng)絡的AUC值隨參數(shù)α的變化情況。從圖2中可以觀察到，不同網(wǎng)絡中HOP-LP算法的性能受參數(shù)影響較大，從圖2中的每個子圖可以觀察到，AUC曲線到達峰值后會呈現(xiàn)下降趨勢，這說明最優(yōu)路徑數(shù)對相似性刻畫的影響是不可或缺的。實驗還發(fā)現(xiàn)，每個網(wǎng)絡取得最佳預測精度對應的參數(shù)值并不同，α的最大值出現(xiàn)在Netscience網(wǎng)絡中，為0.6，結合網(wǎng)絡所具有的拓撲結構特征可以看出，Netscience網(wǎng)絡的集聚系數(shù)在6個網(wǎng)絡中最大，平均路徑長度較大，這說明節(jié)點間最優(yōu)路徑所在階數(shù)較低，相比于節(jié)點間最優(yōu)路徑長度，最優(yōu)路徑數(shù)對節(jié)點間相似性的影響更大；而Hamster網(wǎng)絡的集聚系數(shù)在6個網(wǎng)絡中最小，最優(yōu)預測精度對應的參數(shù)α在6個網(wǎng)絡中取值最小，這是由于網(wǎng)絡的最優(yōu)路徑所在階數(shù)較高，節(jié)點間的高階最優(yōu)路徑數(shù)對相似度的影響較?。辉贑ircuit網(wǎng)絡中，AUC結果在達到最佳值后隨著參數(shù)的增大有所下降，隨后在最優(yōu)路徑數(shù)和最優(yōu)路徑長度達到平衡時又呈現(xiàn)上升趨勢，說明參數(shù)對AUC的影響較為復雜。實際網(wǎng)絡應用中，可適當調(diào)節(jié)α值，提高鏈路預測的準確性。

表2給出了不同網(wǎng)絡中HOP-LP算法與其他算法的AUC值。從表2可以看出，HOP-LP算法在不同網(wǎng)絡上的表現(xiàn)都是最佳的。相比于只考慮二階路徑數(shù)的CCPA算法，考慮了高階最優(yōu)路徑數(shù)的HOP-LP算法在Hamster網(wǎng)絡中預測準確率提高了約6%，這驗證了考慮高階最優(yōu)路徑數(shù)的HOP-LP算法能更好地利用網(wǎng)絡結構。圖3給出了9種鏈路預測方法在6個真實網(wǎng)絡中的AUC值的堆積柱形圖。從圖3可以直觀地看出HOP-LP算法每種顏色的面積幾乎均勻，說明該算法能夠較穩(wěn)定地預測各個網(wǎng)絡。而CN，AA，LP，Katz和ACT 5種指標每種顏色面積差別很大，表明這些指標的穩(wěn)定性相對較差?？v向來看，HOP-LP算法的AUC累計值最大，其次是Katz指標，進一步驗證了所提算法的有效性。

4.2 Pre結果及分析

為了進一步評估所提算法的性能，采用Pre指標對所提算法進行仿真分析。圖4展示了調(diào)節(jié)參數(shù)α對Pre結果的影響，從圖4可以看出，大多數(shù)網(wǎng)絡在α較小時就能取得很好的預測性能。不同于AUC，隨著參數(shù)α的增大，大部分網(wǎng)絡的Pre值會顯著下降，因此，在實際網(wǎng)絡預測中，參數(shù)α可以在較小范圍內(nèi)調(diào)節(jié)，提高鏈路預測的準確度。

表3給出了不同算法在不同網(wǎng)絡的Pre值?？梢钥闯觯琀OP-LP算法在不同網(wǎng)絡上的表現(xiàn)都是最佳的。相比于CCPA算法，尤其在Polbook網(wǎng)絡中，預測精度提高了約32%。圖5給出了9種鏈路預測方法在6個真實網(wǎng)絡中的Pre值堆積柱形圖。其中，USAir網(wǎng)絡整體預測效果較好，Circuit網(wǎng)絡的預測效果普遍較低，相比于其他算法，HOP-LP算法的Pre累計值總量第一，算法的預測結果較穩(wěn)定。

5 結語

準確預測復雜網(wǎng)絡中節(jié)點對間的相似性對于加快積極信息在網(wǎng)絡中傳播、預防電信詐騙、促進電商網(wǎng)絡的發(fā)展具有現(xiàn)實意義。本文通過分析最優(yōu)路徑在促進節(jié)點間信息傳輸過程發(fā)揮的重要作用，提出一種基于最優(yōu)路徑相似度傳輸矩陣的鏈路預測方法。該算法分析了最優(yōu)路徑長度和六階范圍內(nèi)最優(yōu)路徑數(shù)對節(jié)點相似性的貢獻，定義了節(jié)點間緊密中心性函數(shù)，結合節(jié)點間局部和全局屬性信息，取得了全面的相似性度量結果。在6個真實網(wǎng)絡數(shù)據(jù)集上進行實證分析，結果驗證了所提方法的可行性和穩(wěn)定性。下一步將研究加權網(wǎng)絡的特征，挖掘加權網(wǎng)絡中的潛在連邊。

參考文獻：

[1]GUL H， AMIN A， ADNAN A， et al. A systematic analysis of link prediction in complex network[J]. IEEE Access， 2021， 9： 20531-20541.

[2]BRUGERE I， GALLAGHER B， BERGER-WOLF T Y. Network structure inference， a survey： motivations， methods， and applications[J]. ACM Computing Surveys， 2018， 51（2）： 1-39.

[3]ZHOU T， L? L Y， ZHANG Y C. Predicting missing links via local information[J]. European Physical Journal B， 2009， 71（4）： 623-630.

[4]CANNISTRACI C V， ALANIS-LOBATO G， RAVASI T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Scientific Reports， 2013， 3（4）： 1613-1613.

[5]ASSOULI N， BENAHMED K， GASBAOUI B. How to predict crime informatics-inspired approach from link prediction[J]. Physica A： Statistical Mechanics and Its Applications， 2021（8）： 125-143.

[6]LORRAIN F， WHITE H C. Structural equivalence of individuals in social networks[J]. The Journal of Mathematical Sociology， 1971， 1（1）： 49-80.

[7]ADAMIC L A， ADAR E. Friends and neighbors on the Web[J]. Social Networks， 2003， 25（3）： 211-230.

[8]KATZ L. A new status index derived from sociometric index[J]. Psychometrika， 1953， 18（1）： 39-43.

[9]WU J H， SHEN J， ZHOU B， et al. General link prediction with influential node identification[J]. Physica A： Statistical Mechanics and Its Applications， 2019， 523（ 6）： 996-1007.

[10] KUMAR A， SINGH S S， SINGH K， et al. Level-2 node clustering coefficient-based link prediction[J]. Applied Intelligence， 2019， 49（7）： 2762-2779.

[11] YIN H， BENSON A R， LESKOVEC J. Higher-order clustering in networks[J]. Physical Review E， 2018， 97（5）： 052306.

[12] 顧秋陽， 吳寶， 池仁勇. 基于高階路徑相似度的復雜網(wǎng)絡鏈路預測方法[J]. 通信學報， 2021， 42（7）： 61-69.

GU Q Y， WU B， CHI R Y. Link prediction method based on the similarity of high path[J]. Journal on Communications， 2021， 42（7）： 61-69.

[13] YANG J， ZHANG X D. Predicting missing links in complex networks based on common neighbors and distance[J]. Scientific Reports， 2016， 6（1）： 1-10.

[14] AHMAD I， AKHTAR M U， NOOR S， et al. Missing link prediction using common neighbor and centrality based paramete-rized algorithm[J]. Scientific Reports， 2020， 10（1）： 1-9.

[15] 胡鋼， 高浩， 徐翔， 等. 基于重要度傳輸矩陣的復雜網(wǎng)絡節(jié)點重要性辨識方法[J]. 電子學報， 2020， 48（12）： 2402-2408.

HU G， GAO H， XU X， et al. Importance identification method of complex network nodes based on importance transfer matrix[J]. Acta Electronica Sinica， 2020， 48（12）： 2402-2408.

[16] KLEIN D J， RANDIC M. Resistance distance[J]. Journal of Mathematical Chemistry， 1993， 12（1）： 81-95.

[17] FOUSS F， PIROTTE A， RENDERS J M， et al. Random- walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（3）： 355-369.

[18] BAO Z K， MA C， XIANG B B， et al. Identification of influential nodes in complex networks： method from spreading probability viewpoint[J]. Physica A： Statistical Mechanics and Its Applications， 2017， 468： 391-397.

[19] GRIFFITH D A， CHUN Y. Spatial autocorrelation in spatial interactions models： geographic scale and resolution implications for network resilience and vulnerability[J]. Networks and Spatial Economics， 2015， 15（2）： 337-365.

[20] 周麗娜， 李發(fā)旭， 鞏云超， 等. 基于K-shell的超網(wǎng)絡關鍵節(jié)點識別方法[J].復雜系統(tǒng)與復雜性科學， 2021， 18（3）： 15-22.

ZHOU L N， LI F X， GONG Y C， et al. Identification methods of vital nodes based on K-shell in hypernetworks[J]. Complex Systems and Complexity Science， 2021， 18（3）： 15-22.

[21] 郭世澤， 陸哲明. 復雜網(wǎng)絡基礎理論[M].北京：科學出版社，2012.

[22] KUMAR A， MISHRA S， SINGH S S， et al. Link prediction in complex networks based on significance of higher-order path index （SHOPI）[J]. Physica A： Statistical Mechanics and Its Applications， 2020， 545： 123790.

[23] ZHOU T， Lee Y L， Wang G. Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms[J]. Physica A： Statistical Mechanics and Its Applications， 2021， 564： 125532.

[24] LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology， 2003， 54（4）： 396-405.

[25] MILO， R. ITZKOVITZ S， KASHTAN N， et al. Superfamilies of evolved and designednetworks[J]. Science， 2004， 303（5663）： 1538-1542.

[26] ZENG A， LIU W. Enhancing network robustness against malicious attacks[J]. Physical Review E， 2012， 85（6）： 066130.

[27] GUIMERA R， DANON L， DIAZ-GUILERA A， et al. Self-similar community structure in a network of human interactions[J]. Physical Review E， 2003， 68（6）： 065103.

[28] ADAMIC L A， GLANCE N. The political blogosphere and the 2004 U.S. election： divided they blog[C]// Proceedings of the 3rd International Workshop on Link Discovery， Chicago. USA， 2005： 36-43.

（責任編輯 耿金花）