动态网络链接预测研究

郝宵荣，王 莉

(太原理工大学 大数据学院，太原 030600)

现实生活中的网络经常会因为新的实体和链接的加入与消失导致网络的拓扑结构和某些表达信息(例如，中心实体的改变等)不断地发生演化。在挖掘和分析演化网络的信息时，链接预测问题成为了一项非常重要的任务。动态网络链接预测任务不仅从理论方面支撑了许多领域研究，同时从实践方面还拥有广泛的应用价值。在理论上，该任务从提供动态网络建模的理论支撑和评估动态网络演化模型的优劣两方面帮助更好地理解网络底层的演化机制[1]；在应用上，研究者们针对领域需求，研究不同的动态网络链接预测方法：社会媒体网络中，通过预测不同实体之间的链接，完成推荐、营销等任务[2]；学术网络中，基于链接预测技术预测学者们之间未来是否进行学术研究合作[3]；生物关系网络中，链接预测用来研究蛋白质网络之间的相互作用，对研究各种生命特征具有重要意义[2]；知识图谱中[4]，链接预测通过获取数据中新的实体链接和关联规则等信息，进行深度知识推理，从而提高大规模运算速率。

网络数据的高维稀疏性、非线性变化等多种因素使动态网络链接预测任务变得更加复杂，但由于该任务的必要性和重要性，仍吸引了大批学者的关注。目前，大多数学者们主要基于动态网络的历史信息，推断实体之间在未来形成链接的可能性。其本质是在网络中实体数量不变的情况下，研究未来这些实体之间存在链接的概率。

动态网络链接问题可形式化描述，一个动态网络可以表示成

笔者通过分析近几年国内外动态网络链接预测相关研究工作，从所使用的技术路线的不同，主要分为以下两个方面：一种是基于时间快照的方法，将动态网络看成由多个不同的静态历史快照组成，通过对历史快照进行建模分析，进而探索未来时间片中链接的状态；另一种是基于时序感知网络，主要通过建模网络中链接的时序变化信息来预测下一时刻链接可能出现的概率。同时基于上述研究内容，提出了当前研究仍然存在的挑战性问题。最后综合考虑动态网络链接预测的发展和目前存在的问题，对未来的研究提供了新的研究建议。

1 基于历史快照的动态链接预测

基于历史快照的研究方法主要是将动态网络按照一定的时间段划分成多个历史快照，每个历史快照代表那段时期网络的状态，通常称这个时间段为时间窗口。每个时间窗口的网络快照被统一成固定的拓扑状态[5]。基于每个历史快照上的拓扑及其他信息，研究者们采用不同的策略，预测未来时刻网络的链接状态。

1.1 基于相似性指标

由于静态网络中基于相似性指标的链接预测方法计算简单，且获得了很好的预测效果，一些学者扩展该方法到动态网络研究中。该类方法通常使用时序预测模型来综合考虑历史快照的信息。GÜNES et al[6]使用不同的相似性指标计算历史快照中节点对的相似性分数，同时联合链接交互的次数得到历史快照的得分矩阵，之后将各个历史快照的得分矩阵输入到时序预测模型中预测最后一张快照的得分矩阵，得分越高，越容易形成链接。最近，BASU et al[7]通过设计特征实现链接的预测，将节点对的不同相似性指标分数、三种类型节点对(链接随时间片稳定不变的节点对数，链接随时间片出现的节点对数，链接随时间片消失的节点对数——包含一直没有链接和链接被删除的情况)的概率作为特征，并将所有历史快照的特征矩阵输入到时序预测模型中获得最后一个时间片中节点对的特征，最后训练分类器预测最后一张时间片中链接的状态。这些方法往往固定好历史快照的相似性矩阵，随后便完全依赖于相似性矩阵本身设计时序函数，这种只单一地捕获网络的时序特征，缺乏快照内部节点关联信息和不同快照之间链接变化的有效交互，导致无法更准确地捕获到网络的动态演变信息。于是，NAJARI et al[8]利用快照内部特征和快照间相似度来获得链接存在的最终概率。其中，预测快照内部链接分数采用多种经典相似性指标获取，快照间相似度的计算由预测链接在两个快照中共有邻居的概率与历史快照中链接存在的相似性分数的乘积得到。当历史快照的数量大于2时，则计算所有快照间相似度之和，最后综合预测快照内部特征和快照间相似度得到预测快照中链接形成的概率，结果得到明显提升。

1.2 基于矩阵分解

