基于门控循环单元的移动社会网络链路预测方法_刘林峰.pdf

基于门控循环单元的移动社会网络链路预测方法刘林峰于子兴祝贺（南京邮电大学计算机学院南京210023）（）A Link Prediction Method Based on Gated Recurrent Units for Mobile SocialNetworkLiuLinfeng,YuZixing,andZhuHe（College of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210023）AbstractLinkpredictionisdefinedasthepredictionofpotentialrelationshipsbetweennodesinthefuturebasedontheknownnetworktopologyandthenodeinformation.Linkpredictioncanhelpreduceresourceexpenditureandallocateresourcesmorereasonablyinvariousapplicationsincludinglinks.Mobilesocialnetworkisakindofdynamicnetwork,anditsstructureisalwaysevolvingwiththeappearanceanddisappearanceofnodesandlinksovertime.Accordingtothecharacteristicsofthemobilesocialnetwork,thecurrentexistingresearchesusemoresophisticatedmodeltoanalyzetherelationshipbetweenthelinks,howevercomplexmodelsnotonlyhavelargespacecomplexitybutalsoareeasytooverfittingproblem.Inordertosolvetheaboveproblems,agatingcycleunitbasedonthepredictionmethodofmobilesocialnetworklinkisputforward.Firstly,theinputdatasetissortedandfiltered,andthetargetnetworkisdividedintosnapshotgraphsandtransformedintoadjacencymatricestoformasampleset.Then,theprediction model is constructed based on the auto encoder and the gated recurrent units to extract the temporalcharacteristicsofmobilesocialnetwork.BasedonKONECTdataset,theexperimentalresultscomparedwithothermodels show that the proposed method can improve the training efficiency by 49.81%,while the predictionperformancecanbemaintained.Key wordsdeeplearning；linkprediction；mobilesocialnetwork；gatedrecurrentunits；autoencoder摘要链路预测是指通过已知的网络拓扑和节点信息来预测未来时刻节点之间的潜在关系，链路预测能够帮助在各种存在链路的应用领域更加合理地分配资源、降低资源开销.移动社会网络属于动态网络的一种，其网络结构总是随着节点和链路的出现、消失以及时间推移而不断演变.针对移动社会网络的特点，当前已有的研究使用愈加复杂的模型来分析链路之间的联系，然而复杂的模型不但空间复杂度大而且容易造成过拟合问题.为了解决以上问题，提出一种基于门控循环单元的移动社会网络链路预测方法.首先对输入数据集进行排序筛选，将目标网络划分为快照图，并按一定的规则转化为邻接矩阵形成样本集，然后基于自动编码器和门控循环单元构建预测模型，提取出移动社会网络的时间变化特征.在 KONECT 数据集上，与其他模型的对比实验结果表明，该方法能够保持预测性能几乎不变的情况下，使模型训练效率提升 49.81%.关键词深度学习；链路预测；移动社会网络；门控循环单元；自动编码器中图法分类号TP393收稿日期：2021-04-30；修回日期：2022-04-24基金项目：国家自然科学基金项目(62272237，61872191)；江苏省“六大人才高峰”高层次人才项目(2019-XYDXX-247)ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(62272237,61872191)andtheSixTalentsPeakProjectofJiangsuProvince(2019-XYDXX-247).计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202110432JournalofComputerResearchandDevelopment60（3）：705716，2023随着时代的进步，网络的概念逐渐多元化，衍生出如互联网、物联网、经济网络、生物网络等各种网络形式.在现实世界中，网络扮演着重要的角色，网络可以将现实世界中的具体问题抽象描述为一个复杂的网络系统.网络可以分为静态网络和动态网络2 类，现实世界中绝大多数网络都属于动态网络，这些网络中的节点、链路都会随着时间的推移而消失或出现.此外，网络中链路代表着不同实体之间产生的行为或者偏向，所以分析并预测这些网络中的链路具有重要的意义.网络的链路预测通常是指预测网络中节点之间的潜在关系，如何提高预测性能一直是网络科学的一个挑战.性能优异的链路预测方法能够更好地理解网络的演变，从网络中提炼出更有价值的信息，比如蛋白质相互作用网络中1，酵母菌与蛋白质之间80%的相互作用不为人知，如果在已知网络结构的基础上设计足够精确的链路预测方法再进行预测指导实验，就能够提高实验成功率、降低测试成本.移动社会网络2是一种典型的动态网络，如果将网络映射到图中，则节点代表人或实体，链路代表节点间的联系.由于这种联系具有时间特征，所以导致了网络的高度动态性和复杂性.移动社会网络的链路预测可以预测人与人之间的交互，分析这种交互可以一定程度上得知一个人的交往或性格倾向，甚至能够判断该用户可能需要的服务.比如出租车司机可以更加容易在合适的地点找到乘客，陌生人之间更容易找到意气相投的朋友，卖家能够更加精准地为买家提供他们所需的商品.精准的链路预测能够为移动社会网络降低资源开销，给人们的生活带来极大的便利.图 1 为一个移动社会网络示意图，比如在道路上用户通过蓝牙或车载局域网络进行通信，在小区里人们使用智能设备接入 WiFi 信号点进行信息交互，也可以通过无线信号接入互联网并连接服务器，由服务器来控制用户之间的通信.1相关工作链路预测的目的在于根据网络的历史信息来预测未来的网络结构，这可以更好地理解网络的演变，发掘网络中有价值的信息.目前，链路预测方法主要分为 3 种：基于节点相似性的链路预测方法、基于矩阵分解的链路预测方法、基于机器学习的链路预测方法.1.1基于节点相似性的链路预测方法基于节点相似性的链路预测方法是指基于网络中节点的结构信息、属性信息和行为去评估节点间的相似度，若节点间的相似度越高，则表明该对节点越相似，即产生链路的可能性越大.目前广泛应用于静态网络的链路预测指标有很多，例如共同邻居算法（commonneighbors,CN）3、资源分配指标（resourceallocationindex,RA）4.在此基础上，文献 5 基于节点相似性算法和事件检测算法提出一种社会网络事件链路预测方法，该方法对不同网络的演变性进行统一评价，并依此建立事件检测模型，并利用该模型完成链路预测.文献 6 提出了基于节点度和聚类系数的共同邻居紧密度指数，认为节点的共同邻居之间的关系越紧密，节点间连接的可能性就越高.文献 7 考虑了用户活动和其共同的邻居，并定义了局部和全局链路预测算法对节点之间的相似度进行评估.文献 8 重点关注了链路方向在链路预测问题中的作用，认为双向链路可能包含更多的网络信息，并发现具有双向链路的小部分节点更有可能通过双向链路连接到共同的邻居.文献9 认为现有的计算节点相似度方法中公共邻居的数量只描述了一种定量关系，没有考虑给定网络的拓扑结构，于是引入节点度的概念和社区结构的思想，提出了局部亲和结构，然后与其他相似度指标在不同网络中进行实验，最终提高了链路预测精准度.文献 39 中的预测方法主要在拓扑变化缓慢或发生变化较少的网络中性能较好，因此当应用场景中网络结构随时间频繁发生变化时，预测效果大大削弱.1.2基于矩阵分解的链路预测方法基于矩阵分解的链路预测方法是指利用矩阵分互联网Fig.1Examplediagramofmobilesocialnetwork图1移动社会网络示意图706计算机研究与发展2023，60（3）解得到的低秩矩阵来解决链路预测问题.其中，矩阵通常由邻接矩阵或提取的其他网络结构信息矩阵组成.目前，矩阵分解主要有奇异值分解、非负矩阵分解和概率矩阵分解.文献 10 提出了一种动态网络的链路预测方法，该方法从第一张网络快照中得到特征矩阵，并求解其低秩矩阵.然后，根据后续网络快照不断更新低秩矩阵，最终利用差值估算未来时刻节点之间链路的可能性.文献 11 指出，现有的链路预测算法缺乏对社会信息网络中的拓扑信息和非拓扑信息的有效融合，因此基于用户主题信息定义了用户主题相似度指数，并基于该指数构造主题相似度矩阵，然后将目标网络的信息和主题相似度矩阵融合到概率矩阵分解框架中，并在此基础上得到网络节点的表示，最后根据得到的隐含特征表示计算网络节点之间产生链路的概率.文献 12 将动态网络结构随时间变化的特性融合到非负矩阵分解中，提出了一种非负矩阵分解迭代规则，然后根据矩阵分解的结果得到网络的相似度矩阵，从而完成了链路预测.文献 13 采用非负矩阵分解的方法提取了时间序列图的潜在特征，采用 Holt-Winters 时间序列预测方法学习，并提取潜在特征的时域信息，以此较好地解决了链路预测问题.基于矩阵分解的链路预测方法主要是对网络的邻接矩阵进行低秩分解，通过迭代分解矩阵，提取动态网络的时变特征.然而在大规模动态网络中，迭代矩阵分解会导致极高的时间复杂度，会增加系统的响应时间和影响用户的使用体验.1.3基于机器学习的链路预测方法基于机器学习的预测方法是指利用机器学习算法从一定角度提取网络中数据的特征，从而实现链路预测.文献 14 考虑到个体偏好可能是形成链路的主要原因，将效用分析概念引入到链路预测问题中，并关注了链路形成过程中潜在变量的演变过程.由此，将链路预测问题定义为一个带有潜在变量的机器学习过程，并采用期望最大化算法来解决链路预测问题.文 献 15 应 用 图 卷 积 网 络（graphconvolutionalnetwork,GCN）、长 短 期 记 忆 网 络（long short-termmemory,LSTM）和生成对抗网络（generativeadversarialnetwork,GAN）提取加权动态网络中链路变化的非线性特征，并利用 GCN 获取每个快照的局部特征，然后利用 LSTM 来提取动态网络的演化特征，以此提高了预测模型的准确性.文献 16 针对单链链路预测指标普适性较差的问题，提出了一种基于密度峰值聚类的自适应链路预测方法.该方法采用不同