基于门控循环单元的移动社会网络链路预测方法

刘林峰 于子兴 祝贺

（南京邮电大学计算机学院 南京 210023）

随着时代的进步，网络的概念逐渐多元化，衍生出如互联网、物联网、经济网络、生物网络等各种网络形式.在现实世界中，网络扮演着重要的角色，网络可以将现实世界中的具体问题抽象描述为一个复杂的网络系统.网络可以分为静态网络和动态网络2 类，现实世界中绝大多数网络都属于动态网络，这些网络中的节点、链路都会随着时间的推移而消失或出现.此外，网络中链路代表着不同实体之间产生的行为或者偏向，所以分析并预测这些网络中的链路具有重要的意义.

网络的链路预测通常是指预测网络中节点之间的潜在关系，如何提高预测性能一直是网络科学的一个挑战.性能优异的链路预测方法能够更好地理解网络的演变，从网络中提炼出更有价值的信息，比如蛋白质相互作用网络中[1]，酵母菌与蛋白质之间80%的相互作用不为人知，如果在已知网络结构的基础上设计足够精确的链路预测方法再进行预测指导实验，就能够提高实验成功率、降低测试成本.

移动社会网络[2]是一种典型的动态网络，如果将网络映射到图中，则节点代表人或实体，链路代表节点间的联系.由于这种联系具有时间特征，所以导致了网络的高度动态性和复杂性.

移动社会网络的链路预测可以预测人与人之间的交互，分析这种交互可以一定程度上得知一个人的交往或性格倾向，甚至能够判断该用户可能需要的服务.比如出租车司机可以更加容易在合适的地点找到乘客，陌生人之间更容易找到意气相投的朋友，卖家能够更加精准地为买家提供他们所需的商品.精准的链路预测能够为移动社会网络降低资源开销，给人们的生活带来极大的便利.图1 为一个移动社会网络示意图，比如在道路上用户通过蓝牙或车载局域网络进行通信，在小区里人们使用智能设备接入WiFi 信号点进行信息交互，也可以通过无线信号接入互联网并连接服务器，由服务器来控制用户之间的通信.

Fig.1 Example diagram of mobile social network图1 移动社会网络示意图

1 相关工作

链路预测的目的在于根据网络的历史信息来预测未来的网络结构，这可以更好地理解网络的演变，发掘网络中有价值的信息.

目前，链路预测方法主要分为3 种：基于节点相似性的链路预测方法、基于矩阵分解的链路预测方法、基于机器学习的链路预测方法.

1.1 基于节点相似性的链路预测方法

基于节点相似性的链路预测方法是指基于网络中节点的结构信息、属性信息和行为去评估节点间的相似度，若节点间的相似度越高，则表明该对节点越相似，即产生链路的可能性越大.

目前广泛应用于静态网络的链路预测指标有很多，例如共同邻居算法（common neighbors,CN）[3]、资源分配指标（resource allocation index,RA）[4].在此基础上，文献[5]基于节点相似性算法和事件检测算法提出一种社会网络事件链路预测方法，该方法对不同网络的演变性进行统一评价，并依此建立事件检测模型，并利用该模型完成链路预测.文献[6]提出了基于节点度和聚类系数的共同邻居紧密度指数，认为节点的共同邻居之间的关系越紧密，节点间连接的可能性就越高.文献[7]考虑了用户活动和其共同的邻居，并定义了局部和全局链路预测算法对节点之间的相似度进行评估.文献[8]重点关注了链路方向在链路预测问题中的作用，认为双向链路可能包含更多的网络信息，并发现具有双向链路的小部分节点更有可能通过双向链路连接到共同的邻居.文献[9]认为现有的计算节点相似度方法中公共邻居的数量只描述了一种定量关系，没有考虑给定网络的拓扑结构，于是引入节点度的概念和社区结构的思想，提出了局部亲和结构，然后与其他相似度指标在不同网络中进行实验，最终提高了链路预测精准度.

文献[3-9]中的预测方法主要在拓扑变化缓慢或发生变化较少的网络中性能较好，因此当应用场景中网络结构随时间频繁发生变化时，预测效果大大削弱.

1.2 基于矩阵分解的链路预测方法

基于矩阵分解的链路预测方法是指利用矩阵分解得到的低秩矩阵来解决链路预测问题.其中，矩阵通常由邻接矩阵或提取的其他网络结构信息矩阵组成.目前，矩阵分解主要有奇异值分解、非负矩阵分解和概率矩阵分解.

