-
链接预测问题是复杂网络分析领域的重要问题. 现有链接预测方法大多针对静态网络, 忽视了动态信息在网络中的传播. 为此, 针对动态网络中的链接预测问题, 本文提出了一种基于动态网络表示的链接预测(dynamic network representation based link prediction, DNRLP)模型. 该模型对网络中不均匀的动态信息进行了学习, 提出了基于连接强度的随机游走算法来模拟动态信息在网络中的扩散, 从而得到新时刻下的节点表示, 然后通过度量节点表示之间的相似度进行链接预测. 实验使用平均交互排序(mean reciprocal rank, MRR)和召回率(Recall@k)指标在四个公开动态网络数据集上进行实验, 结果显示DNRLP模型的MRR指标较对比模型平均提高了30.8%. 实验结果表明DNRLP模型不仅学习了网络中的动态信息, 还考虑了其对邻居节点的影响以及时间间隔对信息更新的影响, 得到了更为丰富的节点表示, 对于链接预测任务具有明显优势.Link prediction is an important issue in network analysis tasks, which aims at detecting missing, spurious or evolving links in a network, based on the topology information of the network and/or the attributes of the nodes. It has been applied to many real-world applications, such as information integration, social network analysis, recommendation systems, and bioinformatics. Existing link prediction methods focus on static networks and ignore the transmission of dynamic information in the network. However, many graphs in practical applications are dynamic and evolve constantly over time. How to capture time information in a dynamic network and improve the accuracy of link prediction remains a conspicuous challenge. To tackle these challenges, we propose a dynamic network representation based link prediction model, named DNRLP. DNRLP can be mainly divided into two modules: a representation learning module on dynamic network and a link prediction module, where the representation learning module is composed of a node information dynamic update unit and a node neighborhood update unit. Node information dynamic update unit leverages the benefits of the long short-term memory (LSTM) in capturing time information and uses a Time Interval based Filter Unit (TIFU) to introduce time interval information between two links, while for the node neighborhood update unit we present a random walk algorithm based on connection strength to simulate the diffusion of dynamic information. Through the above two parts, the model can obtain the node representation at the new moment, then link prediction is performed by the link prediction module by measuring the similarity between the node representations. The experiment uses MRR and Recall@k indicators to evaluate performance of model on four public dynamic network datasets. The experiments demonstrate the effectiveness and the credibility of the proposed model in link prediction tasks as compared with the comparison models, the MNR index of the DNRLP is increased by 30.8%. The model proposed in this paper not only learns the dynamic information in the network, but also considers its influence on neighbors and the impact of time interval on information update. Therefore, the model has learned more abundant dynamic information and has obvious advantages for link prediction tasks.
-
Keywords:
- link prediction /
- dynamic network /
- representation learning /
- random walk
[1] Borgatti S P, Mehra A, Brass D J, Labianca G 2009 Science 323 892
Google Scholar
[2] Senator T E 2005 SIGKDD Explor. Newsl. 7 76
Google Scholar
[3] Newman M E 2001 Physical review E 64 025102
Google Scholar
[4] Adamic L A, Adar E 2003 Social Networks 25 211
Google Scholar
[5] Fouss F, Pirotte A, Renders J M, Saerens M 2007 IEEE Transactions on Knowledge and Data Engineering 19 355
Google Scholar
[6] Al Hasan M, Zaki M J 2011 Social Network Data Analytics (Boston: Springer) p243
[7] Burges C J 1998 Data Mining and Knowledge Discovery 2 121
Google Scholar
[8] Freno A, Garriga G, Keller M 2011 Proceedings of the 25th Neural Information Processing Systems Workshop on Choice Models and Preference Learning Granada, Spain, December 12−17, 2011 p1
[9] Hoseini E, Hashemi S, Hamzeh A 2012 Proceedings of the 26th International Conference on Advanced Information Networking and Applications Workshops Fukuoka, Japan, March 26−29, 2012 p795
[10] Xu Z, Pu C, Sharafat R R, Li L, Yang J 2017 Chin. Phys. B 26 018902
Google Scholar
[11] Lai D R, Shu X, Nardini C 2017 Chin. Phys. B 26 038902
Google Scholar
[12] Kovacs I A, Luck K, Spirohn K, Wang Y, Pollis C, Schlabach S, Bian W T, Kim D K, Kishore N, Hao T, Calderwood M A, Vidal M, Barabasi A L 2019 Nat. Commun. 10 1240
Google Scholar
[13] Pech R, Hao D, Lee Y L, Yuan Y, Zhou T 2019 Physica A: Statistical Mechanics and its Applications 528 121319
Google Scholar
[14] Zhang M H, Chen Y X 2018 Proceedings of the 32nd Advances in Neural Information Processing Systems Montreal, Canada, December 2−8, 2018 p5165
[15] Scarselli F, Gori M, Tsoi A C, Hagenbuchner M, Monfardini G 2008 IEEE Transactions on Neural Networks 20 61
Google Scholar
[16] Ostapuk N, Yang J, Cudré-Mauroux P 2019 Proceedings of the 28th The World Wide Web Conference San Francisco, American, MAY 13−17, 2019 p1398
[17] Gal Y, Islam R, Ghahramani Z 2017 Proceedings of the 34th International Conference on Machine Learning Sydney, Australia, August 6−11, 2017 p1183
[18] Gal Y, Ghahramani Z 2016 Proceedings of the 33rd International Conference on Machine Learning New York, American, June 19-24, 2016 p1050
[19] Finn C, Abbeel P, Levine S 2017 Proceedings of the 34th International Conference on Machine Learning Sydney, Australia, August 6−11, 2017 p1126
[20] Cui P, Wang X, Pei J, Zhu W W 2018 IEEE Transactions on Knowledge and Data Engineering 31 833
Google Scholar
[21] Perozzi B, Al-Rfou R, Skiena S 2014 Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining New York, American, August 24−27, 2014 p701
[22] Tang J, Qu M, Wang M Z, Zhang M, Yan J, Mei Q Z 2015 Proceedings of the 24th international conference on world wide web Florence, Italy, May 18−22, 2015 p1067
[23] Grover A, Leskovec J 2016 Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, American, August 13−17, 2016 p855
[24] Wang D X, Cui P, Zhu W W 2016 Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, American, August 13−17, 2016 p1225
[25] Kipf T N, Welling M 2016 arXiv: 1609.02907 [cs.LG]
[26] Will H, Ying Z T, Jure L 2017 Proceedings of the 31st Conference and Workshop on Neural Information Processing Systems Long Beach, American, December 4−10, 2017 p1024
[27] Schaub M T, Delvenne J-C, Lambiotte R, Barahona M 2019 Physical Review E 99 062308
Google Scholar
[28] Srijan Kumar, Zhang X K , Jure Leskovec 2018 arXiv: 1812.02289 [cs.SI]
[29] 李志宇, 梁循, 徐志明, 齐金山, 陈燕方 2017 计算机学报 40 805
Google Scholar
LI Z Y, Liang X, Xu Z M, Qi J S, Chen Y F 2017 Chinese Journal of Computers 40 805
Google Scholar
[30] Goyal P, Kamra N, He X R, Liu Y 2018 arXiv: 1805.11273 [cs.SI]
[31] Chen J Y, Zhang J, Xu X H, Fu C B, Zhang D, Zhang Q P, Xuan Q 2019 IEEE T SYST MAN CY-S1 49 1
[32] Hochreiter S, Schmidhuber J 1997 Neural computation 9 1735
Google Scholar
[33] Li T S, Zhang J W, Yu P S, Zhang Y, Yan Y H 2018 IEEE Access 6 29219
Google Scholar
[34] Dey R, Salemt F M 2017 Proceedings of the 60th International Midwest Symposium on Circuits and Systems (MWSCAS) Boston, American, August 6−9, 2017 p1597
[35] Lei K, Qin M, Bai B, Zhang G, Yang M 2019 Proceedings of the IEEE INFOCOM 2019-IEEE Conference on Computer Communications Paris, France, April 29−May 2, 2019 p388
[36] Goodfellow I J, Pouget-Abadie J, Mirza M, Bing X, Warde-Farley D, Ozair S, Courville A, Bengio Y 2014 Proceedings of the 28th Conference on Neural Information Processing Systems Montreal, Canada, December 8−13, 2014 p2672
[37] Chang S Y, Zhang Y, Tang J L, Yin D W, Chang Y, Hasegawa-Johnson M A, Huang T S 2017 Proceedings of the 26th International Conference on World Wide Web Perth, Australia, April 3−7, 2017 p381
[38] Opsahl T, Panzarasa P 2009 Social Networks 31 155
Google Scholar
[39] Sun J, Kunegis J, Staab S 2016 Proceedings of the 16th International Conference on Data Mining Workshops Barcelona, Spain, December 12−15, 2016 p128
[40] Klimt B, Yang Y M 2004 Proceedings of the 15th European Conference on Machine Learning Pisa, Italy, September 20−24, 2004 p3201
-
图 2 基于动态网络表示的链接预测模型结构
Fig. 2. The architecture of link prediction model based on dynamic network representation.
图 6 各数据集上的
$ Recall@k $ 对比图 (a) UCI数据集; (b) DNC数据集; (b) Wikipedia数据集; (d) Enron数据集Fig. 6.
$ Recall@k $ comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset
图 7 各数据集上的
$ Precision@k $ 对比图 (a) UCI数据集; (b) DNC数据集; (b) Wikipedia数据集; (d) Enron数据集Fig. 7.
$ Precision@k $ comparison diagram on each data set. (a) UCI dataset; (b) DNC dataset; (b) Wikipedia dataset; (d) Enron dataset
图 8 DNRLP模型变体的Recall@k对比图 (a) UCI数据集; (b) DNC数据集; (c) Wikipedia数据集; (d) Enron数据集
Fig. 8. Recall@k comparison diagram of the variants of DNRLP. (a) UCI dataset; (b) DNC dataset; (c) Wikipedia dataset; (d) Enron dataset.
图 9 不同训练率的MRR结果对比图 (a) DNC数据集; (b) Enron数据集
Fig. 9. MRR results of different training rates. (a) DNC dataset; (b) Enron dataset
表 1 信息扩散算法
Table 1. Information diffusion algorithm.
输入: 新增链接$ {e}_{ij}\in {E}_{{\rm{new}}} $, 随机游走长度$ L $ 输出: 随机游走序列$ R $ 1) For $ {e}_{ij} $ in $ {E}_{{\rm{new}}} $ do: 2) For $ v $ in $ {e}_{ij} $ do: 3) $ m=\mathrm{ }0 $ 4) While $ m < L $ do 5) 初始化权重分布$ P $ 6) For $ u $ in $ {N}_{v} $ do 7) 根据(13)式计算$ {f}_{\rm{s}}\left({u}_{\rm{u}}, {u}_{v}\right) $, 加入$ P $ 8) End for 9) 根据$ P $选择下一个节点$u^\prime$加入${R}_{v}$ 10) $ m=m+1 $ 11) $ v=u' $ 12) End while 13) 将$ {R}_{v} $加入$ R $ 14) End for 15) End for 
下载: 导出CSV
表 2 动态网络数据详细信息
Table 2. Dynamic network data details.
数据集 节点数 边数 时间/d 聚类系数/% UCI 1899 59835 194 5.68 DNC 2029 39264 982 8.90 Wikipedia 1219241 2284546 4763 0.000837 Enron 384413 1751463 1140 4.96
下载: 导出CSV
表 3 实验环境设置信息
Table 3. Experimental environment setup information.
项目 设置 数量 操作系统 Ubuntu 16.04 1 CPU Intel®i7-5280K, 6 核, 12线程 1 硬盘 512GB PLEXTOR®PX-512M6Pro SSD 1 内存 Kingston®8GB DDR4 2400 8 重要程序包 Python 3.7 1 深度学习
框架PyTorch 1
下载: 导出CSV
表 4 链接预测MRR结果对比
Table 4. Link prediction MRR results comparison.
方法 UCI DNC Wikipedia Enron Logistic Regression 0.005 1 0.020 9 0.003 7 0.005 2 SVM 0.003 2 0.018 2 0.002 1 0.002 9 Node2Vec 0.004 7 0.019 7 0.003 5 0.003 9 GCN 0.015 9 0.048 4 0.010 1 0.017 6 GraphSAGE 0.016 3 0.049 7 0.012 0 0.018 3 DynGEM 0.015 7 0.028 4 0.010 8 0.014 7 GCN-GAN 0.020 1 0.050 4 0.014 9 0.021 5 DDNE 0.014 2 0.026 8 0.009 6 0.011 6 DNRLP 0.035 1 0.053 9 0.018 7 0.036 3
下载: 导出CSV
-
[1] Borgatti S P, Mehra A, Brass D J, Labianca G 2009 Science 323 892
Google Scholar
[2] Senator T E 2005 SIGKDD Explor. Newsl. 7 76
Google Scholar
[3] Newman M E 2001 Physical review E 64 025102
Google Scholar
[4] Adamic L A, Adar E 2003 Social Networks 25 211
Google Scholar
[5] Fouss F, Pirotte A, Renders J M, Saerens M 2007 IEEE Transactions on Knowledge and Data Engineering 19 355
Google Scholar
[6] Al Hasan M, Zaki M J 2011 Social Network Data Analytics (Boston: Springer) p243
[7] Burges C J 1998 Data Mining and Knowledge Discovery 2 121
Google Scholar
[8] Freno A, Garriga G, Keller M 2011 Proceedings of the 25th Neural Information Processing Systems Workshop on Choice Models and Preference Learning Granada, Spain, December 12−17, 2011 p1
[9] Hoseini E, Hashemi S, Hamzeh A 2012 Proceedings of the 26th International Conference on Advanced Information Networking and Applications Workshops Fukuoka, Japan, March 26−29, 2012 p795
[10] Xu Z, Pu C, Sharafat R R, Li L, Yang J 2017 Chin. Phys. B 26 018902
Google Scholar
[11] Lai D R, Shu X, Nardini C 2017 Chin. Phys. B 26 038902
Google Scholar
[12] Kovacs I A, Luck K, Spirohn K, Wang Y, Pollis C, Schlabach S, Bian W T, Kim D K, Kishore N, Hao T, Calderwood M A, Vidal M, Barabasi A L 2019 Nat. Commun. 10 1240
Google Scholar
[13] Pech R, Hao D, Lee Y L, Yuan Y, Zhou T 2019 Physica A: Statistical Mechanics and its Applications 528 121319
Google Scholar
[14] Zhang M H, Chen Y X 2018 Proceedings of the 32nd Advances in Neural Information Processing Systems Montreal, Canada, December 2−8, 2018 p5165
[15] Scarselli F, Gori M, Tsoi A C, Hagenbuchner M, Monfardini G 2008 IEEE Transactions on Neural Networks 20 61
Google Scholar
[16] Ostapuk N, Yang J, Cudré-Mauroux P 2019 Proceedings of the 28th The World Wide Web Conference San Francisco, American, MAY 13−17, 2019 p1398
[17] Gal Y, Islam R, Ghahramani Z 2017 Proceedings of the 34th International Conference on Machine Learning Sydney, Australia, August 6−11, 2017 p1183
[18] Gal Y, Ghahramani Z 2016 Proceedings of the 33rd International Conference on Machine Learning New York, American, June 19-24, 2016 p1050
[19] Finn C, Abbeel P, Levine S 2017 Proceedings of the 34th International Conference on Machine Learning Sydney, Australia, August 6−11, 2017 p1126
[20] Cui P, Wang X, Pei J, Zhu W W 2018 IEEE Transactions on Knowledge and Data Engineering 31 833
Google Scholar
[21] Perozzi B, Al-Rfou R, Skiena S 2014 Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining New York, American, August 24−27, 2014 p701
[22] Tang J, Qu M, Wang M Z, Zhang M, Yan J, Mei Q Z 2015 Proceedings of the 24th international conference on world wide web Florence, Italy, May 18−22, 2015 p1067
[23] Grover A, Leskovec J 2016 Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, American, August 13−17, 2016 p855
[24] Wang D X, Cui P, Zhu W W 2016 Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining San Francisco, American, August 13−17, 2016 p1225
[25] Kipf T N, Welling M 2016 arXiv: 1609.02907 [cs.LG]
[26] Will H, Ying Z T, Jure L 2017 Proceedings of the 31st Conference and Workshop on Neural Information Processing Systems Long Beach, American, December 4−10, 2017 p1024
[27] Schaub M T, Delvenne J-C, Lambiotte R, Barahona M 2019 Physical Review E 99 062308
Google Scholar
[28] Srijan Kumar, Zhang X K , Jure Leskovec 2018 arXiv: 1812.02289 [cs.SI]
[29] 李志宇, 梁循, 徐志明, 齐金山, 陈燕方 2017 计算机学报 40 805
Google Scholar
LI Z Y, Liang X, Xu Z M, Qi J S, Chen Y F 2017 Chinese Journal of Computers 40 805
Google Scholar
[30] Goyal P, Kamra N, He X R, Liu Y 2018 arXiv: 1805.11273 [cs.SI]
[31] Chen J Y, Zhang J, Xu X H, Fu C B, Zhang D, Zhang Q P, Xuan Q 2019 IEEE T SYST MAN CY-S1 49 1
[32] Hochreiter S, Schmidhuber J 1997 Neural computation 9 1735
Google Scholar
[33] Li T S, Zhang J W, Yu P S, Zhang Y, Yan Y H 2018 IEEE Access 6 29219
Google Scholar
[34] Dey R, Salemt F M 2017 Proceedings of the 60th International Midwest Symposium on Circuits and Systems (MWSCAS) Boston, American, August 6−9, 2017 p1597
[35] Lei K, Qin M, Bai B, Zhang G, Yang M 2019 Proceedings of the IEEE INFOCOM 2019-IEEE Conference on Computer Communications Paris, France, April 29−May 2, 2019 p388
[36] Goodfellow I J, Pouget-Abadie J, Mirza M, Bing X, Warde-Farley D, Ozair S, Courville A, Bengio Y 2014 Proceedings of the 28th Conference on Neural Information Processing Systems Montreal, Canada, December 8−13, 2014 p2672
[37] Chang S Y, Zhang Y, Tang J L, Yin D W, Chang Y, Hasegawa-Johnson M A, Huang T S 2017 Proceedings of the 26th International Conference on World Wide Web Perth, Australia, April 3−7, 2017 p381
[38] Opsahl T, Panzarasa P 2009 Social Networks 31 155
Google Scholar
[39] Sun J, Kunegis J, Staab S 2016 Proceedings of the 16th International Conference on Data Mining Workshops Barcelona, Spain, December 12−15, 2016 p128
[40] Klimt B, Yang Y M 2004 Proceedings of the 15th European Conference on Machine Learning Pisa, Italy, September 20−24, 2004 p3201
下载:
计量
- 文章访问数: 8192
- PDF下载量: 142
- 被引次数: 0
