基于高階路徑相似度的復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)方法

顧秋陽(yáng)，吳寶，池仁勇

（1.浙江工業(yè)大學(xué)管理學(xué)院，浙江 杭州 310023；2.浙江工業(yè)大學(xué)中國(guó)中小企業(yè)研究院，浙江 杭州 310023）

1 引言

復(fù)雜系統(tǒng)普遍存在于人類社會(huì)中，常采用復(fù)雜網(wǎng)絡(luò)對(duì)人類行為進(jìn)行研究。隨著近年來(lái)信息技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)信息已成為大眾獲取信息、參與社交必不可少的媒介工具，而鏈路預(yù)測(cè)作為連接復(fù)雜網(wǎng)絡(luò)與信息科學(xué)的重要橋梁，主要用于處理缺失信息的還原與預(yù)測(cè)，相關(guān)研究已受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。復(fù)雜網(wǎng)絡(luò)可對(duì)社會(huì)結(jié)構(gòu)、生物系統(tǒng)和信息系統(tǒng)等進(jìn)行有效建模，其中節(jié)點(diǎn)可表示網(wǎng)絡(luò)中的個(gè)體或群體，邊表示節(jié)點(diǎn)間的關(guān)系[1]。復(fù)雜網(wǎng)絡(luò)研究已成為計(jì)算機(jī)科學(xué)、物理學(xué)、系統(tǒng)科學(xué)等學(xué)科的研究熱點(diǎn)。現(xiàn)有研究多著重于復(fù)雜網(wǎng)絡(luò)的演化機(jī)制、拓?fù)浣Y(jié)構(gòu)等特征，而鏈路預(yù)測(cè)則為其中的基本問(wèn)題。在生物信息學(xué)領(lǐng)域中，鏈路預(yù)測(cè)在傳染病、蛋白質(zhì)等研究中都具有重要意義。鏈路預(yù)測(cè)在社會(huì)網(wǎng)絡(luò)的相關(guān)研究中應(yīng)用于好友預(yù)測(cè)及推薦。此外，還可通過(guò)鏈路預(yù)測(cè)實(shí)現(xiàn)科研合作推薦、知識(shí)產(chǎn)權(quán)推薦等[2]。鏈路預(yù)測(cè)技術(shù)有助于探測(cè)網(wǎng)絡(luò)中個(gè)體間存在的潛在關(guān)系，可用于恐怖分子間的關(guān)系發(fā)現(xiàn)，以有效預(yù)防和制止犯罪行為[3]。由此可知，復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)技術(shù)在不同應(yīng)用場(chǎng)景中存在廣泛應(yīng)用案例。

現(xiàn)有復(fù)雜網(wǎng)絡(luò)常用圖表示，其中節(jié)點(diǎn)表示個(gè)體或群體，邊表示個(gè)體或群體間的交互行為。由于真實(shí)復(fù)雜網(wǎng)絡(luò)中一般存在不斷進(jìn)入和移除的節(jié)點(diǎn)和邊，故導(dǎo)致了系統(tǒng)的復(fù)雜性[4]。現(xiàn)今應(yīng)用在復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法普遍存在精度不高、計(jì)算時(shí)間過(guò)長(zhǎng)等問(wèn)題，故提升鏈路預(yù)測(cè)的精度和效率是學(xué)術(shù)界亟待解決的重要問(wèn)題。學(xué)術(shù)界通常將靜態(tài)鏈路預(yù)測(cè)定義為被觀測(cè)網(wǎng)絡(luò)中尋找節(jié)點(diǎn)間的缺失鏈接，將動(dòng)態(tài)鏈路預(yù)測(cè)定義為基于現(xiàn)有復(fù)雜網(wǎng)絡(luò)是否可預(yù)測(cè)節(jié)點(diǎn)間存在未來(lái)鏈路的可能性。計(jì)算簡(jiǎn)單、效率高的基于相似性的鏈路預(yù)測(cè)方法最常見(jiàn)。通常包括基于鄰域的鏈路預(yù)測(cè)方法（如公共近鄰（CN,common neighbor）[5]、Jaccard 法[6]、Adamic/Adar（AA）法[7]、資源分配（RA,resource allocation）法[8]、偏好依附（PA,preferential attachment）法[9]等）和基于路徑的鏈路預(yù)測(cè)方法（如Katz 指數(shù)[10]等），以探索網(wǎng)絡(luò)中的全局信息。類局部方法采用的信息量與全局方法相同，計(jì)算效率與局部方法相同，故通常認(rèn)為其為局部方法和全局方法間的權(quán)衡。