为了获得更高的准确率，AHMED et al[9]从矩阵分解的角度提出了DeepEye，通过对历史快照的邻接矩阵进行非负矩阵分解，获得每个快照的潜在空间表示矩阵和系数矩阵；随后，他们又设计了一致的低维潜在空间表示矩阵和低维系数矩阵来表示有效保留网络的拓扑信息，其目标是要最小化分解得到的潜在空间表示矩阵和该矩阵的损失。在计算每个矩阵时，先固定三个矩阵，通过最小化损失来不断迭代更新，求取另外一个矩阵。最后一张时间片的相似矩阵由之前更新得到的系数矩阵取行向量的相似值得到。该方案证明了潜在的矩阵特征可以有效且更好地表达网络的动态性。更进一步地，LEI et al[10]提出自适应多重非负矩阵因子分解(AM-NMF)模型，在分析其在各种网络系统中的应用时，全面解决了时间链路预测问题。该模型结合了多个简单NMF组件来学习动态网络的统一低维表示。为进一步考虑单个网络快照的拓扑结构与整个动态网络之间的关系，引入了一种新的自适应参数，该参数伴随着网络表示矩阵的变化而相应改变，从而自动调整不同时间片的网络表示对整个网络表示的相对贡献。随后为了更好地捕获动态网络的非线性特征，文献[11]的作者首先对历史快照的邻接矩阵进行非负矩阵分解，接着集成不同的时序预测方法，包括Holt-Winters[12]，VAR[13]和LSTM(long short-term memory,LSTM[14])预测未来时间片的邻接矩阵，并证明三种时序预测方法中LSTM预测的结果更好。在面对大规模稀疏数据时，该类方法由于需要设计高维的矩阵，将面临着增量计算的困难性和训练速度的低效性等问题。

1.3 基于深度学习模型

基于动态网络深度模型的方法主要通过将网络的历史快照信息输入到深度嵌入模型中，用以预测未来时刻快照的链接状态。

生成模型受限玻尔兹曼机因其能够进行嵌入学习，开始被用于捕获动态网络的非线性特征[15]。LI et al[16]采用受限玻尔兹曼机学习历史时间片的低维嵌入向量，并融入邻居的影响以捕获结构信息，其中邻居的影响因子通过计算局部邻居存在概率的期望获得。最后，结合历史快照的信息和邻居的影响因子共同预测最后一个时刻的网络状态。SAM DE WINTER et al[17]基于静态网络表征学习方法node2vec[18]学习历史快照中节点的表示向量，未来时刻快照的边表示通过拼接历史快照中对应节点向量的Hadamard乘积得到，并采用监督学习的方式预测未来时刻边的状态。

然而，这些研究不足以捕捉网络的动态性变化。长短期记忆(long short-term memory,LSTM)[14]和门控循环单元(gate recurrent unit,GRU)[19]等循环神经网络被用于建模动态网络的时序特征。dyngraph2vec[20]设计了三种不同的模型来捕获网络的动态性，第一个模型简单使用编解码器对历史快照的邻接矩阵进行低维表征，之后解码预测未来时刻的邻接矩阵；第二个模型将历史快照的邻接矩阵输入到多层LSTM编解码器中，预测最后时间片的表征；第三个模型结合了前两种模型，先将历史快照的邻接矩阵通过编码器编码得到表征向量，之后输入到LSTM网络中，将预测得到的最后一个时间片的表示进一步输入到解码器中得到未来时间片的邻接矩阵。实验结果表明，通过第三种模型获得的平均准确率最好。随后，LEI et al[21]基于加权动态网络进行链接预测。首先利用GCN[22]捕获每个网络快照拓扑结构的特征；然后，将学习到的网络表示特征输入到LSTM网络中，捕获具有多个连续时间片的加权动态网络的演化模式；最后，在对抗性训练的基础上，利用GAN[23]生成了高质量、可信的图形快照。由于上述模型缺乏对局部结构信息的考虑，LI et al[24]进一步提出了深度动态网络嵌入模型，该模型将节点的高维稀疏邻接向量输入到GRU神经网络中来捕获节点层次的动态性变化特征，同时加入了节点之间的交互作用对目标函数进行约束，使其包含局部结构信息。其中，边的交互约束通过节点对之间交互的频率和经过GRU编码后节点对向量的距离得到。虽然该类研究方法可以获得较高的预测准确率，但由于选择的时间快照窗口是固定的，而网络结构发生变化的时间段不是固定的。因此该类方法无法更好地应对连续、快速变化的网络结构。

2 基于时间感知的动态链接预测

网络中链接的强度受到多种因素的影响，大多数情况下，链接存在的概率与两个节点之间保持联系的时间有着强烈的关系[25]。因此，一些研究方法单独对链接变化建模时序信息，实现动态网络的链接预测。

2.1 基于时序分数

