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

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

Link prediction algorithm based on high-order proximity approximation

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.