目前，已有較多文獻(xiàn)對(duì)復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題提出了解決方法。基于相似性的鏈路預(yù)測(cè)方法中，節(jié)點(diǎn)對(duì)間相似性得分根據(jù)網(wǎng)絡(luò)的局部/全局拓?fù)浣Y(jié)構(gòu)特征值計(jì)算得到。為提高鏈路預(yù)測(cè)方法性能，現(xiàn)有方法常在復(fù)雜網(wǎng)絡(luò)拓?fù)涮卣髦性黾痈郊有畔11]，這在提升算法精度的同時(shí)也會(huì)使計(jì)算更加復(fù)雜。翟東升等[12]認(rèn)為，從較長(zhǎng)路徑中提取較短長(zhǎng)度的路徑更具相關(guān)性，而高階路徑數(shù)量是由更復(fù)雜的線性指標(biāo)決定的。Wu 等[13]以公共鄰居節(jié)點(diǎn)聚類系數(shù)的形式提取三角結(jié)構(gòu)信息，并利用真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行驗(yàn)證。Rahimi 等[14]指出，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，高連接節(jié)點(diǎn)的影響要小于網(wǎng)絡(luò)中心度較高但連接數(shù)量較少的節(jié)點(diǎn)。Kumar 等[15]將聚類系數(shù)推廣到存在高階路徑的復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中以提取局部路徑信息，并將擴(kuò)展聚類系數(shù)概念應(yīng)用于鏈路預(yù)測(cè)中。

通過(guò)對(duì)現(xiàn)有研究成果的梳理發(fā)現(xiàn)，復(fù)雜網(wǎng)絡(luò)中的鏈路預(yù)測(cè)方法已受到了國(guó)內(nèi)外學(xué)者的重視并得到了豐富研究。上述研究成果雖然對(duì)本文具有一定的借鑒意義，但也存在一些不足。首先，已有很多學(xué)者對(duì)鏈路預(yù)測(cè)方法開(kāi)展了一系列研究，但多數(shù)集中在基于路徑相似和公共近鄰的方法（如吳翼騰等[16]），很少有利用高階路徑作為判別特征，并對(duì)種子節(jié)點(diǎn)對(duì)間的可用長(zhǎng)路徑實(shí)施懲罰進(jìn)行鏈路預(yù)測(cè)的文獻(xiàn)記錄。其次，幾乎所有的相關(guān)文獻(xiàn)都只基于復(fù)雜網(wǎng)絡(luò)圖特征對(duì)鏈路預(yù)測(cè)方法提出了改進(jìn)（如李永立等[17]），很少有在網(wǎng)絡(luò)資源分配過(guò)程的啟發(fā)下基于高度路徑相似度進(jìn)行鏈路預(yù)測(cè)方法設(shè)計(jì)的文獻(xiàn)記錄。最后，現(xiàn)有文獻(xiàn)多在鏈路預(yù)測(cè)過(guò)程中使用了路徑相似度指數(shù)，很少有在計(jì)算過(guò)程中基于公共近鄰的連接懲罰限制信息泄露，以最大化描述節(jié)點(diǎn)間相似度節(jié)點(diǎn)對(duì)間信息流的文獻(xiàn)記錄。本文利用路徑作為判別特征對(duì)復(fù)雜網(wǎng)絡(luò)中的缺失鏈接進(jìn)行有效預(yù)測(cè)，提出了基于高階路徑相似度的鏈路預(yù)測(cè)（HPS-LP,high-order path similarity link prediction）算法。然后通過(guò)懲罰公共近鄰對(duì)信息泄露進(jìn)行限制，以最大化描述節(jié)點(diǎn)間相似度節(jié)點(diǎn)對(duì)間的信息流。最后以高階路徑（定義為六度分隔理論）作為判別特征，對(duì)種子節(jié)點(diǎn)對(duì)間的可用長(zhǎng)路徑實(shí)施懲罰。

2 算法設(shè)計(jì)

