基于高階近似的鏈路預測算法

楊燕琳 冶忠林 趙海興 孟磊

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

關鍵詞：鏈路預測;高階近似;相似度矩陣;矩陣分解;網絡嵌入更新算法

中圖分類號：?TP393

文獻標志碼：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 引言

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

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

目前大部分鏈路預測算法只研究了節點與鄰居節點之間的一階相似性，忽略了節點與鄰居的鄰居節點的高階相似性關系，比如二階相似性、三階相似性等。本文基于NEU表示學習算法，提出了一種基于高階近似的鏈路預測算法（Link Prediction algorithm Based on High Order Proximity Approximation， LP-HOPA）。該方法能夠將基于低階網絡局部結構信息的鏈路預測算法轉化為節點高階特征相似鏈路預測算法，提升其鏈路預測性能。該方法在相似矩陣分解的結果上進行高階轉換，以獲得節點之間高階的關系，從而可以得到高階近似的相似度矩陣，該相似度矩陣給了節點之間的一階相似性、二階相似性，并可以推廣到節點之間的n階相似性，因此可以更精準地預測節點間的相似性。

本文的主要工作有：1） 將NEU表示學習算法引入到網絡的鏈路預測中，提出了一種基于高階近似的鏈路預測算法LP-HOPA。

2）基于四個真實的數據集在17個常見的鏈路預測指標進行了鏈路預測實驗，結果表明，LP-HOPA可有效學習網絡的結構特征，具有一定程度的可行性和有效性，而且它的鏈路預測性能優于本文中用來對比的鏈路預測指標。

LP-HOPA能夠將基于低階網絡局部結構信息的鏈路預測算法轉換為基于節點高階特征的鏈路預測算法，從而提升鏈路預測性能。

1 相關工作

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

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

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

文獻[17]中提出了基于局部樸素貝葉斯算法的相似性指標LNBCN

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

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

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

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

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

第三類是基于機器學習的鏈路預測方法。該類方法在相似性鏈路預測方法的基礎之上進一步獲取網絡特征。如廖亮等[23]針對機會網絡研究了基于

支持向量機（Support Vector Machine， SVM）

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

基于相似性的鏈路預測方法不能充分挖掘網絡的結構特征，尤其是基于網絡局部結構信息的相似性方法，預測準確度較低;基于概率和基于最大似然估計的鏈路預測方法預測準確度高，但算法復雜度較高，導致了此類方法應用的局限性，主要適用于預測低階小規模網絡;

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

因此，有越來越多的學者提出了基于網絡表示學習的鏈路預測算法。如楊曉翠等[26]提出了基于網絡表示學習的鏈路預測算法，冶忠林等[27]提出了基于矩陣分解的DeepWalk鏈路預測算法，劉思等[28]提出了基于網絡表示學習與隨機游走的鏈路預測算法，均得到了較好的預測結果，但他們都只考慮了節點與鄰居節點之間的一階相似性，忽略了節點與鄰居的鄰居節點的高階相似性關系;而本文提出的LP-HOPA能夠將基于低階網絡局部結構信息的鏈路預測算法轉化為節點高階特征相似鏈路預測算法，提升鏈路預測性能。

2 基于高階近似的鏈路預測

2.1 定義描述

信息網絡[29]：定義一個信息網絡為G=（V，E），其中V表示頂點集，E表示邊集。定義G的特征矩陣為 X ， X 是 | V | ×m維的，m表示節點的特征屬性個數。如果網絡G對應的特征矩陣 X 是非空的，則G是一個信息網絡。

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

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

2.2 高階網絡表示學習NEU算法

NEU算法是由Yang等[13]提出的一種基于矩陣轉換的高階近似網絡表示方法，可以應用到任意的網絡表示學習算法中，以提高基類網絡表示學習算法的性能。

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

R ′= R +λ A · R

C ′= C +λ A T· C

（1）

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

式（1）可以在進一步推廣到二階形式，以獲得二階近似的網絡表示。首先更新 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）的時間復雜度仍然是O（ | V | d），但是它在一次迭代中可以得到比式（1）更高的相似矩陣近似。同時也可以使用比式（2）更復雜的更新公式來探索更高的近似，例如三階、四階……n階近似的網絡表示。

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

2.3 基于高階近似的鏈路預測算法

通過NEU算法中節點向量的表示過程發現，該算法在矩陣分解的結果上更新以獲得更高階的網絡表示，使最后的向量效果蘊含更多的網絡結構特征，因此將NEU算法運用到鏈路預測后可以得到高階相似矩陣，可以更精準地預測節點間的相似性。在此基礎上，本文將NEU算法融入到鏈路預測中，提出了一種基于高階近似的鏈路預測算法LP-HOPA。

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

