TLP:一个动态网络中的时序链路预测算法

doi:10.19678/j.issn.1000-3428.0053797

计算机工程 ›› 2020, Vol. 46 ›› Issue (1): 67-73. doi: 10.19678/j.issn.1000-3428.0053797

TLP:一个动态网络中的时序链路预测算法

符汉杰^1,2,3, 熊赟^1,2,3, 朱扬勇^1,2,3

1. 复旦大学计算机科学技术学院, 上海 200433;
2. 上海市数据科学重点实验室, 上海 200433;
3. 上海先进通信与数据科学研究院, 上海 200433

收稿日期:2019-01-24 修回日期:2019-03-18 出版日期:2020-01-15 发布日期:2019-03-22
作者简介:符汉杰(1993-),男,硕士研究生,主研方向为动态网络分析、大数据挖掘;熊赟、朱扬勇,教授、博士生导师。
基金资助:
国家自然科学基金（U1636207，91546105）；上海市科委发展基金（16JC1400801，17511105502）；苏州市科技局民生科技示范工程项目（SS201712，SS201812）。

TLP: A Temporal Link Prediction Algorithm in Dynamic Network

FU Hanjie^1,2,3, XIONG Yun^1,2,3, ZHU Yangyong^1,2,3

1. School of Computer Science, Fudan University, Shanghai 200433, China;
2. Shanghai Key Laboratory of Data Science, Shanghai 200433, China;
3. Shanghai Institute for Advanced Communication and Data Science, Shanghai 200433, China

Received:2019-01-24 Revised:2019-03-18 Online:2020-01-15 Published:2019-03-22

摘要/Abstract

摘要： 链路预测是网络分析的一个重要应用，网络结构在真实场景中随时间发生演变，节点间会产生新的联系或者终止连接，从而导致网络结构变化以及节点中内在的偏向发生偏移。为提升链路预测能力，提出一种基于时序特征的动态网络节点表示的链路预测算法，即每一时刻的节点表示向量由历史的表示向量计算得到，以反映节点在向量空间中的变化规律，同时结合节点间的高阶邻近特性，生成具有鲁棒性的节点向量来维护网络结构。在真实数据集上的实验结果表明，与TNE、DHPE等算法相比，该算法在链路预测任务上的预测性能具有明显提升，适用于大规模的动态网络。

关键词: 链路预测, 动态网络, 随机游走, 时序演变, 高阶邻近

Abstract: Link prediction is an important application of network analysis.In real scenarios,the network structure evolves with time,so new connections or terminations occur between nodes,resulting in changes in the network structure and deviations within the nodes.In order to improve the link prediction capability,this paper proposes a link prediction algorithm based on node representation with temporal characteristics in dynamic network.The node representation vector at each moment is obtained by calculating the historical representation vector,so as to reflect the variation patterns of nodes in the vector space.Meanwhile,by combing the high order proximity characteristics between nodes,robust node vectors are generated to preserve the network structure.Experimental results on real datasets show that compared with algorithms such as TNE and DHPE,the propose algorithm presents a good performance improvement on link prediction tasks and it can be applied to large scale dynamic networks.

Key words: link prediction, dynamic network, random walk, temporal evolution, high order proximity

中图分类号:

TP18

符汉杰, 熊赟, 朱扬勇. TLP:一个动态网络中的时序链路预测算法[J]. 计算机工程, 2020, 46(1): 67-73.

FU Hanjie, XIONG Yun, ZHU Yangyong. TLP: A Temporal Link Prediction Algorithm in Dynamic Network[J]. Computer Engineering, 2020, 46(1): 67-73.

https://www.ecice06.com/CN/Y2020/V46/I1/67

图/表 8

20200115110027

20200115110030

20200115110033

20200115110035

20200115110038

20200115110041

20200115110047

20200115110050

参考文献

