基于高階近似的鏈路預(yù)測算法

楊燕琳 冶忠林 趙海興 孟磊

摘 要：目前大部分鏈路預(yù)測算法只研究了節(jié)點與鄰居節(jié)點之間的一階相似性，沒有考慮節(jié)點與鄰居的鄰居節(jié)點之間的高階相似性關(guān)系。針對此問題，提出一種基于高階近似的鏈路預(yù)測算法（LP-HOPA）。首先，求出網(wǎng)絡(luò)的歸一化鄰接矩陣和相似度矩陣;其次，利用矩陣分解的方法將相似度矩陣進(jìn)行分解，得到網(wǎng)絡(luò)節(jié)點的表示向量以及其上下文的表示向量;然后，通過高階網(wǎng)絡(luò)表示學(xué)習(xí)的網(wǎng)絡(luò)嵌入更新（NEU）算法對原始相似度矩陣進(jìn)行高階優(yōu)化，并利用歸一化的鄰接矩陣計算出更高階的相似度矩陣表示;最后，在四個真實的數(shù)據(jù)集上進(jìn)行大量的實驗。實驗結(jié)果表明，與原始鏈路預(yù)測算法相比，大部分利用LP-HOPA優(yōu)化后的鏈路預(yù)測算法準(zhǔn)確率提升了4%到50%。此外，LP-HOPA算法能夠?qū)⒒诘碗A網(wǎng)絡(luò)局部結(jié)構(gòu)信息的鏈路預(yù)測算法轉(zhuǎn)換為基于節(jié)點高階特征的鏈路預(yù)測算法，在一定程度上肯定了基于高階近似鏈路預(yù)測算法的有效性和可行性。

關(guān)鍵詞：鏈路預(yù)測;高階近似;相似度矩陣;矩陣分解;網(wǎng)絡(luò)嵌入更新算法

中圖分類號：?TP393

文獻(xiàn)標(biāo)志碼：A

Link prediction algorithm based on high-order proximity approximation

YANG Yanlin1，2，3， YE Zhonglin1，2，3，4， ZHAO Haixing1，2，3，4*， MENG Lei1，2，3

1.College of Computer， Qinghai Normal University， Xining Qinghai 810016， China ;

2.Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province （Qinghai Normal University）， Xining Qinghai 810008， China ;

3.Key Laboratory of Tibetan Information Processing of Ministry of Education （Qinghai Normal University）， Xining Qinghai 810008， China ;

4.School of Computer Science， Shaanxi Normal University， Xian Shaanxi 710062， China

Abstract：?Most of the existing link prediction algorithms only study the first-order similarity between nodes and their neighbor nodes， without considering the high-order similarity between nodes and the neighbor nodes of their neighbor nodes. In order to solve this problem， a Link Prediction algorithm based on High-Order Proximity Approximation （LP-HOPA） was proposed. Firstly， the normalized adjacency matrix and similarity matrix of a network were solved. Secondly， the similarity matrix was decomposed by the method of matrix decomposition， and the representation vectors of the network nodes and their contexts were obtained. Thirdly， the original similarity matrix was high-order optimized by using Network Embedding Update （NEU） algorithm of high-order network representation learning， and the higher-order similarity matrix representation was calculated by using the normalized adjacency matrix. Finally， a large number of experiments were carried out on four real datasets. Experiments results show that， compared with the original link prediction algorithm， the accuracy of most of the link prediction algorithms optimized by LP-HOPA is improved by 4% to 50%. In addition， LP-HOPA can transform the link prediction algorithm based on local structure information of low-order network into the link prediction algorithm based on high-order characteristics of nodes， which confirms the validity and feasibility of the link prediction algorithm based on high order proximity approximation to a certain extent.

Key words：?link prediction; high-order proximity approximation; similarity matrix; matrix decomposition; Network Embedding Update （NEU） algorithm

0 引言

隨著網(wǎng)絡(luò)科學(xué)的不斷進(jìn)步，網(wǎng)絡(luò)的演化機(jī)制[1]受到了學(xué)者們的廣泛關(guān)注，而鏈路預(yù)測為網(wǎng)絡(luò)的演化提供了一個高效簡單的比較機(jī)制，因此，對鏈路預(yù)測的研究也受到了學(xué)者們的廣泛關(guān)注。網(wǎng)絡(luò)中的鏈路預(yù)測是指如何通過已知網(wǎng)絡(luò)的特征、結(jié)構(gòu)和節(jié)點信息等預(yù)測不相連的兩個節(jié)點之間產(chǎn)生鏈接的可能性[2]。鏈路預(yù)測的應(yīng)用對實際生活產(chǎn)生了重要的意義。例如，蛋白質(zhì)網(wǎng)絡(luò)[3]可預(yù)測沒有產(chǎn)生相互作用的蛋白質(zhì)節(jié)點未來產(chǎn)生相互作用的可能性，將最可能產(chǎn)生相互作用的蛋白質(zhì)做實驗， 可提高實驗的成功率;社交分析網(wǎng)絡(luò)[4]可預(yù)測陌生人成為朋友的可能性;標(biāo)簽分類[5]可通過節(jié)點的特征和性質(zhì)去預(yù)測節(jié)點的類別;異常檢測[6]可以通過鏈路預(yù)測預(yù)測網(wǎng)絡(luò)中的錯誤鏈接，對錯誤鏈接進(jìn)行糾正;信息推薦系統(tǒng)[7]則通過鏈路預(yù)測向用戶自動推薦可能需要的物品。除此之外，鏈路預(yù)測還應(yīng)用到了網(wǎng)絡(luò)建模[8]、知識獲取[9]等領(lǐng)域。為了將鏈路預(yù)測應(yīng)用到實際生活中，研究者們已經(jīng)提出了很多鏈路預(yù)測算法，大多是基于相似性和最大似然估計的鏈路預(yù)測算法，可是現(xiàn)實生活中產(chǎn)生的數(shù)據(jù)越來越多，網(wǎng)絡(luò)越來越復(fù)雜，規(guī)模越來越大，而這些鏈路預(yù)測算法大多存在著高計算復(fù)雜性和低精確性的問題，主要適用于小規(guī)模網(wǎng)絡(luò)，這就造成了鏈路預(yù)測應(yīng)用的局限性。