文献[10]提出了一种动态网络的链路预测方法，该方法从第一张网络快照中得到特征矩阵，并求解其低秩矩阵.然后，根据后续网络快照不断更新低秩矩阵，最终利用差值估算未来时刻节点之间链路的可能性.文献[11]指出，现有的链路预测算法缺乏对社会信息网络中的拓扑信息和非拓扑信息的有效融合，因此基于用户主题信息定义了用户主题相似度指数，并基于该指数构造主题相似度矩阵，然后将目标网络的信息和主题相似度矩阵融合到概率矩阵分解框架中，并在此基础上得到网络节点的表示，最后根据得到的隐含特征表示计算网络节点之间产生链路的概率.文献[12]将动态网络结构随时间变化的特性融合到非负矩阵分解中，提出了一种非负矩阵分解迭代规则，然后根据矩阵分解的结果得到网络的相似度矩阵，从而完成了链路预测.文献[13]采用非负矩阵分解的方法提取了时间序列图的潜在特征，采用Holt-Winters 时间序列预测方法学习，并提取潜在特征的时域信息，以此较好地解决了链路预测问题.

基于矩阵分解的链路预测方法主要是对网络的邻接矩阵进行低秩分解，通过迭代分解矩阵，提取动态网络的时变特征.然而在大规模动态网络中，迭代矩阵分解会导致极高的时间复杂度，会增加系统的响应时间和影响用户的使用体验.

1.3 基于机器学习的链路预测方法

基于机器学习的预测方法是指利用机器学习算法从一定角度提取网络中数据的特征，从而实现链路预测.

文献[14]考虑到个体偏好可能是形成链路的主要原因，将效用分析概念引入到链路预测问题中，并关注了链路形成过程中潜在变量的演变过程.由此，将链路预测问题定义为一个带有潜在变量的机器学习过程，并采用期望最大化算法来解决链路预测问题.文献[15]应用图卷积网络（graph convolutional network,GCN）、长短期 记忆网 络（long short-term memory,LSTM）和生成对抗网络（generative adversarial network,GAN）提取加权动态网络中链路变化的非线性特征，并利用GCN 获取每个快照的局部特征，然后利用LSTM 来提取动态网络的演化特征，以此提高了预测模型的准确性.文献[16]针对单链链路预测指标普适性较差的问题，提出了一种基于密度峰值聚类的自适应链路预测方法.该方法采用不同的链路预测指标作为链路的属性，并利用聚类分析将链路预测问题转化为分类问题.文献[17]将关系主题模型和贝叶斯深度学习框架相结合，构建了关系深度学习模型，然后推导出广义变分推理算法来学习变量，并完成链路预测.文献[18]将多节点链路预测问题转化为模式分类问题，通过对网络进行划分获得一系列网络快照，并计算每个快照的状态图，然后构建基于卷积神经网络（convolutional neural network,CNN）的预测模型，提取图的演变特征，从而实现了多节点的链路预测.文献[19]将动态网络划分为一系列时间序列快照，利用自动编码器和LSTM 构建模型，以此实现链路预测.文献[20]分析了动态异构网络的特性，提出了时间感知多关系链路预测的特征集，然后构建并训练了基于随机深层森林的预测模型，并对特定类型的链路进行了预测.

基于机器学习的链路预测方法是通过大量数据训练深度学习模型，再使用训练完毕的模型对网络完成链路预测.然而真实数据的复杂性以及动态网络的稀疏性严重影响了模型的训练效果，导致模型预测性能下降.

针对上述研究现状，本文提出了一种用于移动社会网络的链路预测模型（encoder-GRUs-decoder,EGRUs-D），能够较好地解决真实数据高维度、非线性所造成的链路预测困难，同时还能缓解数据稀疏性导致模型训练时可能产生局部最优的问题.由于采用了自动编码器的结构，该模型可以几乎无损地学习网络表示，并根据所提取的信息重构网络图.经过编码器模块降维后的数据更容易被堆叠的门控循环单 元（gated recurrent unit,GRU）模块学 习.本文在KONECT 的3 个真实数据集上进行了大量实验.结果表明，相比于其他方法，E-GRUs-D 模型预测性能良好，且在训练效率方面优势明显.本文主要贡献有2 个方面：

