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

doi:10.11772/j.issn.1001-9081.2019010213

计算机应用 ›› 2019, Vol. 39 ›› Issue (8): 2366-2373.DOI: 10.11772/j.issn.1001-9081.2019010213

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

杨燕琳^1,2,3, 冶忠林^1,2,3,4, 赵海兴^1,2,3,4, 孟磊^1,2,3

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

收稿日期:2019-01-30 修回日期:2019-03-26 出版日期:2019-08-10 发布日期:2019-04-16
通讯作者: 赵海兴
作者简介:杨燕琳(1995-),女,四川南充人,硕士研究生,CCF会员,主要研究方向:复杂网络、链路预测;冶忠林(1989-),男,青海民和人,博士研究生,CCF会员,主要研究方向:数据挖掘、自然语言表示学习;赵海兴(1969-),男,青海湟中人,教授,博士生导师,CCF会员,主要研究方向:复杂网络、超图理论;孟磊(1994-),男,河南项城人,硕士研究生,CCF会员,主要研究方向:复杂网络、超网络。
基金资助:
国家自然科学基金资助项目（11661069，61663041，61763041）；藏文信息处理与机器翻译重点实验室项目（2013-Z-Y17）。

Link prediction algorithm based on high-order proximity approximation

YANG Yanlin^1,2,3, YE Zhonglin^1,2,3,4, ZHAO Haixing^1,2,3,4, MENG Lei^1,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, Xi'an Shaanxi 710062, China

Received:2019-01-30 Revised:2019-03-26 Online:2019-08-10 Published:2019-04-16
Supported by:
This work is partially supported by National Natural Science Foundation of China (11661069, 61663041, 61763041), the Tibetan Information Processing and Machine Translation Key Laboratory (2013-Z-Y17).

摘要/Abstract

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

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

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

中图分类号:

TP393

杨燕琳, 冶忠林, 赵海兴, 孟磊. 基于高阶近似的链路预测算法[J]. 计算机应用, 2019, 39(8): 2366-2373.

YANG Yanlin, YE Zhonglin, ZHAO Haixing, MENG Lei. Link prediction algorithm based on high-order proximity approximation[J]. Journal of Computer Applications, 2019, 39(8): 2366-2373.

参考文献

[1] ALBERT R, BARABÁSI A-L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1):47-97.
[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.)
[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.)
[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.

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

Link prediction algorithm based on high-order proximity approximation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[2]	张成, 万源, 强浩鹏. 基于知识蒸馏的深度无监督离散跨模态哈希[J]. 计算机应用, 2021, 41(9): 2523-2531.
[3]	张元钧, 张曦煌. 基于图卷积与长短期记忆网络的动态网络表示学习模型[J]. 计算机应用, 2021, 41(7): 1857-1864.
[4]	王锦凯, 贾旭. 基于迁移孪生非负矩阵分解的静脉识别算法[J]. 计算机应用, 2021, 41(3): 898-903.
[5]	温雯, 刘芳, 蔡瑞初, 郝志峰. 面向群组用户时序行为的动态推荐算法[J]. 计算机应用, 2021, 41(1): 60-66.
[6]	田保军, 刘爽, 房建东. 融合主题信息和卷积神经网络的混合推荐算法[J]. 计算机应用, 2020, 40(7): 1901-1907.
[7]	王锦凯, 贾旭. 基于加权正交约束非负矩阵分解的车脸识别算法[J]. 计算机应用, 2020, 40(4): 1050-1055.
[8]	齐鹏飞, 周丽华, 杜国王, 黄皓, 黄通. 基于聚类的超链路预测[J]. 计算机应用, 2020, 40(2): 434-440.
[9]	吕亚丽, 苗钧重, 胡玮昕. 基于标签进行度量学习的图半监督学习算法[J]. 计算机应用, 2020, 40(12): 3430-3436.
[10]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[11]	沈学利, 李子健, 赫辰皓. 基于评分填充与信任信息的混合推荐算法[J]. 计算机应用, 2020, 40(10): 2789-2794.
[12]	刘颖, 梁楠楠, 李大湘, 杨凡超. 基于光谱距离聚类的高光谱图像解混算法[J]. 计算机应用, 2019, 39(9): 2541-2546.
[13]	陈善学, 储成泉. 基于稀疏和正交约束非负矩阵分解的高光谱解混[J]. 计算机应用, 2019, 39(8): 2276-2280.
[14]	王文涛, 吴淋涛, 黄烨, 朱容波. 基于密集连接卷积神经网络的链路预测模型[J]. 计算机应用, 2019, 39(6): 1632-1638.
[15]	邵长城, 陈平华. 融合社交网络和图像内容的兴趣点推荐[J]. 计算机应用, 2019, 39(5): 1261-1268.