鄰接矩陣可以將網(wǎng)絡(luò)簡單直接地表示出來，但是鄰接矩陣占用了大量的存儲空間，數(shù)據(jù)十分稀疏，因此，研究者們轉(zhuǎn)而思考如何將網(wǎng)絡(luò)數(shù)據(jù)高效地表示出來。網(wǎng)絡(luò)表示學(xué)習(xí)（Network Representation Learning， NRL） [10]將網(wǎng)絡(luò)的節(jié)點信息轉(zhuǎn)化為低維稠密的向量來表示。因此，將鏈路預(yù)測與網(wǎng)絡(luò)表示學(xué)習(xí)相結(jié)合，可以更全面地讀取網(wǎng)絡(luò)節(jié)點信息，使鏈路預(yù)測結(jié)果更精確。DeepWalk[11]和LINE （Large-scale Information Network Embedding） [12]是最具代表性的基于神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表示學(xué)習(xí)算法。DeepWalk算法利用了網(wǎng)絡(luò)結(jié)構(gòu)的隨機(jī)游走序列信息，并通過節(jié)點及其上下文節(jié)點之間的關(guān)系訓(xùn)練神經(jīng)網(wǎng)絡(luò);LINE算法考慮了網(wǎng)絡(luò)的兩種相似度，用兩節(jié)點是否直接相連來刻畫一階相似度，用不相連的兩個節(jié)點的共同鄰居來刻畫二階相似性，該算法可被應(yīng)用于大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù)，但其精度卻不如DeepWalk算法。網(wǎng)絡(luò)嵌入更新（Network Embedding Update， NEU）算法 [13]是一種通過簡單的矩陣轉(zhuǎn)換構(gòu)建高階網(wǎng)絡(luò)表示的方法，但并不需要重新訓(xùn)練網(wǎng)絡(luò)表示學(xué)習(xí)模型，該算法可以應(yīng)用到任意的NRL方法，來提高它們的性能。例如，將該算法應(yīng)用在DeepWalk算法時，只用了DeepWalk算法運行時間的1%，即有顯著的提升。

目前大部分鏈路預(yù)測算法只研究了節(jié)點與鄰居節(jié)點之間的一階相似性，忽略了節(jié)點與鄰居的鄰居節(jié)點的高階相似性關(guān)系，比如二階相似性、三階相似性等。本文基于NEU表示學(xué)習(xí)算法，提出了一種基于高階近似的鏈路預(yù)測算法（Link Prediction algorithm Based on High Order Proximity Approximation， LP-HOPA）。該方法能夠?qū)⒒诘碗A網(wǎng)絡(luò)局部結(jié)構(gòu)信息的鏈路預(yù)測算法轉(zhuǎn)化為節(jié)點高階特征相似鏈路預(yù)測算法，提升其鏈路預(yù)測性能。該方法在相似矩陣分解的結(jié)果上進(jìn)行高階轉(zhuǎn)換，以獲得節(jié)點之間高階的關(guān)系，從而可以得到高階近似的相似度矩陣，該相似度矩陣給了節(jié)點之間的一階相似性、二階相似性，并可以推廣到節(jié)點之間的n階相似性，因此可以更精準(zhǔn)地預(yù)測節(jié)點間的相似性。

本文的主要工作有：1） 將NEU表示學(xué)習(xí)算法引入到網(wǎng)絡(luò)的鏈路預(yù)測中，提出了一種基于高階近似的鏈路預(yù)測算法LP-HOPA。

2）基于四個真實的數(shù)據(jù)集在17個常見的鏈路預(yù)測指標(biāo)進(jìn)行了鏈路預(yù)測實驗，結(jié)果表明，LP-HOPA可有效學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)特征，具有一定程度的可行性和有效性，而且它的鏈路預(yù)測性能優(yōu)于本文中用來對比的鏈路預(yù)測指標(biāo)。

LP-HOPA能夠?qū)⒒诘碗A網(wǎng)絡(luò)局部結(jié)構(gòu)信息的鏈路預(yù)測算法轉(zhuǎn)換為基于節(jié)點高階特征的鏈路預(yù)測算法，從而提升鏈路預(yù)測性能。

1 相關(guān)工作

近10年，得益于Clauset等2008年在Nature上發(fā)表的論文[14]以及Redner對這篇論文的評論文章[15]，鏈路預(yù)測的研究方法被相繼提出。目前，主要包括以下三大類方法：

第一類是基于相似性的鏈路預(yù)測方法，即節(jié)點相似性越大，說明連邊可能性越大。主要有如下三小類：

1）基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息相似性方法，主要包括基于共同鄰居（Common Neighbors， CN）[7]的相似性指標(biāo)、基于Adamic-Adar（Adamic-Adar， AA）[7]算法的相似性指標(biāo)、基于資源分配（Resource Allocation， RA）[7]的相似性指標(biāo)和基于優(yōu)先鏈接（Preferential Attachment， PA）[7]的相似性指標(biāo)。在共同鄰居的基礎(chǔ)上，可以詳細(xì)分成6種相似性指標(biāo)，包括基于余弦相似性指標(biāo)Salton[7]、Jaccard相似性指標(biāo)[7]、Sorenson相似性指標(biāo)[7]、大度節(jié)點有利相似性指標(biāo)HPI（Hub Promoted Index）[7]、大度節(jié)點不利相似性指標(biāo)HDI（Hub Depressed Index）[7]和節(jié)點對分配相似性指標(biāo)LHN-1（Leicht-Holme-Newman）[16]。在CN、AA和RA的基礎(chǔ)上，

文獻(xiàn)[17]中提出了基于局部樸素貝葉斯算法的相似性指標(biāo)LNBCN

（Local Naive Bayes model-CN）、LNBAA（Local Naive Bayes model-AA）和LNBRA（Local Naive Bayes model-RA）。