1）提出了一种E-GRUs-D 深度学习模型来预测移动社会网络中的链路，自动编码器结构能够以较少的损耗学习网络表示，同时在输入时降低数据维度以减少堆叠GRU 模块的工作量，并在输出时能够根据提取的特征还原数据维度.GRUs 模块能够有效学习数据的时变特征，保证了预测结果的准确性.

2）E-GRUs-D 模型在保持预测准确率良好的基础上，极大地缩短了训练时间.通过改变不同隐藏层单元的数量，能够适用不同规模的网络，具有较好的可扩展性.

2 方法描述

2.1 问题定义

在固定时间间隔下生成的一系列快照图可以用来表示一个移动社会网络.

定义1.移动社会网络.假设有一组图序列（G1,G2,…,Gt），其中Gk＝（V，Ek）表示移动社会网络的第k张快照图.V表 示节点集 合，Ek⊆V×V表 示第k时刻快照中节点的链路情况.假设Ak表示图Gk的邻接矩阵，若节点vi和节点vj在时刻k产生链路，则矩阵Ak的元素ak;i,j＝1，否则ak;i,j＝0.

在静态网络中，链路预测主要根据已观测到的链路分布来寻找实际存在的未知链路.而预测动态网络时则需要利用网络的历史信息，寻找网络演变的规律.由于邻接矩阵能够简化网络中节点链路情况的描述，所以本文模型的输入和输出将以邻接矩阵的形式进行设置.虽然这些相邻时刻的网络图联系较为密切，也许仅仅通过上一时刻图Gt-1也能预测下一时刻图Gt中节点的链路状况，但是这种预测方法存在一定的缺陷，因为图Gt中包含的特征太少，并且随着时间的推移，网络结构会不断发生改变，所以只使用一张图预测时效果不佳，故本文使用一组长度为N的图序列（Gt-N,Gt-(N-1),…,Gt-1）来预测下一时刻网络图Gt.

定义2.移动社会网络的链路预测.定义一组长度为N的图序列S，其中S＝（Gt-N,Gt-(N-1),…,Gt-1），本文使用E-GRUs-D 模型学习网络的演变，使得输入图序列S后可获得图Gt.

移动社会网络链路变化示例图如图2 所示.假设图2（a）为时刻t＝1 的网络链路情况，图2（b）为时刻t＝2 的网络 链路情 况.在下一时刻，边E（1,4）和 边E（5,3）消失，而边E（4,5）和边E（1,5）出现，在邻接矩阵上则可体现为对应元素由0 变为1，或者由1 变为0.通过邻接矩阵可以清晰地观测到链接的出现或消失.本文主要通过节点的历史信息来预测目标时刻可能出现的链路，如果将这一过程映射到邻接矩阵上，即观察矩阵中哪些元素的数值由0 变为1.

Fig.2 Example diagram of link changes in mobile social network图2 移动社会网络链路变化示例图

2.2 E-GRUs-D 模型

本文提出了一种用于移动社会网络链路预测的深度学习模型E-GRUs-D，该模型如图3 所示.E-GRUs-D 由自动编码器模块和GRUs 模块组成.GRUs 模块中包含多个GRU 细胞，如图4 所示，其中H0表示初始时刻的候选状态数值，Ht-1为最后一个GRU 细胞的输出，即最终提取到的时变特征.（Xt-N,Xt-(N-1),…,Xt-1）表示（Gt-N,Gt-(N-1),…,Gt-1）降维度处理后的输入图序列.

循环神经网络（recurrent neural network,RNN）的变体有2 种：GRU 和LSTM，它们的数据输入方式也与RNN 相似，通过这种依次输入并记忆再输入的循环方式，能够较好地增强数据之间的联系，提高模型在处理时间序列时的预测性能.此外，由于GRU 细胞结构的简洁性，其训练效率比LSTM 更胜一筹.

基于自动编码器的特性，本文将编码器部分和解码器部分分别放置于模型的输入端和输出端，在自动编码器模块之间加入GRUs 模块来提取数据的时变性.