大多數(shù)社會(huì)網(wǎng)絡(luò)中會(huì)表現(xiàn)出小世界、聚類和無(wú)標(biāo)度等拓?fù)湫再|(zhì)。本文利用不同長(zhǎng)度的路徑來(lái)計(jì)算復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)間的相似度，基于網(wǎng)絡(luò)中的資源分配過(guò)程向目的地發(fā)送信息[8]。現(xiàn)有用于復(fù)雜網(wǎng)絡(luò)環(huán)境的鏈路預(yù)測(cè)方法普遍存在精度不高、計(jì)算時(shí)間過(guò)長(zhǎng)等問(wèn)題，且還不能對(duì)信息泄露等問(wèn)題進(jìn)行有效控制。本文基于資源分配過(guò)程進(jìn)行設(shè)計(jì)，根據(jù)目標(biāo)節(jié)點(diǎn)接收到的信息量進(jìn)行相似性分析。通過(guò)公共鄰節(jié)點(diǎn)間的信息泄露來(lái)最大化節(jié)點(diǎn)間相似性，以提升復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)精度和效率，對(duì)信息泄露進(jìn)行懲罰以實(shí)現(xiàn)有效控制。長(zhǎng)度為2 的路徑相似度可作為公共鄰度，故可將任意節(jié)點(diǎn)對(duì)間路徑長(zhǎng)度為2 的相似性得分表示為

其中，kz表示節(jié)點(diǎn)z的度。而高階路徑相似度每一條長(zhǎng)度大于2 的路徑都可分解為長(zhǎng)度為l?1 的路徑和與其相連的一條邊。而連接2 個(gè)節(jié)點(diǎn)的路徑相似度得分為其分解所得長(zhǎng)度為l?1 的路徑的相似度得分與構(gòu)成邊的路徑相似度得分的乘積，而較長(zhǎng)的路徑得分可表示為

其中，f1和f2分別為路徑邊與上一周期中路徑邊的相似性得分，最高路徑階數(shù)為6（由六度分隔理論定義），ψ為懲罰較長(zhǎng)路徑的懲罰參數(shù)。路徑相似度得分在第一次迭代中由路徑長(zhǎng)度為2 的得分計(jì)算得到（具體如式(1)所示）。路徑長(zhǎng)度得分f1和f2的累積效應(yīng)可得到長(zhǎng)度為3 的路徑相似性得分。在本文所提算法中，使用類似方法迭代計(jì)算高階路徑相似度，如算法1 所示。

算法1HPS-LP 算法

輸入復(fù)雜網(wǎng)絡(luò)圖G

輸出得分矩陣

1) 計(jì)算路徑為2 的相似度得分

2) 對(duì)每個(gè)節(jié)點(diǎn)對(duì)(i,j)do

3) 將公共近鄰賦值為z

4) 計(jì)算路徑得分

5) 基于步驟4)結(jié)果計(jì)算高階路徑得分

6) 循環(huán)計(jì)算高階路徑長(zhǎng)度

7) 計(jì)算鄰節(jié)點(diǎn)的高階路徑相似度得分

8) 結(jié)合上期末的路徑相似度得分進(jìn)行如式(2)所示計(jì)算

9) 基于步驟8)結(jié)果循環(huán)更新路徑得分

10) 進(jìn)行參數(shù)更新

11) 返回網(wǎng)絡(luò)得分矩陣

算法1 中的輸入為復(fù)雜網(wǎng)絡(luò)圖，輸出為包含所有節(jié)點(diǎn)對(duì)得分的矩陣。該算法主要包括初始化、計(jì)算和更新3 個(gè)階段，初始化階段在網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)對(duì)間為矩陣Score 分配長(zhǎng)度為2 的相似度得分，計(jì)算階段基于2 個(gè)長(zhǎng)度路徑得分矩陣迭代計(jì)算更高路徑長(zhǎng)度分?jǐn)?shù)，更新階段根據(jù)前一階段計(jì)算分?jǐn)?shù)迭代更新上述2 個(gè)矩陣。

3 數(shù)值算例

3.1 數(shù)據(jù)說(shuō)明與評(píng)價(jià)標(biāo)準(zhǔn)