2）基于路徑的相似性方法，包括：基于局部路徑（Local Path， LP）[18]的相似性指標(biāo)、基于節(jié)點聲望的相似性指標(biāo)Katz[19]和LHN-II（Leicht-Holme-Newman II）指標(biāo)[16]。

3）基于隨機(jī)游走的相似性方法，包括：基于平均通勤時間（Average Commute time， ACT）[20]的相似性指標(biāo)、基于隨機(jī)游走的余弦相似性指標(biāo)Cos+[21]、局部隨機(jī)游走（Local Random Walk， LRW）[18]的相似性指標(biāo)、有疊加效應(yīng)的隨機(jī)游走（Superposed Random Walk， SRW）[18]相似性指標(biāo)和有重啟的隨機(jī)游走（Random Walk with Restart， RWR）[18]相似性指標(biāo)。

第二類是基于概率和最大似然估計的鏈路預(yù)測方法?；诟怕实逆溌奉A(yù)測方法通過構(gòu)建貝葉斯、馬爾可夫等數(shù)學(xué)模型預(yù)測未知的鏈接，基于最大似然估計的鏈路預(yù)測方法利用網(wǎng)絡(luò)的結(jié)構(gòu)信息得到最大似然數(shù)。Clauset等[14]最初提出基于最大似然估計的鏈路預(yù)測方法，將其應(yīng)用到有明顯層次的網(wǎng)絡(luò)結(jié)構(gòu)中，發(fā)現(xiàn)有比較高的精確度;

田甜等[22]提出了一種基于最大似然估計的鏈路預(yù)測模型，將腦網(wǎng)絡(luò)的數(shù)據(jù)建立了層次隨機(jī)圖，再結(jié)合馬爾可夫算法計算腦網(wǎng)絡(luò)邊的連接概率，結(jié)果顯示出了良好的預(yù)測性能。

第三類是基于機(jī)器學(xué)習(xí)的鏈路預(yù)測方法。該類方法在相似性鏈路預(yù)測方法的基礎(chǔ)之上進(jìn)一步獲取網(wǎng)絡(luò)特征。如廖亮等[23]針對機(jī)會網(wǎng)絡(luò)研究了基于

支持向量機(jī)（Support Vector Machine， SVM）

的鏈路預(yù)測，構(gòu)建了基于節(jié)點對空間相似性和時間特征加權(quán)融合的支持向量機(jī)模型，從空間相似性和時間特征兩個角度分析單節(jié)點對的連接概率，并證明了其具有很好的預(yù)測效果;吳祖峰等[24]將AdaBoost集成學(xué)習(xí)算法應(yīng)用到了鏈路預(yù)測中，在論文合作網(wǎng)絡(luò)和電子郵件網(wǎng)絡(luò)等進(jìn)行了實驗驗證;呂偉民等[25]將基于機(jī)器學(xué)習(xí)的鏈路預(yù)測方法應(yīng)用到了科研合作網(wǎng)絡(luò)中，提高了推薦合作的精確度。

基于相似性的鏈路預(yù)測方法不能充分挖掘網(wǎng)絡(luò)的結(jié)構(gòu)特征，尤其是基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息的相似性方法，預(yù)測準(zhǔn)確度較低;基于概率和基于最大似然估計的鏈路預(yù)測方法預(yù)測準(zhǔn)確度高，但算法復(fù)雜度較高，導(dǎo)致了此類方法應(yīng)用的局限性，主要適用于預(yù)測低階小規(guī)模網(wǎng)絡(luò);

基于機(jī)器學(xué)習(xí)的鏈路預(yù)測方法的預(yù)測效果較好，可以預(yù)測大規(guī)模網(wǎng)絡(luò)，但是節(jié)點特征矩陣占用了大量的存儲空間，數(shù)據(jù)稀疏，因此大大增加了特征讀取時間;而網(wǎng)絡(luò)表示學(xué)習(xí)可以將特征信息用低維稠密的向量表示出來，這就降低了算法的時間復(fù)雜度，應(yīng)用到鏈路預(yù)測中，具有低算法復(fù)雜度和高精確度的特點。

因此，有越來越多的學(xué)者提出了基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測算法。如楊曉翠等[26]提出了基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測算法，冶忠林等[27]提出了基于矩陣分解的DeepWalk鏈路預(yù)測算法，劉思等[28]提出了基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法，均得到了較好的預(yù)測結(jié)果，但他們都只考慮了節(jié)點與鄰居節(jié)點之間的一階相似性，忽略了節(jié)點與鄰居的鄰居節(jié)點的高階相似性關(guān)系;而本文提出的LP-HOPA能夠?qū)⒒诘碗A網(wǎng)絡(luò)局部結(jié)構(gòu)信息的鏈路預(yù)測算法轉(zhuǎn)化為節(jié)點高階特征相似鏈路預(yù)測算法，提升鏈路預(yù)測性能。

2 基于高階近似的鏈路預(yù)測

2.1 定義描述

信息網(wǎng)絡(luò)[29]：定義一個信息網(wǎng)絡(luò)為G=（V，E），其中V表示頂點集，E表示邊集。定義G的特征矩陣為 X ， X 是 | V | ×m維的，m表示節(jié)點的特征屬性個數(shù)。如果網(wǎng)絡(luò)G對應(yīng)的特征矩陣 X 是非空的，則G是一個信息網(wǎng)絡(luò)。

網(wǎng)絡(luò)表示學(xué)習(xí)[29]：給定一個信息網(wǎng)絡(luò)G=（V，E）， X 為G的特征矩陣，滿足任意頂點v∈V，學(xué)習(xí)將網(wǎng)絡(luò)用低維向量 r v∈ R k表示，其中 r v是一個低維稠密的實數(shù)向量，且滿足k | V | 。

鏈路預(yù)測[2]：給定一個無向網(wǎng)絡(luò)G=（V，E），其中V表示頂點集，E表示邊集。定義M為該網(wǎng)絡(luò)中的最大邊數(shù)，滿足M= | V | （ | V | -1）/2，M-E表示該網(wǎng)絡(luò)中不存在的邊集，而鏈路預(yù)測則是在集合M-E中找出未來可能連邊的頂點對。通過某種鏈路預(yù)測方法可計算出每對未連邊的頂點對的相似性分?jǐn)?shù)，分?jǐn)?shù)越高則連邊可能性越大。