[1] LIAO Lizi,HE Xiangnan,ZHANG Hanwang,et al.Attributed social network embedding[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(12):2257-2270.
[2] LI Bo,ZHENG Chunhou,HUANG Deshuang,et al.Gene expression data classification using locally linear discriminant embedding[J].Computers in Biology and Medicine,2010,40(10):802-810.
[3] 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.New York,USA:ACM Press,2016:855-864.
[4] OU Mingdogn,CUI Peng,PEI Jian,et al.Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2016:1105-1114.
[5] WANG Daixin,CUI Peng,ZHU Wenwu.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2016:1225-1234.
[6] ZHANG Li,WANG Hong,MA Xingfu.Community evolution mining in dynamic social network[J].Computer Engineering,2013,39(6):47-51.(in Chinese)臧丽,王红,马兴福.动态社会网络中的社区演变挖掘[J].计算机工程,2013,39(6):47-51.
[7] WANG Lunwen,ZHANG Ling.A method of finding the shortest path of dynamic networks[J].Journal of System Simulation,2018,30(3):1189-1194.(in Chinese)王伦文,张铃.动态网络最短程求解技术研究[J].系统仿真学报,2018,30(3):1189-1194.
[8] ZHU Linhong,GUO Dong,YIN Junming,et al.Scalable temporal latent space inference for link prediction in dynamic social networks[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(10):2765-2777.
[9] YU W,CHENG W,AGGARWAL C C,et al.Link prediction with spatial and temporal consistency in dynamic networks[C]//Proceedings of International Joint Conference on Artificial Intelligence.Washington D.C.,USA:IEEE Press,2017:3343-3349.
[10] ZHU Dingyuan,CUI Peng,ZHANG Ziwei,et al.High-order proximity preserved embedding for dynamic networks[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(11):2134-2144.
[11] 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,USA:ACM Press,2014:701-710.
[12] ZHOU Lekui,YANG Yang,REN Xiang,et al.Dynamic network embedding by modeling triadic closure process[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence.[S.1.]:AAAI Press,2018:571-578.
[13] GOYAL P,KAMRA N,HE X,et al.DynGEM:deep embedding method for dynamic graphs[EB/OL].[2018-12-10].https://www.researchgate.net/.
[14] XIAONG Yun,ZHANG YAO,FU Hanjie,et al.DynGraphGAN:dynamic graph embedding via generative adversarial networks[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin,Germany:Springer,2019:215-226.
[15] QI Fangpeng,WANG Tong,ZHOU Mingyang,et al.Link prediction in dynamical networks based on mutual information[J].Journal of University of Science and Technology of China,2018,48(6):440-446.(in Chinese)齐方鹏,王童,周明洋,等.基于互信息的动态网络链路预测算法研究[J].中国科学技术大学学报,2018,48(6):440-446.
[16] CAI Bosi,CHEN Xiang.Reseach on Weibo community discovery based on behavior similarity[J].Computer Engineering,2013,39(8):55-59.(in Chinese)蔡波斯,陈翔.基于行为相似度的微博社区发现研究[J].计算机工程,2013,39(8):55-59.
[17] VISWANATH B,MISLOVE A,CHA M,et al.On the evolution of user interaction in facebook[C]//Proceedings of the 2nd ACM Workshop on Online Social Networks.New York,USA:ACM Press,2009:37-42.
[18] MASSA P,AVESANI P.Trust-aware bootstrapping of recommender systems[C]//Proceedings of ECAI Workshop on Recommender Systems.Washington D.C.,USA:IEEE Press,2006:29-33.
[19] HOGG T,LERMAN K.Social dynamics of Digg[J].EPJ Data Science,2012,1(1):5.
[20] RANSHOUS S,SHEN S,KOUTRA D,et al.Anomaly detection in dynamic networks:a survey[J].Computational Statistics,2015,7(3):223-247.

选择文件类型/文献管理软件名称

选择包含的内容

TLP:一个动态网络中的时序链路预测算法

TLP: A Temporal Link Prediction Algorithm in Dynamic Network

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	潘乐, 李弼程, 万旺, 曾荣燊. 基于关系强度理论与反馈机制的信息传播动态网络表示[J]. 计算机工程, 2023, 49(2): 246-253.
[2]	刘宇航, 尹小庆, 林云. 基于网络资源流量的链路预测方法[J]. 计算机工程, 2022, 48(9): 78-88.
[3]	吴翼腾, 于洪涛, 顾泽宇. 基于统一描述网络结构模型的链路预测方法[J]. 计算机工程, 2022, 48(7): 51-58.
[4]	曾茜, 韩华, 马媛媛. 基于模体的朴素贝叶斯链路预测方法[J]. 计算机工程, 2022, 48(10): 95-102.
[5]	刘峰, 王宝亮, 邹荣宇, 赵浩淳. 基于随机游走的网络表示学习推荐算法[J]. 计算机工程, 2021, 47(9): 90-96,105.
[6]	黄鑫, 李赟, 熊瑾煜. 基于信息传播节点集的CTDN节点分类算法[J]. 计算机工程, 2021, 47(6): 188-196.
[7]	徐攸, 王晓萍, 熊贇. 基于角色的网络表征学习方法[J]. 计算机工程, 2021, 47(5): 52-57.
[8]	高宏屹, 张曦煌, 王杰. 生成对抗式分层网络表示学习的链路预测算法[J]. 计算机工程, 2021, 47(2): 60-68,76.
[9]	李英乐, 何赞园, 王凯, 许明艳. 基于资源传输节点拓扑紧密性的链路预测方法[J]. 计算机工程, 2021, 47(1): 50-57.
[10]	汤伟韬, 余敦辉, 魏世伟. 融合知识图谱与用户评论的商品推荐算法[J]. 计算机工程, 2020, 46(8): 93-100.
[11]	马慧芳, 李苗, 童海斌, 詹子俊. 基于通配符模式与随机游走的关键词提取方法[J]. 计算机工程, 2020, 46(7): 78-83.
[12]	陈文杰, 文奕, 张鑫, 杨宁, 赵爽. 一种改进的基于TransE知识图谱表示方法[J]. 计算机工程, 2020, 46(5): 63-69,77.
[13]	陆圣宇, 欧锋, 黄清元, 刘宝, 路振民, 汤凌韬. 基于资源分配与偏好连接的局部路径链路预测算法[J]. 计算机工程, 2019, 45(9): 316-320.
[14]	龙增艳,陈志刚,徐成林. 基于用户交互的社交网络好友推荐算法[J]. 计算机工程, 2019, 45(3): 132-137.
[15]	杨瑞琪,张月霞. 一种时序有向社会网络中的链路预测算法[J]. 计算机工程, 2019, 45(3): 197-201.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

TLP:一个动态网络中的时序链路预测算法

TLP: A Temporal Link Prediction Algorithm in Dynamic Network

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价