1）自动编码器结构.自动编码器能够以无监督学习的方式以较低损耗的代价学习网络表示，其核心思想是实现函数y（x）=x的功能，即模型的输入等于模型输出.因此，将编码器放在模型的输入端来捕捉高阶非线性的网络结构，将解码器放在模型的输出端，使提取到的时变特征还原到先前的维度，并嵌入到网络的邻接矩阵中.由于初步输出的矩阵中元素数值为0 的个数远远大于元素数值为1 的个数，这可能导致解码器更倾向于忽略那些数值为1 的元素，即那些已经存在的链路，所以需要引导解码器更注重于先前数值为1 的元素去构建矩阵.编码器的执行过程表示为：

Fig.3 E-GRUs-D model structure图3 E-GRUs-D 模型结构

Fig.4 GRUs module details图4 GRUs 模块细节

式（1）中，si表示输入序列S的第i张图的邻接矩阵.式（2）中，We;k和be;k表示第k层编码器的权值矩阵和偏置矩阵，表示第k层编码器输入第i张图产生的输出.式（3）中，Ye;k表示第k层编码器输入整个序列时产生的输出.对于编码器层激活函数的选取，本文保存了自动编码器结构的默认设置，仍选取ReLU作为其激活函数.

编码器部分和解码器部分互为镜像结构，它接收GRUs 模块学习而来的特征，重构先前的空间结构并将它们映射到邻接矩阵内，该过程表示为：

式（4）中，U表示GRUs 结构的输出，即提取到的特征.式（5）中，Wd;k和bd;k表示第k层解码器的权值矩阵和偏置矩阵，Yd;k表示第k层解码器的输出.该结构仍和编码器结构一样，选取ReLU作为其激活函数.式（6）中 σ表示激活函数Sigmoid，这是为了在解码器的最后一层实现归一化处理.

2）GRUs 结构.虽然自动编码器结构能够处理高阶非线性类型的数据，但并不能捕捉图序列中的时间特征.GRU 作为RNN 的变体，能够学习动态网络中节点的历史信息，其结构简洁，又能在提取效率上优于LSTM.因此本文使用此结构作为该模型的隐藏层提取数据的时变特征.一个GRU 细胞由2 种门组成，分别是重置门和更新门.GRU 对于输入值的处理程度主要依靠候选状态Ht和隐藏候选状态这2 个变量决定，隐藏候选状态决定着候选状态，而候选状态影响着时刻tGRU 的输出保留了多少历史时刻的输入.首先，数据输入到GRU 中经过重置门，通过输出重置值Rt来重置当前时刻的隐藏候选状态，该过程定义为

其中，Xt表示时刻t的输入；Rt表示时刻t的输出；Ht-1表示时刻t-1 的候选状态，当t=0 时一般取默认值或设置为0；Wr表示重置门的权值矩阵；[,]表示2 个向量相连操作；“· ”表示矩阵点乘，其运算结果为标量；σ表示重置门的激活函数Sigmoid.

在同一时刻，输入数据流入更新门，更新门会更新当前的状态信息，以决定对历史信息的保留程度，该过程定义为

式（8）中，Zt表示时刻t更新门的输出，Wz表示更新门的权值矩阵.然后，更新门根据重置值Rt和更新值Zt对隐藏候选状态和候选状态Ht进行操作，该过程定义为

最后GRU 根据候选状态Ht输出结果，该过程表示为

由式（7）～（11）可知，当Zt=1时，GRU 会完全摒弃过去的候选状态即历史信息；当Zt=0时，GRU 会完全复制当前时刻的上一时刻的候选状态.重置门用于控制前一时刻有多少信息被写入到当前的隐藏候选状态中，重置门的值越小，则的值越小，即前一时刻的信息被写入当前时刻的信息就越少.更新门用于控制前一时刻的状态信息被带入到当前时刻状态中的程度，更新门的值越大，则式（10）对的侧重就越强，即前一时刻的状态信息被带入的越多.通过这种模式，GRU 细胞能够对历史信息有选择地保留.虽然单个GRU 层已经初步具备学习节点历史信息的能力，然而效果并不是很理想，为了充分利用GRU 在时间处理方面的优秀能力，本文将根据输入图序列的长度N，将多个GRU 串联起来，这种串联堆叠的GRUs 模块可以更好地处理具有时变特性的网络，从而有效提高模型预测的准确率.

3）隐藏层节点数量的设置.隐藏层节点的数量与模型提取数据特征的能力密不可分，不同节点数量的隐藏层具有不同的提取能力.如果节点数量设置太少，则提取能力不足，容易增加模型重构数据时的误差；反之，则会增加模型的复杂度，产生多余的资源开销，并且容易出现过拟合问题.节点数量的设置主要由下列公式确定：