2.2 高階網(wǎng)絡(luò)表示學(xué)習(xí)NEU算法

NEU算法是由Yang等[13]提出的一種基于矩陣轉(zhuǎn)換的高階近似網(wǎng)絡(luò)表示方法，可以應(yīng)用到任意的網(wǎng)絡(luò)表示學(xué)習(xí)算法中，以提高基類網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能。

給定超參數(shù)λ∈（0，1/2]，歸一化的鄰接矩陣 A ， R 和 C 分別表示信息網(wǎng)絡(luò)的網(wǎng)絡(luò)表示和上下文表示，通過NEU算法更新后， R ′和 C ′分別為更新后的網(wǎng)絡(luò)表示和上下文表示的方法如下：

R ′= R +λ A · R

C ′= C +λ A T· C

（1）

計算出 A · R 和 A T· C 的時間復(fù)雜度是O（ | V | d），因為矩陣 A 是稀疏的并且有O（ | V | ）個非零項，因此，式（1）一次迭代的整體時間復(fù)雜度為O（ | V | d）。

式（1）可以在進(jìn)一步推廣到二階形式，以獲得二階近似的網(wǎng)絡(luò)表示。首先更新 R 和 C ：

R ′= R +λ1 A · R +λ2 A ·（ A · R ）

C ′= C +λ1 A T· C +λ2 A T·（ A T· C ）

（2）

式（2）的時間復(fù)雜度仍然是O（ | V | d），但是它在一次迭代中可以得到比式（1）更高的相似矩陣近似。同時也可以使用比式（2）更復(fù)雜的更新公式來探索更高的近似，例如三階、四階……n階近似的網(wǎng)絡(luò)表示。

NEU算法避免了高階相似矩陣的精確計算，也避免了通過模型訓(xùn)練高階網(wǎng)絡(luò)表示模型，但可以產(chǎn)生高階近似的網(wǎng)絡(luò)表示，因此該算法可以有效提高網(wǎng)絡(luò)表示的質(zhì)量。直觀上，式（1）和（2）允許學(xué)習(xí)到的節(jié)點表示進(jìn)一步傳播到它們的鄰居，因此，頂點之間距離較長的相似將被嵌入。

2.3 基于高階近似的鏈路預(yù)測算法

通過NEU算法中節(jié)點向量的表示過程發(fā)現(xiàn)，該算法在矩陣分解的結(jié)果上更新以獲得更高階的網(wǎng)絡(luò)表示，使最后的向量效果蘊含更多的網(wǎng)絡(luò)結(jié)構(gòu)特征，因此將NEU算法運用到鏈路預(yù)測后可以得到高階相似矩陣，可以更精準(zhǔn)地預(yù)測節(jié)點間的相似性。在此基礎(chǔ)上，本文將NEU算法融入到鏈路預(yù)測中，提出了一種基于高階近似的鏈路預(yù)測算法LP-HOPA。

LP-HOPA流程如圖1所示，具體如下：

1）輸入網(wǎng)絡(luò)G=（V，E），其中V為頂點集，E為邊集。

2）將網(wǎng)絡(luò)分割成訓(xùn)練集和測試集，將訓(xùn)練集轉(zhuǎn)化為鄰接矩陣 A??? ～?? ∈ R |V|×|V|，如果vi和vj之間有連邊，則 A??? ～?? ij=1，否則 A??? ～?? ij=0。對角矩陣 D ∈ R |V|×|V|，Dii的數(shù)值即為vi的度。

3）將 A??? ～?? 轉(zhuǎn)化為歸一化鄰接矩陣 A ， A = D -1 A??? ～?? ，即每行之和等于1。

4）通過AA、CN、RA和MFI等鏈路預(yù)測基準(zhǔn)指標(biāo)計算相似矩陣 S ，并使用SVDS算法將 S 分解為 U |V|×k、 Σ k×k和 V Tk×|V| （此 V 為矩陣，區(qū)別于2.1小節(jié)的V，該V為頂點集） 三個矩陣。SVDS是奇異值分解（Singular Value Decomposition， SVD）的一種Matlab方法，表示取最大的6個特征值。

接著，將分解得到的這三個矩陣轉(zhuǎn)化為兩個矩陣的乘積：

ne = U ·? Σ

（3）

nc =? Σ? · V T

（4）

使得 S ≈ ne · nc 。

根據(jù)NEU算法得知， ne 為節(jié)點的表示向量， nc 為上下文的表示向量。

5）利用NEU算法在矩陣分解結(jié)果的基礎(chǔ)之上進(jìn)行更新，以獲得更高階的網(wǎng)絡(luò)特征相似度矩陣結(jié)果：

ne ′= ne +λ1 A · ne +λ2 A ·（ A · ne ）

（5）

nc ′= nc +λ1 A T· nc +λ2 A T·（ A T· nc ）

（6）

通過以上更新結(jié)果，可得到接近高階近似的相似矩陣： S ′≈ ne ′· nc ′。將該相似矩陣應(yīng)用到鏈路預(yù)測算法中，利用鏈路預(yù)測準(zhǔn)確度度量指標(biāo)AUC（Area Under the receiver operating characteristic Curve）指標(biāo)計算出AUC值，從而評估本文所提出的鏈路預(yù)測性能。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

本文選擇四個真實網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行測試，分別為：

1）Citeseer網(wǎng)絡(luò)： http：//citeseerx.ist.psu.edu/index。它是由3312篇世界頂級會議論文構(gòu)成的引文網(wǎng)絡(luò)，包含4732篇文章之間引用或被引用的關(guān)系。

2）DBLP（DataBase systems and Logic Programming）網(wǎng)絡(luò)： https：//dblp.uni-trier.de/。它是由3119個作者構(gòu)成的合作網(wǎng)絡(luò)，頂點表示作者，連邊表示作者之間的合作關(guān)系，包含39516個作者間的合作關(guān)系。

