融合节点标签与强弱关系的链路预测算法

doi:10.3778/j.issn.1002-8331.2204-0004

摘要/Abstract

摘要： 如何通过已知路径结合相关属性信息和不同关系强度进行链路预测是一个难题。为了解决这个问题，提出融合节点标签与强弱关系的链路预测算法。选取两个中心节点，采用基于双半径节点标签算法计算以其为中心的所有网络节点标签；生成中心节点带有节点标签的[h]深度局部子图；提取局部子图并将其作为目标网络获得特征矩阵，在对特征矩阵进行矩阵分解的同时融入节点属性信息与强弱关系，赋予动态权值，构建相似度矩阵。实验结果表明，与常见的基于共同邻居算法、基于网络嵌入等链路预测算法相比，该算法的精确度最高提升1.83％，且其预测结果的精确度和效率明显提升，同时能够有效且准确地挖掘各节点的内部相关性。

关键词: 链路预测, 双半径节点标签, 矩阵分解, 相似度

Abstract: It is a difficult problem how to make link prediction through known paths combined with relevant attribute information and different relationship strengths. To solve this problem, a link prediction algorithm that fuses node labels and strong and weak relationships is proposed. Two central nodes are selected, and all network node labels centered on them are calculated by the algorithm based on the double radius node label. The [h]-depth local sub-graph with the node label of the central node is generated. the local sub-graph is extracted and used as the target network. The feature matrix is obtained, and then the feature matrix is matrix decomposing into the node attribute information and the strong and weak relationship, and dynamic weights are assigned to construct the similarity matrix. The experimental results show that compared with the common link prediction algorithms based on common neighbor algorithm and network embedding, the accuracy of this algorithm is improved by up to 1.83%, and the accuracy and efficiency of its prediction results are significantly improved. At the same time, it can be effectively and accurately mined the internal correlation of each node.

Key words: link prediction, double radius node label, matrix decomposing, similarity

王曙燕, 巩婧怡. 融合节点标签与强弱关系的链路预测算法[J]. 计算机工程与应用, 2022, 58(18): 71-77.

WANG Shuyan, GONG Jingyi. Link Prediction Algorithm Fusing Node Label and Strength Relationship[J]. Computer Engineering and Applications, 2022, 58(18): 71-77.

参考文献

