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

楊燕琳 冶忠林 趙海興 孟磊

摘 要：目前大部分鏈路預測算法只研究了節點與鄰居節點之間的一階相似性，沒有考慮節點與鄰居的鄰居節點之間的高階相似性關系。針對此問題，提出一種基于高階近似的鏈路預測算法（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]。……