3）Cora網(wǎng)絡(luò)： http：//www.cs.umd.edu/～sen/lbc-proj/data/cora.tgz。它是由2708份科學(xué)出版物組成的引文網(wǎng)絡(luò)，包含5429條連邊。

4）Wiki網(wǎng)絡(luò)： https：//www.wikipedia.org/。該網(wǎng)絡(luò)是維基百科網(wǎng)頁鏈接網(wǎng)絡(luò)，本文只取了2405個網(wǎng)頁之間的17981個鏈接關(guān)系。

表1進(jìn)一步列出了這四個數(shù)據(jù)集的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征，其中： | V | 表示節(jié)點數(shù)， | E | 表示連邊數(shù)， | Y | 表示網(wǎng)絡(luò)標(biāo)簽數(shù)，K表示平均度，D表示網(wǎng)絡(luò)直徑，L表示平均路徑長度，P表示密度，C表示平均聚類系數(shù)。

3.2 評價指標(biāo)

本文鏈路預(yù)測準(zhǔn)確度的度量指標(biāo)采用AUC指標(biāo)[30]。AUC可以從整體上衡量算法的精確度，可以描述為在測試集中隨機(jī)選擇一條存在連邊的分?jǐn)?shù)值高于隨機(jī)選擇一條不存在連邊的分?jǐn)?shù)值的概率，如果獨立重復(fù)比較n次，有n1次在測試集中存在連邊的分?jǐn)?shù)大于不存在連邊的分?jǐn)?shù)，有n2次在測試集中存在連邊的分?jǐn)?shù)等于不存在連邊的分?jǐn)?shù)，則AUC值可以定義為：

AUC=（n1+0.5n2）/n

（7）

一般意義上，計算出的AUC值至少應(yīng)大于0.5，至多不超過1。AUC值越高，算法的準(zhǔn)確度越高。

3.3 基準(zhǔn)方法

本文將常用的17種基于相似性的鏈路預(yù)測算法作為基準(zhǔn)進(jìn)行性能比較。其中包括基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息的基準(zhǔn)方法：CN、Salton、HPI、HDI、LHN-1、AA、RA、PA、LNBAA、LNBCN、LNBRA;基于路徑的基準(zhǔn)方法：LP、Katz;基于隨機(jī)游走的基準(zhǔn)方法：ACT、Cos+;基于矩陣森林理論的相似性指標(biāo)（Matrix-Forest theory Index， MFI）[18];基于傳遞的相似性指標(biāo)（Transferring Similarty Common Neighbor，TSCN）[31]。下面分別對各基準(zhǔn)方法作簡要介紹。

Katz指標(biāo)考慮了x和y之間的所有路徑數(shù)，對于短路徑賦予大權(quán)重，對于長路徑賦予小權(quán)重。其中，β為可調(diào)參數(shù)。

SKatzxy=β A +β2 A 2+β3 A 3…=（ I -β A ）-1- I

（22）

16）基于平均通勤時間的相似性指標(biāo)ACT。

一個隨機(jī)粒子從節(jié)點x到達(dá)節(jié)點y平均要走的步數(shù)m（x，y），那么，節(jié)點x和y的平均通勤時間定義為：

n（x，y）=m（x，y）+m（y，x）

則其數(shù)值求解可以通過求該網(wǎng)絡(luò)拉普拉斯矩陣的偽逆 L +得到。如果節(jié)點x和y的平均通勤時間越短，則這兩個節(jié)點的相似度越高。

SACTxy= 1 l+xx+l+yy-2l+xy

（23）

17）基于隨機(jī)游走的余弦相似性指標(biāo)cos+。

在由向量 v x= Λ 2 U T e x展開的歐氏空間中， U 是一個標(biāo)準(zhǔn)正交矩陣， Λ 為對角矩陣，對角線元素為特征根， e x表示一個只有第x個為1，其他元素為0的一維向量; L +中的元素l+xy為vx和vy的內(nèi)積。

Scos+xy=cos（x，y）+=（l+xy） / ?l+xxl+yy

（24）

3.4 實驗設(shè)置

在LP-HOPA中，本文設(shè)置了四個網(wǎng)絡(luò)訓(xùn)練集的訓(xùn)練比例分別為0.7、0.8、0.9，測試集的訓(xùn)練比例分別為0.3、0.2、0.1;特征維度d設(shè)為100;超參數(shù)λ1=0.5，λ2=0.25;迭代次數(shù)maxIter設(shè)為3;最終實驗結(jié)果為各網(wǎng)絡(luò)獨立運行10次的平均值。

3.5 實驗結(jié)果

首先求出網(wǎng)絡(luò)的歸一化鄰接矩陣 A 和相似度矩陣 S ：其次，通過SVDS將 S 進(jìn)行分解，得到網(wǎng)絡(luò)節(jié)點的表示向量 ne 以及其上下文的表示向量 nc ：接著，通過高階網(wǎng)絡(luò)表示學(xué)習(xí)NEU算法在原始相似度矩陣的結(jié)果上進(jìn)行高階優(yōu)化;然后，利用歸一化的鄰接矩陣計算出更高階的相似度矩陣表示;最后，在Citeseer、DBLP、Cora和Wiki四個數(shù)據(jù)集上進(jìn)行實驗驗證。為驗證上述方法的可行性及有效性，本文使用3.3節(jié)的所有相似性鏈路預(yù)測基準(zhǔn)指標(biāo)進(jìn)行對比。

表2列出了在上述四個數(shù)據(jù)集上，其訓(xùn)練集的訓(xùn)練比例分別為0.7、0.8、0.9時，3.3節(jié)中原始方法和本文方法在各鏈路預(yù)測基準(zhǔn)算法的AUC值對比。

觀察表2中的數(shù)據(jù)結(jié)果，對于原始鏈路預(yù)測方法，在四個數(shù)據(jù)集上鏈路預(yù)測準(zhǔn)確率都高于80%的僅有4個算法，即LP、Katz、Cos+和MFI。其中Katz和MFI算法鏈路預(yù)測性能較優(yōu)，尤其是在Citeseer數(shù)據(jù)集上準(zhǔn)確率都達(dá)到了97%以上;而CN、Salton、HPI等算法在Citeseer數(shù)據(jù)集上顯示鏈路預(yù)測準(zhǔn)確率較差，最低低至65%。

