融合拓扑和属性的动态网络链路预测方法

doi:10.3778/j.issn.1002-8331.2109-0310

摘要/Abstract

摘要： 网络数据中出现的大量节点属性和随时间变化的特征，给链路预测提出了新挑战。基于注意力机制和循环神经网络对随时间演化网络进行建模，提出了DTA-LP模型。与传统的静态链路预测算法相比，DTA-LP使用LSTM捕获时序信息，动态预测可以更好应用于现实网络；与基于网络拓扑的动态链路预测算法相比，DTA-LP可以聚集高阶拓扑特征，有效挖掘网络邻域信息；与基于属性网络的动态链路预测算法相比，DTA-LP可以加权融合网络拓扑属性，提高预测精度。在4种真实数据上的实验结果表明，该方法能结合网络已有先验知识，以较高的MAP值来预测未来网络中的边，验证了模型的有效性。

关键词: 链路预测, 动态图, 属性融合, 注意力机制, 节点嵌入

Abstract: A large number of node attributes and temporal features in network data provide new challenges for the link prediction. On the basis of the attention mechanism and recurrent neural network, this paper analyses the evolution network over time and proposes a DTA-LP model for the computer simulation of this network. Compared with the traditional static link prediction algorithm, DTA-LP uses LSTM to capture temporal information, the dynamic prediction can be better applied to real networks. Unlike the dynamic link prediction algorithm based on the network topology, DTA-LP can gather high-order topology features and effectively obtain network domain information. Different from the dynamic link prediction algorithm based on attribute networks, DTA-LP can weight and fuse network topology and attributes to improve the prediction accuracy. The experimental results on four kinds of real data show that DTA-LP can combine the prior knowledge of the network to predict the middle edge of the future network with a high MAP value, which verifies the effectiveness of the model.

Key words: link prediction, dynamic network, attribute fusion, attention mechanism, node embedding

罗世杰, 吕文韬, 李凡, 崔家熙, 相洁. 融合拓扑和属性的动态网络链路预测方法[J]. 计算机工程与应用, 2023, 59(5): 122-130.

LUO Shijie, LYU Wentao, LI Fan, CUI Jiaxi, XIANG Jie. Dynamic Network Link Prediction Method for Fusion Topology and Attributes[J]. Computer Engineering and Applications, 2023, 59(5): 122-130.

参考文献