本文使用國(guó)內(nèi)外共10 個(gè)相關(guān)數(shù)據(jù)集對(duì)所提HPS-LP 法進(jìn)行驗(yàn)證。本文利用Python 工具從新浪微博（爬取時(shí)間為2020 年4 月6 日至2020 年8 月12 日）、Twitter（爬取時(shí)間為2020 年3 月14 日至2020 年7 月29 日）、Facebook（爬取時(shí)間為2020年2 月10 日至2020 年8 月19 日）和Dolphins（爬取時(shí)間為2020 年3 月27 日至2020 年7 月13 日）的API 端口，以“華為”和“HUAWEI”為關(guān)鍵詞選取30 個(gè)節(jié)點(diǎn)作為初始節(jié)點(diǎn)，爬取真實(shí)用戶數(shù)據(jù)集作為實(shí)驗(yàn)的基礎(chǔ)數(shù)據(jù)。Netscience[8]是2006 年編制的網(wǎng)絡(luò)理論和實(shí)驗(yàn)的合著者網(wǎng)絡(luò)，SmaGri[4]是HistCite 軟件公司2009 年生產(chǎn)的Garfield collection引文網(wǎng)絡(luò)，為科學(xué)網(wǎng)絡(luò)搜索的結(jié)果。hep-ph 與astro-ph 表示2004—2009 年科研論文作者合作網(wǎng)絡(luò)，其中hep-ph 為物理現(xiàn)象學(xué)領(lǐng)域，astro-ph 為天體物理學(xué)領(lǐng)域，且使用了至少撰寫(xiě)3 篇論文及以上的作者作為節(jié)點(diǎn)形成的網(wǎng)絡(luò)[18]。dblp-collab 來(lái)自1999—2003 年DBLP 計(jì)算機(jī)科學(xué)文獻(xiàn)[19]，其中dblp-collab 為計(jì)算機(jī)科學(xué)作者合作網(wǎng)絡(luò)。本文使用五重交叉驗(yàn)證程序來(lái)評(píng)估所提算法的性能，并將所有數(shù)據(jù)以CSV 格式保存在MySQL 數(shù)據(jù)庫(kù)中以便進(jìn)行數(shù)據(jù)處理。使用Rapidminer 數(shù)據(jù)挖掘工具隨機(jī)選取各用戶評(píng)級(jí)數(shù)據(jù)的20%作為測(cè)試集，并將剩下的80%用戶數(shù)據(jù)作為訓(xùn)練集。表1 為數(shù)據(jù)集統(tǒng)計(jì)信息。

表1 數(shù)據(jù)集統(tǒng)計(jì)信息

鏈路預(yù)測(cè)問(wèn)題通常被視為二分類任務(wù)，故用于二分類任務(wù)的大部分評(píng)估指標(biāo)都可用于鏈路預(yù)測(cè)評(píng)估。在具有2 個(gè)類別的二分類任務(wù)的評(píng)估混淆矩陣中[13]，真正例（TP,true positive）表示正確預(yù)測(cè)鏈接的數(shù)量；真負(fù)例（TN,true negative）表示正確的未預(yù)測(cè)鏈接的數(shù)量；假正例（FP,false positive），表示錯(cuò)誤預(yù)測(cè)鏈接的數(shù)量；假負(fù)例（FN,false negative）表示錯(cuò)誤的未預(yù)測(cè)鏈接的數(shù)量。基于此，可得真正例率（TPR,true positive rate）、假正例率（FPR,false positive rate）、真負(fù)例率（TNR,true negative rate）和精確率（precision）等，其計(jì)算式可參考文獻(xiàn)[20]。基于以下2 個(gè)指標(biāo)進(jìn)行評(píng)估，即ROC 曲線下面積（AUROC,area under the receiver operating characteristics curve）[12]和平均精度（AP,average precision）[15]。ROC 曲線是Y 軸上的真正例率（敏感性）和X 軸上的假正例率（1-特異性）間的曲線，曲線下面積值為[0,1]的數(shù)據(jù)可使用梯形規(guī)則累加計(jì)算得到。曲線下面積值越高，鏈路預(yù)測(cè)方法的性能越好。平均精度是基于不同召回閾值計(jì)算的單點(diǎn)匯總值，為區(qū)間[0,1]召回值的平均精度值。

3.2 基準(zhǔn)算法

為體現(xiàn)本文所提HPS-LP 法的優(yōu)越性，將所述方法與多種非監(jiān)督結(jié)構(gòu)鏈路預(yù)測(cè)算法進(jìn)行對(duì)比。