對比相關(guān)工作中所列出的基于相似性的鏈路預(yù)測算法發(fā)現(xiàn)，基于路徑的相似性方法鏈路預(yù)測性能較優(yōu)，基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息相似性方法性能較差。對于本文方法，在四個數(shù)據(jù)集上鏈路預(yù)測準(zhǔn)確率都高于80%的有14個算法，即為CN、Salton、HPI、HDI、LHN-1、AA、RA、LP、Katz、LNBAA、LNBCN、LNBRA、Cos+和MFI。其中HDI、LNBRA和Salton算法鏈路預(yù)測性能較優(yōu)，尤其是在DBLP數(shù)據(jù)集上準(zhǔn)確率都達(dá)到了93.5%以上;而ACT在Citeseer數(shù)據(jù)集上顯示鏈路預(yù)測準(zhǔn)確率較差，最低低至35.9%。

對比相關(guān)工作中所列出的基于相似性的鏈路預(yù)測算法發(fā)現(xiàn)，基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息相似性方法性能較優(yōu)，基于隨機(jī)游走的相似性方法鏈路預(yù)測性能較差。

通過對比原始鏈路預(yù)測方法和本文方法可以發(fā)現(xiàn)，利用LP-HOPA后，鏈路預(yù)測準(zhǔn)確率都高于80%的算法個數(shù)比原始鏈路預(yù)測算法多10個，這些算法為CN、Salton、HPI、HDI、LHN-1、AA、RA、LNBAA、LNBCN和LNBRA。大部分相比原始鏈路預(yù)測算法準(zhǔn)確率提升了4%到50%不等，僅有極個別算法有較小幅度的下降。

原始算法基于路徑的相似性方法鏈路預(yù)測性能較優(yōu)，而利用LP-HOPA后基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息相似性方法性能較優(yōu)，在一定程度上肯定了本文方法的可行性和有效性。

利用LP-HOPA后，在四個數(shù)據(jù)集上，CN、Salton、HPI、HDI、LHN-1、AA、RA、LNBAA、LNBRA和LBNCN算法的AUC值得到了大幅度提升，尤其是在Citeseer、Cora數(shù)據(jù)集上基本都提升了20個百分點，PA算法略微下降，但Katz、ACT、MFI和TSCN算法上鏈路預(yù)測準(zhǔn)確度卻有一定程度的下降，尤其是在Citeseer數(shù)據(jù)集上ACT算法AUC值比原始方法下降了40個百分點。PA算法是一種只考慮節(jié)點度對相似度影響的鏈路預(yù)測算法，而本文方法對PA算法進(jìn)行優(yōu)化時，由于并未考慮連邊，所以性能略微下降;Katz是基于全部路徑的鏈路預(yù)測算法，因此Katz是一個n階特征的鏈路預(yù)測算法，然而本文方法結(jié)合節(jié)點的高階特征，僅考慮了節(jié)點間6階以內(nèi)的相似性，因此將n階特征降至6階特征導(dǎo)致了鏈路預(yù)測性能下降;MFI是一種基于森林樹的算法，考慮的是兩個節(jié)點所在的相同網(wǎng)絡(luò)生成樹數(shù)量，因此考慮了網(wǎng)絡(luò)節(jié)點的高階特征相似性;ACT算法實質(zhì)上是考慮了兩個節(jié)點之間隨機(jī)游走來回的平均路徑長度之和，路徑越短，相似性越高，而LP-HOPA考慮了節(jié)點間6階以內(nèi)的相似性，因此性能有大幅度下降。

為了更進(jìn)一步分析個別相似性指標(biāo)使用本文方法后預(yù)測準(zhǔn)確率下降的原因，表3比較了1、3、5階對最終預(yù)測結(jié)果的影響。為使對比結(jié)果更加鮮明，2、4、6階對比結(jié)果未展示。

表3所示為Citeseer數(shù)據(jù)集在訓(xùn)練率為0.7時，對1、3、5階使用本文方法后的AUC值?？梢钥闯觯薃CT相似度指標(biāo)外，其他指標(biāo)的AUC值都是呈增加狀態(tài)。階數(shù)越高，ACT的預(yù)測準(zhǔn)確率反而越來越低，說明ACT路徑越短，相似性越高;Katz指標(biāo)呈增加趨勢，也可以由此說明若不斷將階數(shù)增加到n，Katz相似性指標(biāo)的AUC值也會不斷遞增;CN、Salton、AA和LNBRA等這些低階的相似性指標(biāo)呈現(xiàn)了一個很好的增加趨勢。

本文所采用的方法是結(jié)合節(jié)點間的二階相似、三階相似、n階相似綜合考慮節(jié)點的相似性，所以對于能夠轉(zhuǎn)換為高階特征的鏈路預(yù)測算法使用本文方法后性能會有所下降，但對于低階鏈路預(yù)測算法使用本文方法的鏈路預(yù)測準(zhǔn)確率都會有一定程度的提升，由此說明本文方法主要適用于基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息的低階鏈路預(yù)測基準(zhǔn)方法。

3.6 時間復(fù)雜度對比

圖2所示為Citeseer數(shù)據(jù)集下訓(xùn)練率為0.7時的鏈路預(yù)測算法時間復(fù)雜度對比，不同的數(shù)據(jù)集在不同的訓(xùn)練率下結(jié)果雖然不同，但是時間變化規(guī)律一致，因此時間復(fù)雜度對比結(jié)果具有代表性。橫坐標(biāo)表示相似性基準(zhǔn)方法，縱坐標(biāo)表示運行時間。通過對比可以看出，CN、Salton、HPI、HDI、LHN1、AA、RA、LP、LNBAA、LNBCN和LNBRA使用本文方法優(yōu)化后，時間復(fù)雜度基本與原始方法的時間復(fù)雜度持平，說明本文方法對低階鏈路預(yù)測算法能夠在不提升算法復(fù)雜度的情況下轉(zhuǎn)化為高階特征的鏈路預(yù)測算法，并提升其鏈路預(yù)測性能;PA、Katz、ACT、Cos+、MFI和TSCN在使用本文方法后的算法復(fù)雜度有不同程度的提高，尤其是MFI的運行時間有大幅度的增加，由此說明本文方法并不適用于可轉(zhuǎn)化為高階特征的鏈路預(yù)測算法。