式（12）和式（13）中，Sn表示隐藏层节点的数量，m表示模型的输入维度，n表示模型的输出维度，考虑到数据集的大小和计算开销，本文选择式（13）来计算隐藏层节点的数量.

4）梯度算法的设置.梯度算法决定了模型的收敛速度.E-GRUs-D 模型使用的是Keras 库中的Adadelta优化器，由于Adadelta 能够根据渐变更新的移动窗口调整学习速率，所以相比于传统的SGD 随机梯度下降优化器，Adadelta 具有更强鲁棒性，且在设定的模型训练次数完毕之前，Adadelta 能够保持对参数的学习，同时无需设置其初始学习率，从而避免了设置参数时的主观性.

2.3 训练过程

在线性回归问题中，L2范数常常被用来测量2 个样本的相似度.然而如果仅仅使用该范数作为本文模型的损失函数，并不能很好地解决矩阵稀疏性所造成的过拟合现象.为了处理这一问题，应当把反向传播的重点放在现存的链路上而非不存在的链路上.本文采用了文献[20]所提供的损失函数Ltotal，该函数由基础损失函数L和L2范数组成：

其中，L2范数通常用来避免模型进入过拟合状态；α为超参数，其取值范围是0～1；基础损失函数L表示预测值和标签值的差值并求和.

基于理论出发，邻接矩阵At的元素值取值为0或者1.然而实际生成的数值均为小数.为了获得有效的邻接矩阵元素值，首先对这些小数进行归一化处理，即在输出层放置1 个Sigmoid 函数.然后进行一层过滤，若矩阵元素at;i,j＞ 0.5，则令at;i,j=1，即近似表示节点i和节点j之间存在链路，反之，令at;i,j＝0，即表示不存在链路.

对于模型的收敛，本文主要根据损失函数数值变动的幅度进行判断.如果在模型训练100 轮之后，损失函数的数值不再显著变化（保留小数点后3 位不再变化），则判定模型收敛.由于本文采用的数据集规模适中，且GRU 模块参数较少，所以模型更容易达到收敛但同时易产生过拟合问题.

2.4 抗噪性分析

离群点作为数据集中的一种异常点，它的产生可能由于数据格式异常、数据内容异常和事件偶然性造成的异常.对于前2 种异常的发生，本文在数据集预处理时已经进行规避，但对于第3 种异常情况，比如首次见面的人之间偶然产生的短暂且不具备重复性的对话，为了保证数据集的真实性，本文未将其从数据集中排除.因此造成了不同数据集之间分布的优劣，导致各个数据集形成的网络在周期性上具有一定的差异，而这种差异会对模型的训练造成影响，从而导致预测结果的不同.

2.5 空间复杂度分析

1）LSTM 主要维护4 套参数，分别是输入门参数、输出门参数、遗忘门参数和候选状态参数，每套参数都由输入参数input_size、输出参数output_size、偏移项参数bias以及隐藏层参数hidden_size共4 部分组成，则LSTM 参数总量Num为

由于任意时刻LSTM 的输出y均为ht，并未产生额外的映射，所以

假设LSTM 的输入维度为p×g，隐藏层的节点数为p，则最终LSTM 的空间复杂度为

2）GRU 主要维护3 套参数，分别是重置门参数、更新门参数和候选状态参数，每套参数都有其输入和输出以及偏移项，由于GRU 和LSTM 均为RNN 的变体，所以GRU 的参数计数过程与LSTM 相同，则最终GRU 的空间复杂度为

LSTM 和GRU 作为RNN 的变体，均能够捕捉数据的时间关联性，并且能够有效抑制梯度消失或爆炸，但是LSTM 的参数量约为RNN 的4 倍，而GRU的参数量只有RNN 的3 倍，所以在模型复杂度方面，GRU 更加简洁，同时这也是GRU 模型在训练时更不容易出现过拟合问题的原因.因此，在相同的数据集下GRU 的训练效率相比于LSTM 大大提高.

3 实 验

本文所提出的模型将基于KONECT 的3 个移动社会网络数据集进行评估，并与其他3 种基准方法进行比较.

3.1 数据集

