基于高阶近似的链路预测算法  

Link prediction algorithm based on high-order proximity approximation

作　　者：杨燕琳 冶忠林 赵海兴[1,2,3,4] 孟磊 YANG Yanlin;YE Zhonglin;ZHAO Haixing;MENG Lei(College of Computer,Qinghai Normal University,Xining Qinghai 810016,China;Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province(Qinghai Normal University),Xining Qinghai 810008,China;Key Laboratory of Tibetan Information Processing of Ministry of Education(Qinghai Normal University),Xining Qinghai 810008,China;School of Computer Science,Shaanxi Normal University,Xi'an Shaanxi 710062,China)

机构地区：[1]青海师范大学计算机学院,西宁810016 [2]青海省藏文信息处理与机器翻译重点实验室(青海师范大学),西宁810008 [3]藏文信息处理教育部重点实验室(青海师范大学),西宁810008 [4]陕西师范大学计算机科学学院,西安710062

出　　处：《计算机应用》2019年第8期2366-2373,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(11661069,61663041,61763041);藏文信息处理与机器翻译重点实验室项目(2013-Z-Y17)~~

摘　　要：目前大部分链路预测算法只研究了节点与邻居节点之间的一阶相似性,没有考虑节点与邻居的邻居节点之间的高阶相似性关系。针对此问题,提出一种基于高阶近似的链路预测算法(LP-HOPA)。首先,求出网络的归一化邻接矩阵和相似度矩阵;其次,利用矩阵分解的方法将相似度矩阵进行分解,得到网络节点的表示向量以及其上下文的表示向量;然后,通过高阶网络表示学习的网络嵌入更新(NEU)算法对原始相似度矩阵进行高阶优化,并利用归一化的邻接矩阵计算出更高阶的相似度矩阵表示;最后,在四个真实的数据集上进行大量的实验。实验结果表明,与原始链路预测算法相比,大部分利用LP-HOPA优化后的链路预测算法准确率提升了4%到50%。此外,LP-HOPA算法能够将基于低阶网络局部结构信息的链路预测算法转换为基于节点高阶特征的链路预测算法,在一定程度上肯定了基于高阶近似链路预测算法的有效性和可行性。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.

关 键 词：链路预测 高阶近似 相似度矩阵 矩阵分解 网络嵌入更新算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]