[1] WANG K，LI X，LAN J L，et al.A new link prediction method for complex networks based on topological effectiveness of resource transmission paths[J].Journal of Electronics & Information Technology，2020，42（3）：653-660.
[2] 初晓宇，高守玮.基于优先连接和用户属性的链路预测算法研究[J].计算机技术与发展，2019，29（11）：17-20.
CHU X Y，GAO S W.Research on link prediction algorithm based on priority connection and user attributes[J].Computer Technology and Development，2019，29（11）：17-20.
[3] 张月霞，冯译萱.链路预测的方法与发展综述[J].测控技术，2019，38（2）：8-12.
ZHANG Y X，FENG Y X.Overview of link prediction methods and development[J].Measurement & Control Technology，2019，38（2）：8-12.
[4] 曹蓉，赵海兴，冶忠林.基于网络节点文本增强的链路预测算法[J].计算机应用与软件，2019，36（3）：227-235.
CAO R，ZHAO H X，YE Z L.Link prediction algorithm based on network node text enhancement[J].Computer Applications and Software，2019，36（3）：227-235.
[5] LIBEN-NOWELL D，KLEINBERG J.The link prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2003，58（7）：1019-1031.
[6] 吕琳媛.复杂网络链路预测[J].电子科技大学学报，2010，9（5）：651-661.
LU L Y.Complex network link prediction[J].Journal of University of Electronic Science and Technology of China，2010，9（5）：651-661.
[7] 王智强，梁吉业，李茹.基于信息融合的概率矩阵分解链路预测方法[J].计算机研究与发展，2019，56（2）：306-318.
WANG Z Q，LIANG J Y，LI R.Probabilistic matrix decomposition link prediction method based on information fusion[J].Journal of Computer Research and Development，2019，56（2）：306-318.
[8] ABUODA G，MORALES G D F，ABOULNAGA A.Link prediction via higher-order motif features[J].arXiv：1902.
06679，2019.
[9] ZHAO H，DU L，BUNTINE W.Leveraging node attributes for incomplete relational data[C]//International Conference on Machine Learning，Sydney，Aug 6-11，2017.New York：ACM，2017：4072-4081.
[10] DAI H，DAI B，SONG L.Discriminative embeddings of latent variable models for structured data[C]//International Conference on Machine Learning，New York，Jun 19-24，2016.New York：ACM，2016：2702-2711.
[11] FENG Y，HU B，LV F，et al.Atbrg：adaptive target-behavior relational graph network for effective recommendation[C]//Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval，Xi’an，Jul 25-30，2020.New York：ACM，2020：2231-2240.
[12] GROVER A，LESKOVEC J.Node2vec：scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，San Francisco，Aug 13-17，2016.New York：ACM，2016：855-864.
[13] BRIN S，PAGE L.Reprint of：the anatomy of a large-scale hypertextual web search engine[J].Computer Networks，2012，56（18）：3825-3833.
[14] Lü L，ZHOU T.Link prediction in complex networks：a survey[J].Physica A：Statistical Mechanics and Its Applications，2011，390（6）：1150-1170.
[15] LORRAIN F，WHITE H C.Structure equivalence of individuals in social networks[J].The Journal of Mathematical Sociology，1971，1（1）：49-80.
[16] NAUN C C.Book review：introduction to modern information retrieval[J].Library Resources & Technical Services，2011，55（4）：239-240.
[17] JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin of the Torrey Botanical Club，1901，37（142）：547-579.
[18] LU L，JIN C H，ZHOU T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E，2009，80（4）：046122.
[19] KATZ L.A new status index derived from sociometric index[J].Psychometrika，1953，18（1）：39-43.
[20] LEICHT E A，HOLME P，NEWMAN M E J.Vertex similarity in networks[J].Physical Review E，2006，73（2）：026120.
[21] KOVáCS I A，LUCK K，SPIROHN K，et al.Network-based prediction of protein interactions[J].Nature Communications，2019，10（1）：1-8.
[22] MIKOLOV T，SUTSKEVER I，CHEN K，et al.Distributed representations of words and phrases and their compositionality[C]//Proceedings of the Advances in Neural Information Processing Systems，Lake Tahoe，Dec 5-10，2013.La Jolla：NIPS，2013：3111-3119.
[23] PEROZZI B，AL-RFOU R，SKIENA S.Deepwalk：online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，Aug 24-27，2014.New York：ACM，2014：701-710.
[24] 张学佩.基于3D卷积神经网络的多节点间链路预测方法研究[D].南昌：南昌航空大学，2018.
ZHANG X P.Research on multi-node link prediction method based on 3D convolutional neural network[D].Nanchang：Nanchang Aviation University，2018.
[25] 顾秋阳，吴宝，池仁勇.基于高阶路径相似度的复杂网络链路预测方法[J].通信学报，2021，42（7）：61-69.
GU Q Y，WU B，CHI R Y.Link prediction method of complex network based on high-order path similarity[J].Journal on Communications，2021，42（7）：61-69.
[26] 刘树新，李星，陈鸿昶，等.基于资源传输匹配度的复杂网络链路预测方法[J].通信学报，2020，41（6）：70-79.
LIU S X，LI X，CHEN H C，et al.Complex network link prediction method based on resource transmission matching degree[J].Journal on Communications，2020，41（6）：70-79.
[27] FAN W，MA Y，LI Q，et al.Graph neural networks for social recommendation[C]//The World Wide Web Conference，San Francisco，May 13-17，2019.Germany：Springer，2019：417-426.
[28] YANG P，SHAO K，HUO X，et al.Social recommendation algorithm incorporating users’ implicit preferences[J].Journal of Chinese Computer Systems，2019，40（10）：2039-2045.
[29] ZHANG M，CHEN Y.Link prediction based on graph neural networks[J].Advances in Neural Information Processing Systems，2018，31：5165-5175.
[30] YANG S，HU B，ZHANG Z，et al.Inductive link prediction with interactive structure learning on attributed graph[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases，Bilbao，Sep 13-17，2021.Germany：Springer，2021：383-398.
[31] YANG C，LIU Z Y，ZHAO D L，et al.Network representation learning with rich text information[C]//Proceedings of the 2015 International Conference on Artificial Intelligence，Buenos Aires，Oct 28-30，2015.Germany：Springer，2015：2111-2117.
[32] MARSDEN P V，FRIEDKIN N E.Network studies of social influence[J].Sociological Methods & Research，1993，22（1）：127-151.
[33] MCPHERSON M，SMITH-LOVIN L，COOK J M.Birds of a feather：homophily in social networks[J].Annual Review of Sociology，2001，27（1）：415-444.