1) CN 法。在給定的復(fù)雜網(wǎng)絡(luò)或圖中，給定一對(duì)節(jié)點(diǎn)x和y的公共鄰居的規(guī)模被計(jì)算為2 個(gè)節(jié)點(diǎn)鄰節(jié)點(diǎn)的交集大小，如式(3)所示。

其中，Γ(x)和Γ(y)分別為節(jié)點(diǎn)x和y的鄰居，在x和y間存在聯(lián)系的可能性隨著其間共有鄰居的數(shù)量而增加。

2) AA 法。該方法為一種基于共享特征的相似度計(jì)算方法，并將其用于鏈接預(yù)測(cè)中，具體計(jì)算方法如式(4)所示。

其中，z表示節(jié)點(diǎn)x和y的公共鄰節(jié)點(diǎn)，由此可知更多的權(quán)重被分配給階數(shù)較小的公共鄰節(jié)點(diǎn)。

3) Jaccard 系數(shù)法[6]。此度量方法與公共近鄰法相同，不同之處在于，如果2 個(gè)節(jié)點(diǎn)有較多的公共鄰點(diǎn)和較少的非公共鄰點(diǎn)，則其相似度較大。在將上述相似度分?jǐn)?shù)標(biāo)準(zhǔn)化后，可表示為

其中，Jaccard 系數(shù)被定義為從任意一個(gè)節(jié)點(diǎn)的所有鄰節(jié)點(diǎn)中選擇成對(duì)節(jié)點(diǎn)的公共鄰節(jié)點(diǎn)的概率。

4) 優(yōu)先連接（PA,preferential attachment）[9]。其將優(yōu)先依附的思想用于生成一個(gè)不斷增長(zhǎng)的無(wú)標(biāo)度網(wǎng)絡(luò)中，節(jié)點(diǎn)度數(shù)是預(yù)測(cè)新鏈接的關(guān)鍵屬性。度數(shù)越高的2 個(gè)節(jié)點(diǎn)在未來(lái)彼此交互的可能性越大，添加與節(jié)點(diǎn)x和y相關(guān)的新鏈接的可能性與節(jié)點(diǎn)度k(x)和k(y)成正比。節(jié)點(diǎn)x和y間的優(yōu)先鏈接分?jǐn)?shù)為

其中，節(jié)點(diǎn)特征值上的聚合函數(shù)可用于計(jì)算鏈接特征值。

5) CAR 指數(shù)[11]。基于兩節(jié)點(diǎn)共同近鄰為本地社區(qū)成員，則兩節(jié)點(diǎn)間的鏈路更可能存在的假設(shè)進(jìn)行設(shè)計(jì)，且會(huì)隨著種子節(jié)點(diǎn)對(duì)間的公共近鄰鏈路數(shù)量而增加，具體如式(7)所示。

其中，γ(z)為節(jié)點(diǎn)鄰域子集。

6) Katz 指數(shù)[10]。該指標(biāo)可看作最短路徑度量的改進(jìn)，可直接聚集x和y間的所有路徑，并對(duì)較長(zhǎng)路徑進(jìn)行指數(shù)轉(zhuǎn)儲(chǔ)懲罰，具體如式(8)表示。

其中，β表示控制路徑權(quán)重，A表示鄰接矩陣。

7) 本地路徑指數(shù)（LP,local path index）[6]。本地路徑指數(shù)法為局部與全局鏈路預(yù)測(cè)方法在精度和計(jì)算復(fù)雜度間的良好折中。如x和y間沒(méi)有直接聯(lián)系，表示x和y間長(zhǎng)度為n-1 的不同路徑，該指數(shù)也可擴(kuò)展為如式(9)所示的形式。

其中，n為最大階數(shù)。

8) Node2vec（N2V）[16]是一種節(jié)點(diǎn)嵌入技術(shù)，學(xué)習(xí)圖中節(jié)點(diǎn)的低維連續(xù)表示，目的是為了保持鄰域結(jié)構(gòu)，并將有偏隨機(jī)游動(dòng)作為抽樣策略。其中共存在4 個(gè)參數(shù)，即行走次數(shù)（即為每個(gè)節(jié)點(diǎn)生成的隨機(jī)游動(dòng)數(shù)）、游動(dòng)長(zhǎng)度（即每次隨機(jī)游動(dòng)中的節(jié)點(diǎn)數(shù)）、返回超參數(shù)p和輸入輸出超參數(shù)q。

