-
链接预测问题是复杂网络分析领域的重要问题. 现有链接预测方法大多针对静态网络, 忽视了动态信息在网络中的传播. 为此, 针对动态网络中的链接预测问题, 本文提出了一种(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@ kindicators 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] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] -
输入: 新增链接$ {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 数据集 节点数 边数 时间/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 项目 设置 数量 操作系统 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 方法 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 -
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40]
计量
- 文章访问数:7550
- PDF下载量:139
- 被引次数:0