3.7 度分布可視化

度分布是網(wǎng)絡(luò)的基本性質(zhì)之一，指網(wǎng)絡(luò)中節(jié)點的度的概率分布。度分布與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)密切相關(guān)，因此，研究網(wǎng)絡(luò)的度分布可以基本確定網(wǎng)絡(luò)的類型。本文使用Matlab實現(xiàn)了Citeseer、Cora、DBLP和Wiki四個數(shù)據(jù)集的度分布可視化。具體結(jié)果如圖3所示，橫坐標(biāo)表示該數(shù)據(jù)集節(jié)點度值，縱坐標(biāo)表示該度值對應(yīng)的節(jié)點個數(shù)。

通過對比四個數(shù)據(jù)集可以看出，Citeseer數(shù)據(jù)集中節(jié)點最大度僅為100，但度為1的節(jié)點高頻出現(xiàn)，高達(dá)1270次;Cora數(shù)據(jù)集節(jié)點的最大度值為169，度為2的節(jié)點較多，有567次;DBLP數(shù)據(jù)集中節(jié)點的最大度高于900，度為6的節(jié)點較多，有170次;Wiki數(shù)據(jù)集中節(jié)點最大度大于280，度為4的節(jié)點較多，有176次。通過對比，Citeseer和Cora數(shù)據(jù)集是相對比較稀疏的網(wǎng)絡(luò)，而DBLP和Wiki數(shù)據(jù)集是相對稠密的網(wǎng)絡(luò)。再通過對比表2和表3可以發(fā)現(xiàn)，不管是原始方法還是本文方法，DBLP和Wiki數(shù)據(jù)集鏈路預(yù)測效果比Citeseer和Cora數(shù)據(jù)集好。由此可以說明，鏈路預(yù)測對稠密的網(wǎng)絡(luò)的預(yù)測結(jié)果比稀疏的網(wǎng)絡(luò)好。

4 結(jié)語

本文針對目前大部分鏈路預(yù)測算法未考慮節(jié)點與鄰居的鄰居節(jié)點之間的高階相似性關(guān)系，提出了一種基于高階近似的鏈路預(yù)測算法LP-HOPA。首先，利用矩陣分解將相似度矩陣進(jìn)行分解;其次，通過高階網(wǎng)絡(luò)表示學(xué)習(xí)NEU算法在矩陣分解的結(jié)果上進(jìn)行更新，得到高階的相似度矩陣;最后，在Citeseer、DBLP、Cora和Wiki四個數(shù)據(jù)集上進(jìn)行了實驗驗證。實驗結(jié)果表明，在實際網(wǎng)絡(luò)的鏈路預(yù)測中，利用LP-HOPA可以進(jìn)行更加有效的高階轉(zhuǎn)換，使其鏈路預(yù)測性能比現(xiàn)有的眾多鏈路預(yù)測算法更加優(yōu)異。但是LP-HOPA也存在著不足，主要有以下兩點：1）LP-HOPA對于能夠轉(zhuǎn)換為高階特征的鏈路預(yù)測算法使性能會有所下降;2）本文只考慮了6階以內(nèi)的相似性，因此基于隨機(jī)游走的ACT算法性能有大幅度下降。在下一步的研究中，將嘗試考慮在高階轉(zhuǎn)換時融入外部信息，充分挖掘網(wǎng)絡(luò)的相關(guān)特征，并且將相似性階數(shù)提升，使其不僅能適用于網(wǎng)絡(luò)低階的鏈路預(yù)測算法，同樣基于高階特征的鏈路預(yù)測算法也有一定程度的提升。除此之外，還可基于本文方法結(jié)合邊的權(quán)值嘗試構(gòu)造相似性指標(biāo)。

參考文獻(xiàn)

[1]?ALBERT R， BARABSI A-L. Statistical mechanics of complex networks [J]. Reviews of Modern Physics， 2002， 74（1）： 47-97.

https：//doi.org/10.1103/RevModPhys.74.47

[2]??GETOOR L， DIEHL C P. Link mining： a survey [J]. ACM? SIGKDD Explorations Newsletter， 2005， 7（2）： 3-12.

[3]?YU H， BRAUN P， YILDIRIM M A， et al. High-quality binary protein interaction map of the yeast interactome network [J]. Science， 2008， 322（5898）： 104-110.

[4]?XIE X， LI Y， ZHANG Z， et al. A joint link prediction method for social network [C]// Proceedings of the 2015 International Conference of Young Computer Scientists， Engineers and Educators， CCIS 503. Berlin： Springer， 2015： 56-64.

[5]?KUMAR R， NOVAK J， TOMKINS A. Structure and evolution of online social networks [M]// Link Mining： Models， Algorithms， and Applications. New York： Springer， 2010： 337-357.

[6]?ZHANG X， ZHAO C， WANG X， et al. Identifying missing and spurious interactions in directed networks [C]// Proceedings of the 2014 International Conference on Wireless Algorithms， Systems， and Applications， LNCS 8491. Berlin： Springer， 2014： 470-481.

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

[8]?LEICHT E A， HOLME P， NEWMAN M E J. Vertex similarity in networks [J]. Physical Review E：Statistical Nonlinear & Soft Matter Physics， 2006， 73（2）： No.026120.

[9]?ZADEH P M， KOBTI Z. A knowledge based framework for link prediction in social networks [C]// Proceedings of the 2016 International Symposium on Foundations of Information and Knowledge Systems， LNCS 9616. Cham： Springer， 2016： 255-268.

[10]?涂存超， 楊成， 劉知遠(yuǎn)，等. 網(wǎng)絡(luò)表示學(xué)習(xí)綜述[J]. 中國科學(xué)：信息科學(xué)， 2017， 47（8）： 980-996. （TU C C， YANG C， LIU Z Y， et al. Network representation learning： an overview [J]. SCIENTIA SINICA Information， 2017， 47（8）： 980-996.）