本文使用了3 个现实生活中的移动社会网络数据集，这些数据集均涉及人与人之间的交互记录.在这些网络图中，节点代表参与者，而边则表示与他人之间的联系.数据集的部分具体信息如表1 所示.

Table 1 Basic Information for the Three Datasets表1 3 种数据集的基本信息

1）HyperText[21].该数据 集记录 了2009 年ACM超文本会议中出席人之间面对面会谈的情况，该会议于2009 年6 月29 日在意大利都灵举办，为期3 天.在该网络中，节点代表会议出席人，边代表出席人之间至少存在20s 以上的对话，并且每条边都标注了接触发生的时间.

2）Infectious[21].该数据集记录了2009 年在都柏林科学画廊举办的《传染：远离》展览会期间人们之间的交流情况.在该网络中，节点代表了画展的参观者，边表示参观者之间产生了至少20 s 以上的接触，并且记录了发生时间.

3）Haggle[21].该数据集记录了人们在一定区域携带无线智能设备生活，并与他人产生往来的情况.在该网络中，节点和边代表的含义与网络HyperText 和网络Infectious 相同，并且同样记录了接触的发生时间.不同的是，在Haggle 网络中，同一时刻可能产生多条边.

在输入数据之前，要先对数据集进行预处理.首先，对数据集按照时间戳大小进行排序，保证模型所获取的历史信息的连续性和正确性.然后，排除数据异常值，如空值或残缺值.再次，按照固定时间间隔为每个数据集生成快照，即将整个数据集划分为一系列网络图，由于数据集中记录的相邻时刻链路产生的时间差均为20 s，所以固定时间间隔设置为20 s.考虑到存在同一时刻可能产生多条链路的情况，将同一时刻产生的链路归属到同一个图中.本文将抽象的图转化为具体的邻接矩阵，每个邻接矩阵的维度设置为各个数据集对应的参加人数，为了保证数据集的充足和数据之间的时间关联性，每个样本以滑动窗口的形式进行创建，滑动窗口的长度等同于输入图序列长度N，即每个样本的格式均为（Gt-N,Gt-(N-1),…,Gt）.实验中N=10，矩阵序列（Gt-10,Gt-9,…,Gt）作为一个样本，在该样本中，前10 个矩阵作为模型的输入，最后1 个矩阵作为此次输入的标签.每个矩阵中，存储着当前时间的节点信息，若人们之间存在交谈，则相应的矩阵元素数值设置为1，否则设置为0.在极端条件下，即某一时刻没有任何人产生交谈记录，则生成零矩阵.本文按照链路产生的时间顺序，将前75%的数据集设置为训练集，将后25%的数据集设置为测试集，同时遵循滑动窗口规则，尽可能多地创建样本，最终从数据集中提取出320 张网络快照图，其中前240 张快照图作为训练集使用，后80 张快照图作为测试集使用.

3.2 基准方法

为了验证E-GRUs-D 模型的性能，本文使用了3种基准方法与该模型进行对比，包括静态网络的链路预测方法node2vec[22]、深度学习模型DDNE[23]和深度学习模型E-LSTM-D[19].

1）node2vec[22].node2vec 是一种综合考量深度优先搜索邻域和广度优先搜索邻域的图嵌入（graph embedding）方法.该方法常用于静态网络，它将网络中节点的链路情况进行降维.在低维空间中，如果1对节点对应的向量距离越短，则表明2 个节点的相似性就越高，即这对节点产生链路的可能性越高.

2）DDNE[23].该模型借鉴了自动编码器结构，模型的核心部分是2 个GRU 层，其中一层作为编码器使用，另一层作为解码器使用，编码器模块负责学习数据的时间变化特性，解码器模块则负责将提取的特征嵌入到未来网络结构中.

3）E-LSTM-D[19].该模型使用了自动编码器和长短期记忆网络结合的方式构造模型，编码器负责简化数据，解码器负责还原数据维度.隐藏层为多个LSTM 串联组成，用来提取数据特征.

基于数据集的规模和对比实验，首先将隐藏层层数设置为2，然后根据式（13）设置隐藏层节点数量.输入层编码器节点数量取默认值128，由于输出层的输出形状要求与最终输出的邻接矩阵形状相同，所以解码器层节点数量设置为各数据集中的总参与人数.参数的具体设置如表2 所示.

Table 2 Number of Hidden Layer Nodes Under Each Dataset表2 各数据集下隐藏层节点的数量

