顧秋陽，吳寶，池仁勇

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

1 引言

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

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

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

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

2 算法設(shè)計

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

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

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

算法1HPS-LP 算法

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

輸出得分矩陣

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

2) 對每個節(jié)點對(i,j)do

3) 將公共近鄰賦值為z

4) 計算路徑得分

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

6) 循環(huán)計算高階路徑長度

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

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

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

10) 進行參數(shù)更新

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

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

3 數(shù)值算例

3.1 數(shù)據(jù)說明與評價標(biāo)準(zhǔn)

本文使用國內(nèi)外共10 個相關(guān)數(shù)據(jù)集對所提HPS-LP 法進行驗證。本文利用Python 工具從新浪微博（爬取時間為2020 年4 月6 日至2020 年8 月12 日）、Twitter（爬取時間為2020 年3 月14 日至2020 年7 月29 日）、Facebook（爬取時間為2020年2 月10 日至2020 年8 月19 日）和Dolphins（爬取時間為2020 年3 月27 日至2020 年7 月13 日）的API 端口，以“華為”和“HUAWEI”為關(guān)鍵詞選取30 個節(jié)點作為初始節(jié)點，爬取真實用戶數(shù)據(jù)集作為實驗的基礎(chǔ)數(shù)據(jù)。Netscience[8]是2006 年編制的網(wǎng)絡(luò)理論和實驗的合著者網(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)域，且使用了至少撰寫3 篇論文及以上的作者作為節(jié)點形成的網(wǎng)絡(luò)[18]。dblp-collab 來自1999—2003 年DBLP 計算機科學(xué)文獻[19]，其中dblp-collab 為計算機科學(xué)作者合作網(wǎng)絡(luò)。本文使用五重交叉驗證程序來評估所提算法的性能，并將所有數(shù)據(jù)以CSV 格式保存在MySQL 數(shù)據(jù)庫中以便進行數(shù)據(jù)處理。使用Rapidminer 數(shù)據(jù)挖掘工具隨機選取各用戶評級數(shù)據(jù)的20%作為測試集，并將剩下的80%用戶數(shù)據(jù)作為訓(xùn)練集。表1 為數(shù)據(jù)集統(tǒng)計信息。

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

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

3.2 基準(zhǔn)算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

11) Propflow 指數(shù)[22]?；诹麟S機游走的鏈路算法通過將粒子的隨機游走限制在有限步以內(nèi)，當(dāng)游走時遇到已游走過的節(jié)點或者回到原始節(jié)點則停止游走。

3.3 實驗結(jié)果

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

表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ù)測法在非大型數(shù)據(jù)集中具有較優(yōu)效果；ERA 法作為一種基于節(jié)點間本地路徑傳輸潛在資源的鏈路預(yù)測方法，故能有效對科研合作網(wǎng)絡(luò)中的潛在合作鏈路實現(xiàn)預(yù)測?；贑N 的鏈路預(yù)測算法普遍效果較差，這是由于在信息爆炸的現(xiàn)狀下，受各種拓?fù)涮卣骱拖到y(tǒng)動力學(xué)要素的影響，CN 并不足以涵蓋預(yù)測所需的信息。N2V 法作為一種節(jié)點嵌入技術(shù)，為保持鄰域結(jié)構(gòu)犧牲了部分預(yù)測精度，故在大型數(shù)據(jù)集中性能較差。

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

3.4 敏感性分析

針對參數(shù)值ψ的影響，本文將不同長度的路徑作為特征屬性來計算網(wǎng)絡(luò)中兩節(jié)點間的相似度。本文就參數(shù)值ψ在區(qū)間[0.0,1.0]范圍內(nèi)對曲線下面積和精度值的影響進行了分析。圖1 為不同復(fù)雜網(wǎng)絡(luò)中基于曲線下面積值的懲罰參數(shù)敏感性分析（由于其他算法的曲線下面積敏感性參數(shù)都遠差于本文所提算法，故在此不再贅述）。由圖1 可知，本文所提HPS-LP 法在社交網(wǎng)絡(luò)和科研協(xié)作網(wǎng)絡(luò)中受參數(shù)值ψ影響不顯著，而LP 法受參數(shù)值ψ的穩(wěn)定性僅次于HPS-LP 法。相比其他網(wǎng)絡(luò)，鏈路預(yù)測方法普遍在社交網(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ù)都遠差于本文所提算法，故在此不再贅述）。由圖2 可知，本文所提HPS-LP 法精度最高，LP 法其次。Katz法隨懲罰參數(shù)值的變化較大，這本質(zhì)上是由于其為一種最短路徑度量方法，故預(yù)測結(jié)果存在不穩(wěn)定性。相對社交網(wǎng)絡(luò)，懲罰參數(shù)值對科研協(xié)作網(wǎng)絡(luò)的影響較大，這是由于科研合作網(wǎng)絡(luò)具有較低度值，故算法穩(wěn)定性更高。

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

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

表4 路徑長度對鏈路預(yù)測精度的影響

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

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

4 結(jié)束語

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

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