[11]?BEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining， New York： ACM， 2014： 701-710.

[12]?TANG J， QU M， WANG M， et al. LINE： Large-scale information network embedding [C]// Proceedings of the 24th International Conference on World Wide Web. New York： ACM， 2015： 1067-1077.

[13]?YANG C， SUN M， LIU Z， et al. Fast network embedding enhancement via high order proximity approximation [C]// Proceedings of the 2017 26th International Joint Conference on Artificial Intelligence. Pola Alto， CA： AAAI， 2017： 3894-3900.

[14]?CLAUSET A， MOORE C， NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks [J]. Nature， 2008， 453（7191）： 98-101.

[15]?REDNER S. Networks： teasing out the missing links [J]. Nature， 2008， 453 （7191）： 47-48.

[16]?LEICHT E A， HOLME P， NEWMAN M E J. Vertex similarity in networks [J]. Physical Review E： Statistical Nonlinear & Soft Matter Physics， 2006， 73（2）： No. 026120.

[17]?LIU Z， ZHANG Q-M， LYU L， et al. Link prediction in complex networks： a local Naive Bayes model [J]. Europhysics Letters， 2011， 96（4）： No. 48007.

[18]?王富田，張鵬，肖井華.鏈路預(yù)測算法錯邊識別能力的評測[J/OL]. 中國科技論文在線， 2015 [2015-12-30]. http：//www.paper.edu.cn/releasepaper/content/201512-1363. （WANG F T， ZHANG P， XIAO J H. Evaluation the ability of link prediction methods in the spurious link detection [J/OL]. Sciencepaper Online， 2015 [2015-12-30]. http：//www.paper.edu.cn/releasepaper/content/201512-1363.）

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

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

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

[22]?田甜， 楊艷麗， 郭浩，等. 基于層次隨機(jī)圖模型的腦網(wǎng)絡(luò)鏈路預(yù)測[J]. 計算機(jī)應(yīng)用研究， 2016， 33（4）：1066-1069. （TIAN T， YANG Y L， GUO H， et al. Link prediction of brain networks based on hierarchical random graph model [J]. Application Research of Computers， 2016， 33（4）：1066-1069.）

[23]?廖亮， 張恒鋒. 基于支持向量機(jī)的機(jī)會網(wǎng)絡(luò)鏈路預(yù)測[J]. 信息通信， 2018（9）：28-30. （LIAO L， ZHANG H F. Link prediction based on support vector machine chance network [J]. Information & Communications， 2018（9）：23-25.）

[24]?吳祖峰，梁棋，劉嶠，等.基于AdaBoost的鏈路預(yù)測優(yōu)化算法[J]. 通信學(xué)報， 2014，35（3）：116-123. （WU Z F， LIANG Q， LIU Q， et al. Modified link prediction algorithm based on AdaBoost [J]. Journal on Communications， 2014， 35（3）：116-123.）

[25]?呂偉民，王小梅，韓濤.結(jié)合鏈路預(yù)測和ET機(jī)器學(xué)習(xí)的科研合作推薦方法研究[J]. 數(shù)據(jù)分析與知識發(fā)現(xiàn)， 2017，1（4）：38-45. （LYU W M， WANG X M， HAN T. Recommending scientific research collaborators with link prediction and extremely randomized trees algorithm [J]. Data Analysis and Knowledge Discovery， 2017， 1（4）：38-45.）

[26]?楊曉翠，宋甲秀，張曦煌.基于網(wǎng)絡(luò)表示學(xué)習(xí)的鏈路預(yù)測算法[J/OL].計算機(jī)科學(xué)與探索， 2018[2018-06-25]. http：//kns.cnki.net/kcms/detail/11.5602.TP.20180622.1301.008.html. （YANG X C， SONG J X， ZHANG X H. Link prediction algorithm based on network representation learning [J/OL]. Journal of Frontiers of Computer Science and Technology， 2018[2018-06-25]. http：//kns.cnki.net/kcms/detail/11.5602.TP.20180622.1301.008.html.）

http：//www.cnki.com.cn/Article/CJFDTOTAL-KXTS201905009.htm

[27]?冶忠林，曹蓉，趙海興，等.基于矩陣分解的DeepWalk鏈路預(yù)測算法[J/OL].計算機(jī)應(yīng)用研究， 2018 [2018-12-12 ]. http：//kns.cnki.net/KCMS/detail/51.1196.TP.20181211.1539.012.html. （YE Z L， CAO R， ZHAO H X， et al. Link prediction based on matrix factorization for DeepWalk [J/OL]. Application Research of Computers， 2018 [2018-12-12 ]. http：//kns.cnki.net/KCMS/detail/51.1196.TP.20181211.1539.012.html.）

http：//kns.cnki.net/KCMS/detail/51.1196.TP.20181211.1539.012.html

[28]?劉思， 劉海， 陳啟買， 等. 基于網(wǎng)絡(luò)表示學(xué)習(xí)與隨機(jī)游走的鏈路預(yù)測算法[J]. 計算機(jī)應(yīng)用， 2017， 37（8） ：2234-2239. （LIU S， LIU H， CHEN Q M， et al. Link prediction algorithm based on network representation learning and random walk [J]. Journal of Computer Applications， 2017， 37（8）： 2234-2239.）

[29]?陳維政，張巖，李曉明.網(wǎng)絡(luò)表示學(xué)習(xí)[J].大數(shù)據(jù)，2015，1（3）：8-22. （CHEN W Z， ZHANG Y， LI X M. Network representation learning [J]. Big Data Research， 2015， 1（3）： 8-22.）

[30]?HANLEY J A， MCNEIL B J. The meaning and use of the area under a Receiver Operating Characteristic （ROC） curve [J]. Radiology， 1982， 143（1）： 29-36.

[31]??CHEBOTAREV P， SHAMIS E. The matrix-forest theorem and? measuring relations in small social groups [J]. Automation & Remote Control， 1997， 58（9）： 1505-1514.