3.3 评价指标

1）混淆矩阵（confusion matrix）.该指标是一个标准混淆矩阵，如图5 所示.

在混淆矩阵中，预测类别为1 的为正样本（Positive），预测类别为0 的为负样本（Negative）.真阳率TPR表示所有真实类别为1 的样本中预测类别为1 的占比，伪阳率FPR表示所有真实类别为0 的样本中预测类别为1 的占比.TPR和FPR分别定义为：

其中TP表示模型正确预测为正样本的次数，FP表示模型错误预测为正样本的次数，FN表示模型错误预测为负样本的次数，TN表示正确预测为负样本的次数.根据TPR和FPR则能绘制出接收者操作特征曲 线（receiver operating characteristic curve,ROC）.其中TPR作为纵坐标轴，FPR作为横坐轴.

2）AUC指标.AUC通常用于衡量静态网络链路预测方法的准确性，其表示ROC 下的面积，表示模型正确预测为正样本概率大于错误预测为正样本概率的可能性.假设在数据中有M个正样本和 ℓ个负样本，则共有M×ℓ 对样本.若有M1次出现正样本和负样本预测概率相同，有M2次出现正样本预测概率值大于负样本预测概率值，则AUC定义为

AUC数值越大则表明模型的预测性能越好.特别地，当AUC=0.5 时表明对于不论真实类别是1 还是0 的样本，模型预测为1 的概率是相等的.

3）错误率ER.ER一般是指模型错误预测的样本数量占总样本数量的比例，是一种通用的性能指标，定义为

其中，at;i,j表示时刻t标签矩阵中第i行第j列的元素值，表示时刻t输出矩阵中第i行第j列的元素值，Q代表总链路数，n代表输出维度.

Fig.5 Confusion matrix图5 混淆矩阵

3.4 实验结果

本文设置N＝10 作为E-GRUs-D，DDNE，E-LSTM-D这3 种模型的输入序列长度，由于node2vec 方法无法处理时间序列，故直接使用图Gt-1去预测图Gt，以此完成性能评估.

本文在评价指标AUC和ER的基础上对E-GRUs-D 模型和其他3 种基准方法进行了比较，并选取其中性能最好的2 种方法对比它们的模型训练时间，预测性能对比实验结果分别如表3 和表4 所示，模型训练时间对比实验结果如图6 所示.

Table 3 AUC Evaluation Metric表3 AUC 评价指标

Table 4 ER Evaluation Metric表4 ER 评价指标

Fig.6 Comparison of training time图6 训练时间对比

在表3 和表4 中，node2vec 方法的链路预测准确率远远小于其他方法，这表明相比于用于动态网络链路预测的方法，node2vec 并不能很好地学习移动社会网络中节点的链路变化情况.总体而言，尽管ELSTM-D 模型的预测结果要略优于E-GRUs-D 模型，但图6 表明，在3 种不同数据集下，E-GRUs-D 模型的训练时间要远短于E-LSTM-D 模型，体现了在相同数据规模下，E-GRUs-D 模型在缩短训练时间上的优势.

从实验结果来看，E-GRUs-D 模型在不同的网络规模、网络密度中都能够得到较为理想的预测效果，虽然其预测性能略低于E-LSTM-D 模型，但是训练时间和计算效率得到显著提高.此外，当在数据集规模较小的情况下，E-GRUs-D 的预测准确率超过了ELSTM-D 模型，该现象符合LSTM 和GRU 的特性：虽然GRU 和LSTM 内部均和“门控”这一概念密不可分，但是GRU 内部主要由2 个门进行运作，而LSTM内部则由3 个门进行运作，得益于GRU 内部构造的简洁性，在数据集规模较小的情况下，GRU 的训练效果会优于LSTM.

Fig.7 AUC values on different datasets图7 不同数据集下AUC 值

Fig.8 ER values on different datasets图8 不同数据集下ER 值

不同数据集下的实验结果如图7 和图8 所示.其中，实线是相应数据集下模型在测试集中不同测试轮数的评价指标结果，虚线表示其结果的平均值.从这2 个图可知，本文所提出的E-GRUs-D 模型具有稳定良好的预测效果，其中在Haggle 数据集下，预测的稳定性相对于Infectious 数据集和HyperText 数据集较差，这是由于Infectious 和HyperText 这2 种网络的演变更具有周期性，更易于模型的学习，从而可以得到稳定性更强的预测结果.