[1] JIANG J，LIU L P，HASSOUN S.Learning graph representations of biochemical networks and its application to enzymatic link prediction[J].Bioinformatics，2021，37（6）：793-799.
[2] LIBEN‐NOWELL D，KLEINBERG J.The link‐prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2007，58（7）：1019-1031.
[3] GREIBE P.Accident prediction models for urban roads[J].Accident Analysis & Prevention，2003，35（2）：273-285.
[4] AIELLO L M，BARRAT A，SCHIFANELLA R，et al.Friendship prediction and homophily in social media[J].ACM Transactions on the Web，2012，6（2）：1-33.
[5] KUMAR A，SINGH S S，SINGH K，et al.Link prediction techniques，applications，and performance：a survey[J].Physica A：Statistical Mechanics and Its Applications，2020，553：124289.
[6] 张月霞，冯译萱.链路预测的方法与发展综述[J].测控技术，2019，38（2）：8-12.
ZHANG Y X，FENG Y X.A summary of the methods and development of link prediction[J].Measurement & Control Technology，2019，38（2）：8-12.
[7] 李艳丽，周涛.链路预测中的局部相似性指标[J].电子科技大学学报，2021，50（3）：422-427.
LI Y L，ZHOU T.Local similarity indices in link prediction[J].Journal of University of Electronic Science and Technology of China，2021，50（3）：422-427.
[8] 吕琳媛.复杂网络链路预测[J].电子科技大学学报，2010，39（5）：651-661.
LV L Y.Link prediction on complex networks[J].Journal of University of Electronic Science and Technology of China，2010，39（5）：651-661.
[9] 蔡菲，张鑫，牟晓慧，等.深度非负矩阵分解的链路预测方法研究[J].计算机工程与应用，2020，56（15）：153-161.
CAI F，ZHANG X，MU X H，et al.Research on link prediction method based on deep non-negative matrix factorization[J].Computer Engineering and Applications，2020，56（15）：153-161.
[10] 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，2014：701-710.
[11] 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，2016：855-864.
[12] KIPF T N，WELLING M.Variational graph auto-encoders[J].arXiv：1611.07308，2016.
[13] DIVAKARAN A，MOHAN A.Temporal link prediction：a survey[J].New Generation Computing，2019：1-46.
[14] BOGAERTS T，MASEGOSA A D，ANGARITA-ZAPATA J S，et al.A graph CNN-LSTM neural network for short and long-term traffic forecasting based on trajectory data[J].Transportation Research Part C：Emerging Technologies，2020，112：62-77.
[15] 卢志刚，陈倩.动态供应链网络中企业合作关系的链路预测[J].计算机工程与应用，2022，58（2）：265-273.
LU Z G，CHEN Q.Link prediction of enterprise cooperation relationship in dynamic supply chain network[J].Computer Engineering and Applications，2022，58（2）：265-273.
[16] GOYAL P，KAMRA N，HE X，et al.Dyngem：deep embedding method for dynamic graphs[J].arXiv：1805. 11273，2018.
[17] GOYAL P，CH HETRI S R，CANEDO A.Dyngraph2vec：capturing network dynamics using dynamic graph representation learning[J].Knowledge-Based Systems，2020，187：104816.
[18] MO X，PANG J，LIU Z.THS-GWNN：a deep learning framework for temporal network link prediction[J].Frontiers of Computer Science，2022，16（2）：162304.
[19] GONG M，JI S，XIE Y，et al.Exploring temporal information for dynamic network embedding[J].IEEE Transactions on Knowledge and Data Engineering，2022，34（8）：3754-3764.
[20] SANKAR A，WU Y，GOU L，et al.DYSAT：deep neural representation learning on dynamic graphs via self-attention networks[C]//Proceedings of the 13th International Conference on Web Search and Data Mining，2020：519-527.
[21] PAREJA A，DOMENICONI G，CHEN J，et al.EvolveGCN：evolving graph convolutional networks for dynamic graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2020，34（4）：5363-5370.
[22] LI J，CHENG K，WU L，et al.Streaming link prediction on dynamic attributed networks[C]//Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining，2018：369-377.
[23] MENG Z，LIANG S，ZHANG X，et al.Jointly learning representations of nodes and attributes for attributed networks[J].ACM Transactions on Information Systems，2020，38（2）：1-32.
[24] CAO S，LU W，XU Q.Deep neural networks for learning graph representations[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2016.
[25] 符汉杰，熊赟，朱扬勇.TLP：一个动态网络中的时序链路预测算法[J].计算机工程，2020，46（1）：67-73.
FU H J，XIONG Y，ZHU Y Y.TLP：a temporal link prediction algorithm in dynamic network[J].Computer Engineering，2020，46（1）：67-73.
[26] XU D，CHENG W，LUO D，et al.Adaptive neural network for node classification in dynamic networks[C]//2019 IEEE International Conference on Data Mining（ICDM），2019：1402-1407.
[27] WANG F，TAX D M J.Survey on the attention based RNN model and its applications in computer vision[J].arXiv：1601.06823，2016.
[28] 齐方鹏，王童，周明洋，等.基于互信息的动态网络链路预测算法研究[J].中国科学技术大学学报，2018，48（6）：440-446.
QI F P，WANG T，ZHOU M Y，et al.Link prediction in dynamical networks based onmutual information[J].Journal of University of Science and Technology of China，2018，48（6）：440-446.
[29] 袁立宁，李欣，王晓冬，等.图嵌入模型综述[J].计算机科学与探索，2022，16（1）：59-87.
YUAN L N，LI X，WANG X D，et al.Graph embedding models：a survey[J].Journal of Frontiers of Computer Science and Technology，2022，16（1）：59-87.
[30] WANG D，CUI P，ZHU W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2016：1225-1234.