9) 擴(kuò)展資源分配（ERA,extended resource allocation）[17]是一種2 個(gè)節(jié)點(diǎn)間通過(guò)本地路徑傳輸?shù)臐撛谫Y源，基于節(jié)點(diǎn)間的資源交換，提出了一種擴(kuò)展的資源分配指標(biāo)，具體如式(10)所示。

10) 資源傳輸容量（PIC,potential information capacity）[21]在考慮信息通道和容量的情況下，提出了信息容量的定義，用以量化節(jié)點(diǎn)間的信息傳輸能力，具體如式(11)所示。

11) Propflow 指數(shù)[22]。基于流隨機(jī)游走的鏈路算法通過(guò)將粒子的隨機(jī)游走限制在有限步以內(nèi)，當(dāng)游走時(shí)遇到已游走過(guò)的節(jié)點(diǎn)或者回到原始節(jié)點(diǎn)則停止游走。

3.3 實(shí)驗(yàn)結(jié)果

本文分別在 Python 環(huán)境中使用 Scipy[11]、Numpy[6]和LPmade 工具包[13]執(zhí)行上述算法和本文所提HPS-LP 法。然后利用上述評(píng)價(jià)指標(biāo)，對(duì)不同的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行評(píng)估，并對(duì)不同參數(shù)進(jìn)行了敏感性分析。由于實(shí)驗(yàn)中HPS-LP 法預(yù)測(cè)列表在每次運(yùn)行時(shí)的結(jié)果都有可能不同，故設(shè)置評(píng)估結(jié)果為迭代500 次運(yùn)行后的平均值，運(yùn)行的平均標(biāo)準(zhǔn)差為1.286。表2 為各數(shù)據(jù)集在不同方法中的曲線下面積值（其他算法的曲線下面積值都差于表中算法，故在此不再贅述）。從表2 可以看出，本文所提HPS-LP法在社交網(wǎng)絡(luò)數(shù)據(jù)集中都具有較優(yōu)的實(shí)驗(yàn)結(jié)果。在科研協(xié)作網(wǎng)絡(luò)中雖然結(jié)果也較好，但不能保證最優(yōu)。hep-ph 科研論文作者合作網(wǎng)絡(luò)的聚類系數(shù)較低，故具有長(zhǎng)度3 的路徑較少，故本文所提方法在上述2 個(gè)數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果相對(duì)較差，而在其他聚類系數(shù)較大的網(wǎng)絡(luò)中有較好表現(xiàn)。除本文所提HPS-LP 法外，LP 法與PIC 法次之，且分別在hep-ph 數(shù)據(jù)集和Twitter 數(shù)據(jù)集中具有較好表現(xiàn)，這是由于LP 法作為一種類局部鏈路預(yù)測(cè)法在非大型數(shù)據(jù)集中具有較優(yōu)效果，PIC 法作為一種重視信息傳輸?shù)逆溌奉A(yù)測(cè)方法在信息資源爆炸的社交網(wǎng)絡(luò)數(shù)據(jù)集中具有較優(yōu)效果。而基于CN 的鏈路預(yù)測(cè)算法普遍效果較差，這是由于在現(xiàn)今信息爆炸的狀況下，受各種拓?fù)涮卣骱拖到y(tǒng)動(dòng)力學(xué)要素的影響，只考慮CN 并不足以涵蓋預(yù)測(cè)所需的信息。

表2 各數(shù)據(jù)集在不同方法中的曲線下面積值

表3 為各數(shù)據(jù)集在不同方法中的平均精度值（其他算法的精度都差于表中算法，故在此不再贅述）。結(jié)果顯示，本文所提HPS-LP 法在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集中具有較高的平均精度值，而在聚類系數(shù)較低的科研協(xié)作網(wǎng)絡(luò)稀疏數(shù)據(jù)集中的平均精確度較低。除本文所提HPS-LP 法外，LP 與ERA 法的精度次之，都在科研合作網(wǎng)站中具有較優(yōu)效果，其原因是LP 法作為一種類局部鏈路預(yù)測(cè)法在非大型數(shù)據(jù)集中具有較優(yōu)效果；ERA 法作為一種基于節(jié)點(diǎn)間本地路徑傳輸潛在資源的鏈路預(yù)測(cè)方法，故能有效對(duì)科研合作網(wǎng)絡(luò)中的潛在合作鏈路實(shí)現(xiàn)預(yù)測(cè)。基于CN 的鏈路預(yù)測(cè)算法普遍效果較差，這是由于在信息爆炸的現(xiàn)狀下，受各種拓?fù)涮卣骱拖到y(tǒng)動(dòng)力學(xué)要素的影響，CN 并不足以涵蓋預(yù)測(cè)所需的信息。N2V 法作為一種節(jié)點(diǎn)嵌入技術(shù)，為保持鄰域結(jié)構(gòu)犧牲了部分預(yù)測(cè)精度，故在大型數(shù)據(jù)集中性能較差。