早期加入时序信息进行链接预测的方法，主要通过融入时序权重，计算不同节点间链接关系的相似度分数，其中相似分数越高，越容易形成链接[26]。TYLENDA et al[27]在论文协作网中考虑了三种不同的影响因子作为链接的权重，其中关于时间的影响因子通过用户之间最近合作论文发布的时间来获得，用户的未来可能合作对象根据节点与不同邻居的链接强度系数排序获得。同一时期，HUANG et al[28]混合了时序预测分数和静态链接相似分数，该文基于历史链接的交互次数，采用时序预测模型，预测未来链接存在的分数，计为时序分数；同时将不同时期历史快照的邻接矩阵加和得到一个矩阵，变换为二值矩阵后，应用相似性指标(例如，共同邻居)获取得分矩阵，通过综合两种方法得到最后的链接概率矩阵。随后，SOARES et al[29]设计了更多的时序预测模型(包括移动平均，线性指数平滑等)来更好地描述网络的演变特性。为了进一步提升链接的准确性，一些研究者引入了新的时序分数，不仅捕捉链接强度的相似分数，同时还捕捉了节点在不同时间戳之间的交互分数(例如：节点a在t1时刻，b在t2时刻，a和b之间所有共同邻居的共现频率加权之和作为链接时序交互分数)[30]和不同链接类型的时序分数(对链接在不同时刻的多种状态施加奖励分数)[31]等。近来，一些学者应用时序信息到链接权重上，作为随机游走转移的概率来计算节点间交互的信息率，高的信息率更容易形成链接[25]。AHMED et al[32]首次将不同的快照通过时序衰减函数(确保更近的快照更重要)组合成一个加权图作为概率矩阵，之后进行局部随机游走获得采样节点序列，对这些采样得到的节点集，分别计算相似分数。随后，AHMED和CHEN[33]扩展该方法到不确定网络中。紧接着，一些新的思想开始被融入到动态网络中计算相似性分数。LIU et al[34]基于信息传播的思想，首先在动态演化图中利用Dijkstra算法找到节点与图中所有节点的最短路径，并转化为传播概率，添加传播概率大于设定值的最大路径影响集，两个节点的最大路径影响集的交集记为共同影响集，相似性分数的计算为：目标预测链接中节点分别与共同影响集中节点的影响分数的乘积。然而，这些方法仅简单利用了时间特征，并且大多数研究使用复杂的方法，却不能有效地学习动态网络的演化过程。

2.2 基于表示学习

随着表示学习的发展，JIANG et al[35]基于Trans E模型，对中间关系的信息融入时序转移矩阵信息来约束知识库网络的嵌入，在嵌入过程中同时优化基于翻译机制的约束和时序信息的约束。NGUYEN et al[36]将时间系数作为权重参数置于网络中，通过随机游走选择时序递增的节点，节点的嵌入向量通过优化节点表征函数来得到，之后融合节点的表示形成边的表示进行分类预测。

SAJADMANESH et al[37]首次将连续时间网络和异质网络联合起来进行链接预测。该文设计了基于元路径的时序感知特征，通过元路径的方式来捕获异质网络的信息。其中时序感知按照结点对的生成时间和消亡时间进行定义，同时将得到的基于元路径的时序感知特征输入到基于自编码器的循环神经网络中，用于获取具有时序性的节点对的低维表示。最后又设计了非参数模型将得到的链接特征表示融合为单一的特征表示，通过计算在某个时间段内形成关系的概率，实现链接预测。近几年，LIU et al[38]将时序表示学习应用到多关系网络中，通过对每个时期的网络分别应用SVD分解得到节点的嵌入向量，之后采用Hawkes过程建模具有时序信息的关系序列，最后通过结合节点嵌入的乘积和关系序列来获得链接的预测概率，该模型在大规模网络上获得不错的链接预测效果。此类方法基于表示学习，设计融入了更多的时序特征信息，同时也获得了更好的预测效果。然而该类方法不能更好地解释每个时序特征，设计实现一种具有可解释性的模型可以帮助更好地改进表示学习得到的时序特征，以便得到最佳的预测性能。

3 面临的挑战和未来研究方向

3.1 异质动态网络链接预测

随着网络数据的稀疏性、复杂性、时序性以及规模扩大等问题的出现，涉及复杂关联的大规模异质性真实网络给链接预测带来了新的挑战。异质网络包含了不同类型的节点和边，且不同类的对象均蕴含着丰富的语义信息，需要从多个维度来刻画不同类对象的意义。因此，如何有效地抽取和利用异质网络中不同类对象的多维特征信息，并有效地融合这些信息，以便全面地学习动态网络的时序特征成为了一个巨大的挑战。

3.2 不确定性动态网络链接预测

在实际生活中，常常因为各种不同的原因导致网络数据信息采集的不精确，采用该类数据得到的网络称之为不确定性网络。在不确定性网络研究中，节点被认为是确定存在的，而每条边的存在则有一定的概率。由于在不确定性网络中，建模节点对的相似性需要枚举更多的可能性情况，这也导致了该类网络实现链接预测的困难性。

3.3 准确性、高效性和可扩展性

大数据时代的到来产生了越来越多复杂的网络数据，同时也导致了现有动态网络链接预测模型的准确性和执行效率的降低，且大多数网络模型只在特定的网络结构中表现良好，当涉及到其他领域中不同的网络结构时，其表现力将发生不同程度的下降。因此，如何设计一个通用、灵活和高效的网络模型用于动态网络链接预测仍然是一个很大的挑战。

4 结束语

本文从研究动态网络链接预测的两种角度入手，分别阐述了基于历史快照和基于时间感知建模动态网络链接预测的不同方法。每种方法按不同类别研究的先后顺序展现动态网络链接预测的研究发展情况。并在此基础上总结了目前尚未完全解决的几大研究挑战，希望为今后的研究方向提供借鉴和参考。