李巧麗 韓華 李秋暉 曾茜

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

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

中圖分類號： TP393; N94文獻(xiàn)標(biāo)識碼： A

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

基金項(xiàng)目：國家自然科學(xué)基金青年科學(xué)基金（111701435）；國家自然科學(xué)基金（12071364）

第一作者：李巧麗（1991-），女，河南平輿人，碩士，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)動力學(xué)、鏈路預(yù)測。

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

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

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

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

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

1 相關(guān)研究

1.1 問題描述

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

1.2 基準(zhǔn)算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

節(jié)點(diǎn)中心性即節(jié)點(diǎn)在網(wǎng)絡(luò)中的相對重要性，其表征有度中心性、介數(shù)中心性和接近中心性^[18]。其中，接近中心性是指任意節(jié)點(diǎn)對間的平均最短路徑?；诖耍覀儚墓?jié)點(diǎn)間最優(yōu)路徑長度對信息傳輸能力的影響和節(jié)點(diǎn)中心性兩個角度，給出節(jié)點(diǎn)對間的緊密中心性函數(shù)，表示為

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

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

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

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

2.3 節(jié)點(diǎn)間相似度傳輸矩陣構(gòu)建

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

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

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

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

2.4 算法流程

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

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

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

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

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

6）生成相應(yīng)的節(jié)點(diǎn)相似性得分矩陣。

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

3 實(shí)驗(yàn)條件介紹

3.1 算法衡量標(biāo)準(zhǔn)

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

為了評估本文所提算法的性能，采用AUC和Pre兩個衡量指標(biāo)對其進(jìn)行測試和分析。實(shí)驗(yàn)中，每個AUC和Pre結(jié)果均為500次獨(dú)立實(shí)驗(yàn)結(jié)果的均值。

4.1 AUC結(jié)果及分析

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

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

4.2 Pre結(jié)果及分析

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[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] 顧秋陽， 吳寶， 池仁勇. 基于高階路徑相似度的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測方法[J]. 通信學(xué)報， 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] 胡鋼， 高浩， 徐翔， 等. 基于重要度傳輸矩陣的復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性辨識方法[J]. 電子學(xué)報， 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)絡(luò)關(guān)鍵節(jié)點(diǎn)識別方法[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 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] 郭世澤， 陸哲明. 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京：科學(xué)出版社，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.

（責(zé)任編輯 耿金花）