表3 各數(shù)據(jù)集在不同方法中的平均精度值

3.4 敏感性分析

針對(duì)參數(shù)值ψ的影響，本文將不同長(zhǎng)度的路徑作為特征屬性來(lái)計(jì)算網(wǎng)絡(luò)中兩節(jié)點(diǎn)間的相似度。本文就參數(shù)值ψ在區(qū)間[0.0,1.0]范圍內(nèi)對(duì)曲線下面積和精度值的影響進(jìn)行了分析。圖1 為不同復(fù)雜網(wǎng)絡(luò)中基于曲線下面積值的懲罰參數(shù)敏感性分析（由于其他算法的曲線下面積敏感性參數(shù)都遠(yuǎn)差于本文所提算法，故在此不再贅述）。由圖1 可知，本文所提HPS-LP 法在社交網(wǎng)絡(luò)和科研協(xié)作網(wǎng)絡(luò)中受參數(shù)值ψ影響不顯著，而LP 法受參數(shù)值ψ的穩(wěn)定性僅次于HPS-LP 法。相比其他網(wǎng)絡(luò)，鏈路預(yù)測(cè)方法普遍在社交網(wǎng)絡(luò)數(shù)據(jù)集中具有更優(yōu)表現(xiàn)。PIC 法受參數(shù)值ψ的穩(wěn)定性較差，這是由于其需考慮信息通道與信息容量。

圖1 不同復(fù)雜網(wǎng)絡(luò)中曲線下面積值的懲罰參數(shù)敏感性分析

圖2 為不同復(fù)雜網(wǎng)絡(luò)中精度值的懲罰參數(shù)敏感性分析（由于其他算法的精度敏感性參數(shù)都遠(yuǎn)差于本文所提算法，故在此不再贅述）。由圖2 可知，本文所提HPS-LP 法精度最高，LP 法其次。Katz法隨懲罰參數(shù)值的變化較大，這本質(zhì)上是由于其為一種最短路徑度量方法，故預(yù)測(cè)結(jié)果存在不穩(wěn)定性。相對(duì)社交網(wǎng)絡(luò)，懲罰參數(shù)值對(duì)科研協(xié)作網(wǎng)絡(luò)的影響較大，這是由于科研合作網(wǎng)絡(luò)具有較低度值，故算法穩(wěn)定性更高。

圖2 不同復(fù)雜網(wǎng)絡(luò)中精度值的懲罰參數(shù)敏感性分析

本文將路徑視為特征參數(shù)之一，認(rèn)為在大多數(shù)復(fù)雜網(wǎng)絡(luò)中任何兩節(jié)點(diǎn)間的路徑平均長(zhǎng)度為6（即六度分隔理論），故路徑長(zhǎng)度可達(dá)6。表4 為短路徑(l≤ 3)與長(zhǎng)路徑(l>3)下的鏈路預(yù)測(cè)精度。由表4可知，社交網(wǎng)絡(luò)中短路徑和長(zhǎng)路徑的曲線下面積值值沒(méi)有顯著差異；科研協(xié)作網(wǎng)絡(luò)短路徑和長(zhǎng)路徑的曲線下面積值存在顯著差異。當(dāng)考慮較長(zhǎng)路徑時(shí)，曲線下面積值在大多數(shù)科研協(xié)作網(wǎng)絡(luò)中甚至?xí)档停溌奉A(yù)測(cè)方法的精度沒(méi)有顯著提高。

表4 路徑長(zhǎng)度對(duì)鏈路預(yù)測(cè)精度的影響