1）輸入網絡G=（V，E），其中V為頂點集，E為邊集。

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

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

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

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

ne = U ·? Σ

（3）

nc =? Σ? · V T

（4）

使得 S ≈ ne · nc 。

根據NEU算法得知， ne 為節點的表示向量， nc 為上下文的表示向量。

5）利用NEU算法在矩陣分解結果的基礎之上進行更新，以獲得更高階的網絡特征相似度矩陣結果：

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

（5）

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

（6）

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

3 實驗結果與分析

3.1 實驗數據

本文選擇四個真實網絡數據集進行測試，分別為：

1）Citeseer網絡： http：//citeseerx.ist.psu.edu/index。它是由3312篇世界頂級會議論文構成的引文網絡，包含4732篇文章之間引用或被引用的關系。

2）DBLP（DataBase systems and Logic Programming）網絡： https：//dblp.uni-trier.de/。它是由3119個作者構成的合作網絡，頂點表示作者，連邊表示作者之間的合作關系，包含39516個作者間的合作關系。

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

4）Wiki網絡： https：//www.wikipedia.org/。該網絡是維基百科網頁鏈接網絡，本文只取了2405個網頁之間的17981個鏈接關系。

表1進一步列出了這四個數據集的網絡拓撲結構特征，其中： | V | 表示節點數， | E | 表示連邊數， | Y | 表示網絡標簽數，K表示平均度，D表示網絡直徑，L表示平均路徑長度，P表示密度，C表示平均聚類系數。

3.2 評價指標

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

AUC=（n1+0.5n2）/n

（7）

一般意義上，計算出的AUC值至少應大于0.5，至多不超過1。AUC值越高，算法的準確度越高。

3.3 基準方法

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

Katz指標考慮了x和y之間的所有路徑數，對于短路徑賦予大權重，對于長路徑賦予小權重。其中，β為可調參數。

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

（22）

16）基于平均通勤時間的相似性指標ACT。

一個隨機粒子從節點x到達節點y平均要走的步數m（x，y），那么，節點x和y的平均通勤時間定義為：

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

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

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

（23）

17）基于隨機游走的余弦相似性指標cos+。

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

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

（24）

3.4 實驗設置

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

3.5 實驗結果

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

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

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

對比相關工作中所列出的基于相似性的鏈路預測算法發現，基于路徑的相似性方法鏈路預測性能較優，基于網絡局部結構信息相似性方法性能較差。對于本文方法，在四個數據集上鏈路預測準確率都高于80%的有14個算法，即為CN、Salton、HPI、HDI、LHN-1、AA、RA、LP、Katz、LNBAA、LNBCN、LNBRA、Cos+和MFI。其中HDI、LNBRA和Salton算法鏈路預測性能較優，尤其是在DBLP數據集上準確率都達到了93.5%以上;而ACT在Citeseer數據集上顯示鏈路預測準確率較差，最低低至35.9%。

對比相關工作中所列出的基于相似性的鏈路預測算法發現，基于網絡局部結構信息相似性方法性能較優，基于隨機游走的相似性方法鏈路預測性能較差。

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

原始算法基于路徑的相似性方法鏈路預測性能較優，而利用LP-HOPA后基于網絡局部結構信息相似性方法性能較優，在一定程度上肯定了本文方法的可行性和有效性。

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

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

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

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

3.6 時間復雜度對比

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

3.7 度分布可視化

度分布是網絡的基本性質之一，指網絡中節點的度的概率分布。度分布與網絡的拓撲結構性質密切相關，因此，研究網絡的度分布可以基本確定網絡的類型。本文使用Matlab實現了Citeseer、Cora、DBLP和Wiki四個數據集的度分布可視化。具體結果如圖3所示，橫坐標表示該數據集節點度值，縱坐標表示該度值對應的節點個數。

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

4 結語

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

參考文獻

[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]?涂存超， 楊成， 劉知遠，等. 網絡表示學習綜述[J]. 中國科學：信息科學， 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]?王富田，張鵬，肖井華.鏈路預測算法錯邊識別能力的評測[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]. 計算機應用研究， 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]. 信息通信， 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的鏈路預測優化算法[J]. 通信學報， 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]?呂偉民，王小梅，韓濤.結合鏈路預測和ET機器學習的科研合作推薦方法研究[J]. 數據分析與知識發現， 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]?楊曉翠，宋甲秀，張曦煌.基于網絡表示學習的鏈路預測算法[J/OL].計算機科學與探索， 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鏈路預測算法[J/OL].計算機應用研究， 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]?劉思， 劉海， 陳啟買， 等. 基于網絡表示學習與隨機游走的鏈路預測算法[J]. 計算機應用， 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]?陳維政，張巖，李曉明.網絡表示學習[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.