A Link Prediction Method Based on Gated Recurrent Units for Mobile Social Network
-
摘要:
链路预测是指通过已知的网络拓扑和节点信息来预测未来时刻节点之间的潜在关系，链路预测能够帮助在各种存在链路的应用领域更加合理地分配资源、降低资源开销.移动社会网络属于动态网络的一种，其网络结构总是随着节点和链路的出现、消失以及时间推移而不断演变.针对移动社会网络的特点，当前已有的研究使用愈加复杂的模型来分析链路之间的联系，然而复杂的模型不但空间复杂度大而且容易造成过拟合问题. 为了解决以上问题，提出一种基于门控循环单元的移动社会网络链路预测方法.首先对输入数据集进行排序筛选，将目标网络划分为快照图，并按一定的规则转化为邻接矩阵形成样本集，然后基于自动编码器和门控循环单元构建预测模型，提取出移动社会网络的时间变化特征.在KONECT数据集上，与其他模型的对比实验结果表明，该方法能够保持预测性能几乎不变的情况下，使模型训练效率提升49.81%.
Abstract:Link prediction is defined as the prediction of potential relationships between nodes in the future based on the known network topology and the node information. Link prediction can help reduce resource expenditure and allocate resources more reasonably in various applications including links. Mobile social network is a kind of dynamic network, and its structure is always evolving with the appearance and disappearance of nodes and links over time. According to the characteristics of the mobile social network, the current existing researches use more sophisticated model to analyze the relationship between the links, however complex models not only have large space complexity but also are easy to over fitting problem. In order to solve the above problems, a gating cycle unit based on the prediction method of mobile social network link is put forward. Firstly, the input data set is sorted and filtered, and the target network is divided into snapshot graphs and transformed into adjacency matrices to form a sample set. Then, the prediction model is constructed based on the auto encoder and the gated recurrent units to extract the temporal characteristics of mobile social network. Based on KONECT dataset, the experimental results compared with other models show that the proposed method can improve the training efficiency by 49.81%, while the prediction performance can be maintained.
-
Keywords:
- deep learning /
- link prediction /
- mobile social network /
- gated recurrent units /
- auto encoder
-
随着时代的进步，网络的概念逐渐多元化，衍生出如互联网、物联网、经济网络、生物网络等各种网络形式. 在现实世界中，网络扮演着重要的角色，网络可以将现实世界中的具体问题抽象描述为一个复杂的网络系统. 网络可以分为静态网络和动态网络2类，现实世界中绝大多数网络都属于动态网络，这些网络中的节点、链路都会随着时间的推移而消失或出现. 此外，网络中链路代表着不同实体之间产生的行为或者偏向，所以分析并预测这些网络中的链路具有重要的意义.
网络的链路预测通常是指预测网络中节点之间的潜在关系，如何提高预测性能一直是网络科学的一个挑战. 性能优异的链路预测方法能够更好地理解网络的演变，从网络中提炼出更有价值的信息，比如蛋白质相互作用网络中[1]，酵母菌与蛋白质之间80%的相互作用不为人知，如果在已知网络结构的基础上设计足够精确的链路预测方法再进行预测指导实验，就能够提高实验成功率、降低测试成本.
移动社会网络[2]是一种典型的动态网络，如果将网络映射到图中，则节点代表人或实体，链路代表节点间的联系. 由于这种联系具有时间特征，所以导致了网络的高度动态性和复杂性.
移动社会网络的链路预测可以预测人与人之间的交互，分析这种交互可以一定程度上得知一个人的交往或性格倾向，甚至能够判断该用户可能需要的服务. 比如出租车司机可以更加容易在合适的地点找到乘客，陌生人之间更容易找到意气相投的朋友，卖家能够更加精准地为买家提供他们所需的商品. 精准的链路预测能够为移动社会网络降低资源开销，给人们的生活带来极大的便利. 图1为一个移动社会网络示意图，比如在道路上用户通过蓝牙或车载局域网络进行通信，在小区里人们使用智能设备接入WiFi信号点进行信息交互，也可以通过无线信号接入互联网并连接服务器，由服务器来控制用户之间的通信.
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, E-GRUs-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.
2.2 E-GRUs-D模型
本文提出了一种用于移动社会网络链路预测的深度学习模型E-GRUs-D，该模型如图3所示. E-GRUs-D由自动编码器模块和GRUs模块组成. GRUs模块中包含多个GRU细胞，如图4所示，其中
{\boldsymbol{H}}_{0} 表示初始时刻的候选状态数值，{\boldsymbol{H}}_{t-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的元素去构建矩阵. 编码器的执行过程表示为：
{\boldsymbol{y}}_{i}^{1}=ReLU({\boldsymbol{W}}_{\mathrm{e};1}{{\boldsymbol{s}}}_{i}+{\boldsymbol{b}}_{\mathrm{e};1}) \text{，} (1) {\boldsymbol{y}}_{i}^{k}=ReLU({\boldsymbol{W}}_{\mathrm{e};k}{{\boldsymbol{y}}}_{i}^{(k-1)}+{\boldsymbol{b}}_{\mathrm{e};k}) \text{，} (2) {\boldsymbol{Y}}_{\mathrm{e};k}=\left({\boldsymbol{y}}_{0}^{k},{\boldsymbol{y}}_{1}^{k},…,{\boldsymbol{y}}_{N-1}^{k}\right) . (3) 式（1）中，
{{\boldsymbol{s}}}_{i} 表示输入序列S的第i张图的邻接矩阵. 式（2）中，{\boldsymbol{W}}_{\mathrm{e};k} 和{\boldsymbol{b}}_{\mathrm{e};k} 表示第k层编码器的权值矩阵和偏置矩阵，{\boldsymbol{y}}_{i}^{k} 表示第k层编码器输入第i 张图产生的输出. 式（3）中，{\boldsymbol{Y}}_{\mathrm{e};k} 表示第k层编码器输入整个序列时产生的输出. 对于编码器层激活函数的选取，本文保存了自动编码器结构的默认设置，仍选取ReLU作为其激活函数.编码器部分和解码器部分互为镜像结构，它接收GRUs模块学习而来的特征，重构先前的空间结构并将它们映射到邻接矩阵内，该过程表示为：
{\boldsymbol{Y}}_{\mathrm{d};1}=ReLU({\boldsymbol{W}}_{\mathrm{d};1}\boldsymbol{U}+{\boldsymbol{b}}_{\mathrm{d};1}) \text{，} (4) {\boldsymbol{Y}}_{\mathrm{d};k}=ReLU\left({\boldsymbol{W}}_{\mathrm{d};k}{\boldsymbol{Y}}_{\mathrm{d};\left(k-1\right)}+{\boldsymbol{b}}_{\mathrm{d};k}\right) \text{，} (5) {\boldsymbol{Y}}_{\mathrm{d};n}=\sigma ({\boldsymbol{W}}_{\mathrm{d};n}{\boldsymbol{Y}}_{\mathrm{d};(n-1)}+{\boldsymbol{b}}_{\mathrm{d};n} . (6) 式（4）中，U表示GRUs结构的输出，即提取到的特征. 式（5）中，
{\boldsymbol{W}}_{\mathrm{d};k} 和{\boldsymbol{b}}_{\mathrm{d};k} 表示第k层解码器的权值矩阵和偏置矩阵，{\boldsymbol{Y}}_{\mathrm{d};k} 表示第k层解码器的输出. 该结构仍和编码器结构一样，选取ReLU作为其激活函数. 式（6）中\sigma 表示激活函数Sigmoid，这是为了在解码器的最后一层实现归一化处理.2）GRUs结构. 虽然自动编码器结构能够处理高阶非线性类型的数据，但并不能捕捉图序列中的时间特征. GRU作为RNN的变体，能够学习动态网络中节点的历史信息，其结构简洁，又能在提取效率上优于LSTM. 因此本文使用此结构作为该模型的隐藏层提取数据的时变特征. 一个GRU细胞由2种门组成，分别是重置门和更新门. GRU对于输入值的处理程度主要依靠候选状态
{\boldsymbol{H}}_{t} 和隐藏候选状态\widetilde{{\boldsymbol{H}}}_{t} 这2个变量决定，隐藏候选状态决定着候选状态，而候选状态影响着时刻t GRU的输出保留了多少历史时刻的输入. 首先，数据输入到GRU中经过重置门，通过输出重置值{R}_{t} 来重置当前时刻的隐藏候选状态，该过程定义为{R}_{t}=\sigma ({\boldsymbol{W}}_{\mathrm{r}}· [{\boldsymbol{H}}_{t-1},{\boldsymbol{X}}_{t}\left]\right) . (7) 其中，
{\boldsymbol{X}}_{t} 表示时刻t的输入；{R}_{t} 表示时刻t的输出；{\boldsymbol{H}}_{t-1} 表示时刻t−1的候选状态，当t=0时一般取默认值或设置为0；{\boldsymbol{W}}_{\mathrm{r}} 表示重置门的权值矩阵；[ , ]表示2个向量相连操作；“· ”表示矩阵点乘，其运算结果为标量；\sigma 表示重置门的激活函数Sigmoid.在同一时刻，输入数据流入更新门，更新门会更新当前的状态信息，以决定对历史信息的保留程度，该过程定义为
{Z}_{t}=\sigma ({\boldsymbol{W}}_{\mathrm{z}}· [{\boldsymbol{H}}_{t-1},{\boldsymbol{X}}_{t}\left]\right) . (8) 式（8）中，
{Z}_{t} 表示时刻t更新门的输出，{\boldsymbol{W}}_{\mathrm{z}} 表示更新门的权值矩阵. 然后，更新门根据重置值{R}_{t} 和更新值{Z}_{t} 对隐藏候选状态\widetilde {\boldsymbol{H}}_{t} 和候选状态{\boldsymbol{H}}_{t} 进行操作，该过程定义为\widetilde {\boldsymbol{H}}_{t}=\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}({\boldsymbol{W}}_{\mathrm{h}}· [{R}_{t}{\boldsymbol{H}}_{t-1},{\boldsymbol{X}}_{t}\left]\right) \text{，} (9) {\boldsymbol{H}}_{t}=(1-{Z}_{t}){\boldsymbol{H}}_{t-1}+{Z}_{t}\widetilde {\boldsymbol{H}}_{t} . (10) 最后GRU根据候选状态
{\boldsymbol{H}}_{t} 输出结果，该过程表示为{{\boldsymbol{Y}}}_{t}=\sigma ({\boldsymbol{W}}_{{\boldsymbol{y}}}·{\boldsymbol{H}}_{t}) . (11) 由式（7）~（11）可知，当
{Z}_{t}=1 时，GRU会完全摒弃过去的候选状态即历史信息；当{Z}_{t}=0 时，GRU会完全复制当前时刻的上一时刻的候选状态. 重置门用于控制前一时刻有多少信息被写入到当前的隐藏候选状态\widetilde {\boldsymbol{H}}_{t} 中，重置门的值越小，则\widetilde {\boldsymbol{H}}_{t} 的值越小，即前一时刻的信息被写入当前时刻的信息就越少. 更新门用于控制前一时刻的状态信息被带入到当前时刻状态中的程度，更新门的值越大，则式（10）对\widetilde {\boldsymbol{H}}_{t} 的侧重就越强，即前一时刻的状态信息被带入的越多. 通过这种模式，GRU细胞能够对历史信息有选择地保留. 虽然单个GRU层已经初步具备学习节点历史信息的能力，然而效果并不是很理想，为了充分利用GRU在时间处理方面的优秀能力，本文将根据输入图序列的长度N，将多个GRU串联起来，这种串联堆叠的GRUs模块可以更好地处理具有时变特性的网络，从而有效提高模型预测的准确率.3）隐藏层节点数量的设置. 隐藏层节点的数量与模型提取数据特征的能力密不可分，不同节点数量的隐藏层具有不同的提取能力. 如果节点数量设置太少，则提取能力不足，容易增加模型重构数据时的误差；反之，则会增加模型的复杂度，产生多余的资源开销，并且容易出现过拟合问题. 节点数量的设置主要由下列公式确定：
{S}_{n}=\sqrt{mn}+n \text{，} (12) {S}_{n}\le \sqrt{n(m-1)}+1 . (13) 式（12）和式（13）中，Sn表示隐藏层节点的数量，m表示模型的输入维度，n表示模型的输出维度，考虑到数据集的大小和计算开销，本文选择式（13）来计算隐藏层节点的数量.
4）梯度算法的设置. 梯度算法决定了模型的收敛速度. E-GRUs-D模型使用的是Keras库中的Adadelta优化器，由于Adadelta能够根据渐变更新的移动窗口调整学习速率，所以相比于传统的SGD随机梯度下降优化器，Adadelta具有更强鲁棒性，且在设定的模型训练次数完毕之前，Adadelta能够保持对参数的学习，同时无需设置其初始学习率，从而避免了设置参数时的主观性.
2.3 训练过程
在线性回归问题中，
{L}_{2} 范数常常被用来测量2个样本的相似度. 然而如果仅仅使用该范数作为本文模型的损失函数，并不能很好地解决矩阵稀疏性所造成的过拟合现象. 为了处理这一问题，应当把反向传播的重点放在现存的链路上而非不存在的链路上. 本文采用了文献[20]所提供的损失函数{L}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}} ，该函数由基础损失函数L 和{L}_{2} 范数组成：{L}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}=L+\alpha {L}_{2} . (14) 其中，
{L}_{2} 范数通常用来避免模型进入过拟合状态；\alpha 为超参数，其取值范围是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为
Num=4hidden\_size\times (input\_size+ bias+output\_size) . (15) 由于任意时刻LSTM的输出
\boldsymbol{y} 均为{\boldsymbol{h}}_{t} ，并未产生额外的映射，所以hidden\_size=output\_size . (16) 假设LSTM的输入维度为
p\times g ，隐藏层的节点数为p ，则最终LSTM的空间复杂度为O\left(4\right(pq+p+{p}^{2}\left)\right) . (17) 2） GRU主要维护3套参数，分别是重置门参数、更新门参数和候选状态参数，每套参数都有其输入和输出以及偏移项，由于GRU和LSTM均为RNN的变体，所以GRU的参数计数过程与LSTM相同，则最终GRU的空间复杂度为
O\left(3\right(pq+p+{p}^{2}\left)\right) . (18) LSTM和GRU作为RNN的变体，均能够捕捉数据的时间关联性，并且能够有效抑制梯度消失或爆炸，但是LSTM的参数量约为RNN的4倍，而GRU的参数量只有RNN的3倍，所以在模型复杂度方面，GRU更加简洁，同时这也是GRU模型在训练时更不容易出现过拟合问题的原因. 因此，在相同的数据集下GRU的训练效率相比于LSTM大大提高.
3. 实 验
本文所提出的模型将基于KONECT的3个移动社会网络数据集进行评估，并与其他3种基准方法进行比较.
3.1 数据集
本文使用了3个现实生活中的移动社会网络数据集，这些数据集均涉及人与人之间的交互记录. 在这些网络图中，节点代表参与者，而边则表示与他人之间的联系. 数据集的部分具体信息如表1所示.
表 1 3种数据集的基本信息Table 1. Basic Information for the Three Datasets数据集 参与人数 边数 平均距离/m 最大距离/m 持续天数 HyperText 113 20818 368.5 1483 3 Infectious 410 17298 84.4 294 9 Haggle 274 28202 206.2 2092 4 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所示.
表 2 各数据集下隐藏层节点的数量Table 2. Number of Hidden Layer Nodes Under Each Dataset数据集 编码器层 GRUs第1层和第2层 解码器层 HyperText 128 118，118 113 Infectious 128 227，227 410 Haggle 128 185，185 274 3.3 评价指标
1） 混淆矩阵（confusion matrix）. 该指标是一个标准混淆矩阵，如图5所示.
在混淆矩阵中，预测类别为1的为正样本（Positive），预测类别为0的为负样本（Negative）. 真阳率TPR表示所有真实类别为1的样本中预测类别为1的占比，伪阳率FPR表示所有真实类别为0的样本中预测类别为1的占比. TPR和FPR分别定义为：
TPR=\frac{TP}{TP+FN} \text{，} (19) FPR=\frac{FP}{FP+TN} . (20) 其中TP表示模型正确预测为正样本的次数，FP表示模型错误预测为正样本的次数，FN表示模型错误预测为负样本的次数，TN表示正确预测为负样本的次数. 根据TPR和FPR则能绘制出接收者操作特征曲线（receiver operating characteristic curve, ROC）. 其中TPR作为纵坐标轴，FPR作为横坐轴.
2） AUC指标. AUC通常用于衡量静态网络链路预测方法的准确性，其表示ROC下的面积，表示模型正确预测为正样本概率大于错误预测为正样本概率的可能性. 假设在数据中有M个正样本和
\ell 个负样本，则共有M×\ell 对样本. 若有M1次出现正样本和负样本预测概率相同，有M2次出现正样本预测概率值大于负样本预测概率值，则AUC定义为AUC=\frac{0. 5{M}_{1}+{M}_{2}}{M\times \ell} . (21) AUC数值越大则表明模型的预测性能越好. 特别地，当AUC=0.5时表明对于不论真实类别是1还是0的样本，模型预测为1的概率是相等的.
3） 错误率ER. ER一般是指模型错误预测的样本数量占总样本数量的比例，是一种通用的性能指标，定义为
ER=\dfrac{\displaystyle\sum_{j=0}^{n}\displaystyle\sum_{i=0}^{n}|{a}_{t;i,j}-{a}_{t;i,j}'|}{Q} . (22) 其中，
{a}_{t;i,j} 表示时刻t标签矩阵中第i行第j列的元素值，{a}_{t;i,j}' 表示时刻t输出矩阵中第i行第j列的元素值，Q代表总链路数，n代表输出维度.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所示.
表 3 AUC评价指标Table 3. AUC Evaluation Metric模型方法 数据集 Infectious HyperText Haggle node2vec 0.5374 0.5921 0.5104 DDNE 0.8975 0.9013 0.9352 E-LSTM-D 0.9418 0.9463 0.9583 E-GRUs-D 0.9367 0.9606 0.9524 注：黑体值表示最优值. 表 4 ER评价指标Table 4. ER Evaluation Metric模型方法 数据集 Infectious HyperText Haggle Node2vec 0.9813 0.9515 0.9712 DDNE 0.4553 0.3340 0.3791 E-LSTM-D 0.2388 0.1528 0.1602 E-GRUs-D 0.2352 0.1473 0.1841 注：黑体值表示最优值. 在表3和表4中，node2vec方法的链路预测准确率远远小于其他方法，这表明相比于用于动态网络链路预测的方法，node2vec并不能很好地学习移动社会网络中节点的链路变化情况. 总体而言，尽管E-LSTM-D模型的预测结果要略优于E-GRUs-D模型，但图6表明，在3种不同数据集下，E-GRUs-D模型的训练时间要远短于E-LSTM-D模型，体现了在相同数据规模下，E-GRUs-D模型在缩短训练时间上的优势.
从实验结果来看，E-GRUs-D模型在不同的网络规模、网络密度中都能够得到较为理想的预测效果，虽然其预测性能略低于E-LSTM-D模型，但是训练时间和计算效率得到显著提高. 此外，当在数据集规模较小的情况下，E-GRUs-D的预测准确率超过了E-LSTM-D模型，该现象符合LSTM和GRU的特性：虽然GRU和LSTM内部均和“门控”这一概念密不可分，但是GRU内部主要由2个门进行运作，而LSTM内部则由3个门进行运作，得益于GRU内部构造的简洁性，在数据集规模较小的情况下，GRU的训练效果会优于LSTM.
不同数据集下的实验结果如图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时，由于提取了过多无用的信息，并且计算量随着层数增多而急剧增加，预测效果反而下降.
2） 输入图序列长度的影响. 一般来说，输入的图序列越长，其中包含的历史信息就越多，模型能更好地学习网络的演变，预测准确率也越高.
然而，实验结果表明如果输入的图序列过长，则其中可能会包含过多不相关的特征，导致资源浪费. 因此，合适的输入图序列长度对于模型的预测性能也至关重要. 本文在各数据集下测试了N从5到15变化时对模型性能的影响，实验结果如图11和图12所示. 对于规模较小的数据集HyperText和数据集Haggle而言，在N取值为11之前，其预测性能随着长度的递增而不断提升，而N取值超过11之后，性能开始降低，这是因为当输入序列过长，模型学习到过多冗余的历史信息. 由于Infectious数据集规模较大，在整个过程中模型性能都随着N的增加而增加，但在N取值为11之后，模型的性能提升幅度减缓，需要注意的是，这种性能缓慢提升需要耗费巨大的模型训练计算量.
4. 结 论
本文提出了一种适用于移动社会网络链路预测的E-GRUs-D模型，该模型的Encoder-Decoder模块能够学习高阶非线性的网络结构，从而降低了隐藏层的计算量，同时将提取的特征重构至先前的维度并映射到目标时刻网络的邻接矩阵中. GRUs模块的复数个GRU串联结构，首先能使模型提取数据的时变特征；其次，和只有1层GRU相比，学习能力更强，有助于提升模型预测性能；而且由于自身结构的简洁性，该方法在缩短训练时间方面要明显优于现有方法；还能通过调整节点数量，适用不同规模的网络，具有良好的可扩展性. 大量的实验表明，对于移动社会网络的链路预测问题，该模型具有较为高效且准确的预测性能.
E-GRUs-D模型和E-LSTM-D模型在相同数据集下，模型性能差距较小，但是由于GRU拥有相对于LSTM较低的模型复杂度，所以在模型训练效率方面更加优秀. 然而，不论是LSTM还是GRU，只是相对于RNN而言，更加能够抑制梯度消失或爆炸，且作为RNN的变体，有着和RNN结构同样的弊端，即无法进行并行计算，所以在数据量不断剧增以及模型体量不断增大的未来，我们的研究将更加注重模型本身的优化，尽可能进一步抑制梯度消失和提高模型运算效率.
作者贡献声明：刘林峰提出指导性意见并修改论文；于子兴提出算法思路和实验方案，完成实验并撰写论文；祝贺负责收集实验数据和完善实验方案.
-
表 1 3种数据集的基本信息
Table 1 Basic Information for the Three Datasets
数据集 参与人数 边数 平均距离/m 最大距离/m 持续天数 HyperText 113 20818 368.5 1483 3 Infectious 410 17298 84.4 294 9 Haggle 274 28202 206.2 2092 4 
下载: 导出CSV
表 2 各数据集下隐藏层节点的数量
Table 2 Number of Hidden Layer Nodes Under Each Dataset
数据集 编码器层 GRUs第1层和第2层 解码器层 HyperText 128 118，118 113 Infectious 128 227，227 410 Haggle 128 185，185 274
下载: 导出CSV
表 3 AUC评价指标
Table 3 AUC Evaluation Metric
模型方法 数据集 Infectious HyperText Haggle node2vec 0.5374 0.5921 0.5104 DDNE 0.8975 0.9013 0.9352 E-LSTM-D 0.9418 0.9463 0.9583 E-GRUs-D 0.9367 0.9606 0.9524 注：黑体值表示最优值.
下载: 导出CSV
表 4 ER评价指标
Table 4 ER Evaluation Metric
模型方法 数据集 Infectious HyperText Haggle Node2vec 0.9813 0.9515 0.9712 DDNE 0.4553 0.3340 0.3791 E-LSTM-D 0.2388 0.1528 0.1602 E-GRUs-D 0.2352 0.1473 0.1841 注：黑体值表示最优值.
下载: 导出CSV
-
[1] Theocharidis A. Network visualization and analysis of gene expression data using biolayout expre3d[J]. Nature Protocols, 2009, 4(10): 1535−1550 doi: 10.1038/nprot.2009.177
[2] York S N. Mobile social network [M] //Encyclopedia of Social Network Analysis and Mining. Berlin: Springer, 2014: 950 − 955
[3] Newman M E J. Clustering and preferential attachment in growing networks[J]. Physical Review E, 2001, 64(2): 025102−025105 doi: 10.1103/PhysRevE.64.025102
[4] Zhou Tao, Lin Yuanlu. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71(4): 623−630 doi: 10.1140/epjb/e2009-00335-8
[5] 胡文斌,彭超,梁欢乐,等. 基于链路预测的社会网络事件检测方法[J]. 软件学报,2015,26(9):2339−2355 doi: 10.13328/j.cnki.jos.004703 Hu Wenbin, Peng Chao, Liang Huanle, et al. Event detection method based on link prediction for social network evolution[J]. Journal of Software, 2015, 26(9): 2339−2355 (in Chinese) doi: 10.13328/j.cnki.jos.004703
[6] Guo Junchao, Shi Leilei, Liu Lu. Node degree and neighbourhood tightness based link prediction in social networks [C] //Proc of the 9th Int Conf on Information Science and Technology. Piscataway, NJ: IEEE, 2019: 135 − 140
[7] Rahman M S, Dey L R, Haider S, et al. Link prediction by correlation on social network [C/OL] // Proc of the 20th Int Conf of Computer and Information Technology. Piscataway, NJ: IEEE, 2017[2021-05-27].https://ieeexplore.ieee.org/document/8281812
[8] Ke-Ke S, Small M, Yan Weisheng, et al. Link direction for link prediction[J]. Physica A:Statistical Mechanics and Its Applications, 2017, 469(1): 767−776
[9] Sun Qiangshang, Hu Rongjing, Zhao Yang, et al. An improved link prediction algorithm based on degrees and similarities of nodes [C] //Proc of the 16th IEEE/ACIS Int Conf on Computer and Information Science. Piscataway, NJ: IEEE, 2017: 13 − 18
[10] Li Jundong, Cheng Keiwei, Wu Liang, et al. Streaming link prediction on dynamic attributed networks [C] //Proc of the 11th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2018: 369 − 377
[11] 王智强,梁吉业,李茹. 基于信息融合的概率矩阵分解链路预测方法[J]. 计算机研究与发展,2019,56(2):306−318 doi: 10.7544/issn1000-1239.2019.20170746 Wang Zhiqiang, Liang Jiye, Li Ru. Probability matrix factorization for link prediction based on information fusion[J]. Journal of Computer Research and Development, 2019, 56(2): 306−318 (in Chinese) doi: 10.7544/issn1000-1239.2019.20170746
[12] Ahamd N M, Ling Chen, Wang Yulong, et al. Deepeye: Link prediction in dynamic networks based on non-negative matrix factorization[J]. Big Data Mining and Analytics, 2018, 1(1): 19−33 doi: 10.26599/BDMA.2017.9020002
[13] Mutinda F W, Nakashima A, Takeuchi K, et al. Time series link prediction using NMF [C] //Proc of the 6th IEEE Int Conf on Big Data and Smart Computing. Piscataway, NJ: IEEE, 2019: 752 − 761
[14] Li Yongli, Luo Peng, Fan Zhiping, et al. A utility-based link prediction method in social networks[J]. European Journal of Operational Research, 2017, 260(2): 693−705 doi: 10.1016/j.ejor.2016.12.041
[15] Lei Kai, Qin Meng, Bo Bai, et al. GCN-GAN: A non-linear temporal link prediction model for weighted dynamic networks [C] //Proc of the 38th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2019: 388 − 396
[16] Hao Shao, Wang Luwen, Jian Deng. A link prediction algorithm by unsupervised machine learning [C] //Proc of the 1st Int Conf on Communications, Information System and Computer Engineering. Piscataway, NJ: IEEE, 2019: 622 − 625
[17] Wang Hao, Shi Xingjian, Yeung D Y. Relational deep learning: A deep latent variable model for link prediction [C] //Proc of the 31st AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2017: 14346 − 14463
[18] 舒坚,张学佩,刘琳岚,等. 基于深度卷积神经网络的多节点间链路预测方法[J]. 电子学报,2018,46(12):2970−2977 doi: 10.3969/j.issn.0372-2112.2018.12.021 Shu Jian, Zhang Xuepei, Liu Linlan, et al. Multi-nodes link prediction method based on deep convolution neural networks[J]. Acta Electronica Sinica, 2018, 46(12): 2970−2977 (in Chinese) doi: 10.3969/j.issn.0372-2112.2018.12.021
[19] Chen Jinyin, Zhang Jian, Xu Xuanheng, et al. E-LSTM-D: A deep learning framework for dynamic network link prediction[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 51(6): 3699−3712
[20] Sett N, Basu S, Nandi S, et al. Temporal link prediction in multi-relational network[J]. World Wide Web-internet & Web Information Systems, 2018, 21(2): 395−419
[21] Kunegis J. The KONECT project[DB/OL]. The University of Namur, [2021-05-27]. http://konect.cc/networks
[22] Han Zhizhong, Liu Zhenbao, Vong C, et al. Deep spatiality: Unsupervised learning of spatially-enhanced global and local 3D features by deep neural network with coupled softmax[J]. IEEE Transactions on Image Processing, 2018, 27(6): 3049−3063 doi: 10.1109/TIP.2018.2816821
[23] Li Taisong, Zhang Jiawei, Phillip S. Yu, et al. Deep dynamic network embedding for link prediction[J]. IEEE Access, 2018, 6: 29219−29230 doi: 10.1109/ACCESS.2018.2839770
-
期刊类型引用(5)
1. 闫钦与，卜凡亮，王一帆. 基于脉冲神经网络优化的动态图链路预测. 科学技术与工程. 2025(04): 1522-1528 . 
百度学术
2. 刘琳岚，冯振兴，舒坚. 基于时序图卷积的动态网络链路预测. 计算机研究与发展. 2024(02): 518-528 . 本站查看
3. 何亚迪，刘林峰. 面向强稀疏性移动社交网络的链路预测深度学习方法. 网络与信息安全学报. 2024(03): 117-129 . 百度学术
4. 李楠，白玉凤. 基于混合神经网络的室内可见光定位方法. 光学技术. 2024(06): 706-712 . 百度学术
5. 张蕾，潘佳兴，魏楚元. 污染排放网络中基于图嵌入的链路预测算法. 计算机仿真. 2024(10): 393-399+447 . 百度学术
其他类型引用(9)
计量
- 文章访问数: 178
- HTML全文浏览量: 36
- PDF下载量: 112
- 被引次数: 14