本文基于以下假設(shè)對(duì)時(shí)間復(fù)雜度進(jìn)行了討論，即大多數(shù)復(fù)雜網(wǎng)絡(luò)都為稀疏的，并將每個(gè)節(jié)點(diǎn)的平均邊數(shù)設(shè)為n（網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)的階數(shù)）。最高階路徑lmax是節(jié)點(diǎn)對(duì)間路徑最大長(zhǎng)度，超過(guò)最高階路徑則定義認(rèn)為相似性概率對(duì)高階路徑不產(chǎn)生影響。本文所提HPS-LP 法的關(guān)鍵是計(jì)算2 個(gè)及以上的路徑長(zhǎng)度分?jǐn)?shù)。算法1 會(huì)循環(huán)迭代至O(n2)次，普通節(jié)點(diǎn)對(duì)的CN 值的成本為O(n2K)。對(duì)于階數(shù)更高的路徑，時(shí)間復(fù)雜度由2 個(gè)循環(huán)使用時(shí)間O(n2K)和O(nlgn) 組成，具有較高路徑的總時(shí)間復(fù)雜度為O(n2K)+O(n2)，故本文所提HPS-LP 法的總時(shí)間復(fù)雜度為O(n2K)。基準(zhǔn)算法的時(shí)間復(fù)雜度如文獻(xiàn)[14]所示，在此不再贅述。時(shí)間復(fù)雜度的算法比較結(jié)果如圖3 所示。

圖3 時(shí)間復(fù)雜度的算法比較結(jié)果

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

復(fù)雜網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)和演化會(huì)受到各種拓?fù)涮卣骱拖到y(tǒng)動(dòng)力學(xué)要素的制約。現(xiàn)有基于公共近鄰的鏈路預(yù)測(cè)方法普遍存在效率較低、維數(shù)災(zāi)難等問(wèn)題。而當(dāng)今信息爆發(fā)的現(xiàn)狀對(duì)復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)算法的運(yùn)行效率和精度提出了更高的要求。社交關(guān)系的重要性則要求必須在鏈路預(yù)測(cè)算法中考慮邊權(quán)重的影響。由于有關(guān)研究說(shuō)明用戶間的弱關(guān)系具有極高的商業(yè)價(jià)值，故對(duì)高階路徑中的鏈路預(yù)測(cè)及其隱私保護(hù)提出了更高的要求。故在本文所提HPS-LP 方法中，利用路徑作為判別特征來(lái)預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)中的缺失鏈接；并以資源分配過(guò)程為目標(biāo)，通過(guò)基于公共近鄰的連接懲罰限制信息泄露，以最大化描述節(jié)點(diǎn)間相似度的節(jié)點(diǎn)對(duì)間的信息流。高階路徑（基于六度分隔理論）也被用作判別特征，并對(duì)其應(yīng)用懲罰函數(shù)。本文在多個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)中進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明所提HPS-LP 法優(yōu)于基準(zhǔn)方法，且考慮高階路徑相似度能有效提高其對(duì)復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)精度，并顯著影響計(jì)算時(shí)間復(fù)雜度。

盡管本文已提出了上述具有重要意義的發(fā)現(xiàn)，但還具有一定局限性，其中一些可能會(huì)為未來(lái)的進(jìn)一步研究指明方向。首先，本文所提HPS-LP 法利用路徑作為判別特征進(jìn)行鏈路預(yù)測(cè)，故在后續(xù)研究中可結(jié)合更多具有路徑復(fù)雜性的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集來(lái)對(duì)本文所提鏈路預(yù)測(cè)方法進(jìn)行驗(yàn)證。其次，由于本文所提HPS-LP 法應(yīng)用了公共近鄰思想，故未來(lái)可嘗試?yán)蒙窠?jīng)網(wǎng)絡(luò)或探索異構(gòu)動(dòng)態(tài)網(wǎng)絡(luò)嵌入技術(shù)對(duì)鏈路預(yù)測(cè)方法進(jìn)行進(jìn)一步優(yōu)化，以消除可能存在的維數(shù)災(zāi)難等問(wèn)題。最后，由于本文所提方法以資源分配過(guò)程為目標(biāo)，故可結(jié)合社會(huì)化調(diào)查法和計(jì)算實(shí)驗(yàn)等研究框架，分別在有/無(wú)向圖中對(duì)所提鏈路預(yù)測(cè)方法進(jìn)行進(jìn)一步佐證。