模型预测结果波动较大是因为数据集中存在一些偏差点，比如首次见面的人之间偶然性的对话，由于在数据集中该节点对之间产生的数据较少，模型对于该信息无法进行充分的学习，故模型测试时在某段数据上易表现出较大的波动.

如果忽略掉个别离群点，如Infectious 数据集对应图中的离群点，那么基于该数据集的预测结果在预测稳定性、指标平均值都较优于其他2 个数据集，这是因为在数据规模上，Infectious 数据集要大于其他2 种数据集，它能够提供给模型更加充足的信息，使模型提取到足够的历史信息，更好地训练得到网络的时间变化特性.

3.5 参数设置实验

E-GRUs-D 模型的性能主要受到模型结构和输入图序列长度N的影响，下面将展开相关实验.

1）模型结构的影响.模型结构主要由隐藏层节点数量和隐藏层层数决定，借助于式（13），隐藏层节点数量可以确定，所以本文在相同节点数量的条件下观察隐藏层层数对预测结果的影响.

图9 和图10 为隐藏层层数对模型性能影响的实验结果.可知，在任何一种数据集下，当隐藏层层数设置为1 时，模型的学习能力不足，所以必须通过增加层数来提升模型的学习能力；当隐藏层层数设置为2 时预测效果最佳；当层数设置为3 时，由于提取了过多无用的信息，并且计算量随着层数增多而急剧增加，预测效果反而下降.

Fig.9 Influence of the number of hidden layers on AUC values图9 隐藏层数对AUC 值的影响

Fig.10 Influence of the number of hidden layers on ER values图10 隐藏层数对ER 值的影响

2）输入图序列长度的影响.一般来说，输入的图序列越长，其中包含的历史信息就越多，模型能更好地学习网络的演变，预测准确率也越高.

然而，实验结果表明如果输入的图序列过长，则其中可能会包含过多不相关的特征，导致资源浪费.因此，合适的输入图序列长度对于模型的预测性能也至关重要.本文在各数据集下测试了N从5 到15变化时对模型性能的影响，实验结果如图11 和图12所示.对于规模较小的数据集HyperText 和数据集Haggle 而言，在N取值为11 之前，其预测性能随着长度的递增而不断提升，而N取值超过11 之后，性能开始降低，这是因为当输入序列过长，模型学习到过多冗余的历史信息.由于Infectious 数据集规模较大，在整个过程中模型性能都随着N的增加而增加，但在N取值为11 之后，模型的性能提升幅度减缓，需要注意的是，这种性能缓慢提升需要耗费巨大的模型训练计算量.

Fig.12 Influence of the input sequence length on ER values图12 输入序列长度对ER 值的影响

4 结论

本文提出了一种适用于移动社会网络链路预测的E-GRUs-D 模型，该模型的Encoder-Decoder 模块能够学习高阶非线性的网络结构，从而降低了隐藏层的计算量，同时将提取的特征重构至先前的维度并映射到目标时刻网络的邻接矩阵中.GRUs 模块的复数个GRU 串联结构，首先能使模型提取数据的时变特征；其次，和只有1 层GRU 相比，学习能力更强，有助于提升模型预测性能；而且由于自身结构的简洁性，该方法在缩短训练时间方面要明显优于现有方法；还能通过调整节点数量，适用不同规模的网络，具有良好的可扩展性.大量的实验表明，对于移动社会网络的链路预测问题，该模型具有较为高效且准确的预测性能.

E-GRUs-D 模型和E-LSTM-D 模型在相同数据集下，模型性能差距较小，但是由于GRU 拥有相对于LSTM 较低的模型复杂度，所以在模型训练效率方面更加优秀.然而，不论是LSTM 还是GRU，只是相对于RNN 而言，更加能够抑制梯度消失或爆炸，且作为RNN 的变体，有着和RNN 结构同样的弊端，即无法进行并行计算，所以在数据量不断剧增以及模型体量不断增大的未来，我们的研究将更加注重模型本身的优化，尽可能进一步抑制梯度消失和提高模型运算效率.

作者贡献声明：刘林峰提出指导性意见并修改论文；于子兴提出算法思路和实验方案，完成实验并撰写论文；祝贺负责收集实验数据和完善实验方案.