符号网络链接预测算法研究综述

符号网络链接预测包括网络结构上两个节点间未知链接的可能性预测与符号预测两方面,其相关研究对于分析和理解符号网络的拓扑结构、功能及演化行为具有十分重要的意义,在个性化推荐、态度预测、蛋白质交互作用研究等领域有着重大的应用价值。文中综述了符号网络链接预测问题的研究成果,介绍了相关概念、符号网络的理论基础、常用符号网络数据集以及预测精度评价标准;将目前主要的符号网络链接预测算法按照设计思路分为有监督学习与无监督学习两大类,详细阐述了每种算法的主要思想;归纳总结了符号网络链接预测问题的特点和规律,讨论了目前存在的问题并指出了面临的挑战和未来可能的发展方向。这能为信息学、生物学、社会学等领域的相关研究人员提供有益参考。     

符号社会网络中正负关系预测算法研究综述

一些网络中的边根据其潜在涵义可分为正关系和负关系,若用正号和负号来标记网络中的边,则形成一个符号网络.符号网络的应用场景非常丰富,在社会学、信息学、生物学等多个领域广泛存在,逐渐成为当前研究的热点之一.对符号社会网络中链接的正负预测问题进行研究,其成果对社会网络的个性化推荐、网络中异常节点的识别、用户聚类等都具有非常重要的应用价值.主要介绍符号社会网络中正负关系预测问题在国内外的研究现状和最新进展.首先介绍了社会结构平衡理论和地位理论,并将目前主要的预测算法按照设计思路分成两类:基于矩阵的符号预测算法和基于分类的符号预测算法,详细介绍各类算法的基本思路,并从算法效率、准确性和可伸缩性等角度进行详细的对比和分析,总结了符号社会网络预测问题具有的一些特点以及所面临的挑战,同时指出未来可能的发展方向,为相关研究人员提供有价值的参考.     

联合社区和影响节点的通用可扩展的链接预测

针对相似度预测算法无法同时嵌入局部和全局信息并提高运行速度等问题,融合社区发现和影响节点识别技术提出一个通用可扩展的链接预测模型。对网络进行社区划分,分别计算局部共邻节点的社区参与度和全局影响力得分,集成到统一的相似度框架中。为验证算法的有效性和可扩展性,给出在加权和无权下多个局部密集结构和影响节点识别指标的定义。在真实数据集上的实验结果表明,提出方法可快速实现通用可扩展性的预测任务,结果也普遍优于基准算法。     

基于端到端分布式框架的符号网络预测方法

社交网络中的链接关系根据其潜在含义可分为正关系和负关系。若对网络中的链接关系进行正负标注,则可形成一个符号网络。符号网络在社会学、信息学、生物学等多个领域存在广泛应用。针对符号网络中链接关系的正负预测已经成为当前研究的热点之一。在大数据背景下,随着符号网络规模的日益增大,符号预测算法的可伸缩性问题日益突出。一些研究者提出了分布式环境下的符号预测方法,使得算法的可伸缩性问题部分得到缓解。但由于大多数算法采用了服务器-客户端方式的分布式框架,导致问题并没有得到根本上的解决。本文提出了一种新的端到端分布式框架（Client to Client Distributed FrameWork,简称C2CDF）,相比传统服务器-客户端架构的集中通信模式,C2CDF各个节点间地位平等,不存在集中通信,集群的带宽瓶颈和压力大大减轻。通过在社交网络正负符号预测、广告点击率预测及森林类型预测等三个不同真实数据集上的实验证明,C2CDF能够在拥有更高准确性的同时,获得2.3-3.3倍的加速比,而且拥有良好的泛化性,不仅能应用在社交网络正负符号预测方面,也能作用于广告点击预测等其他领域。     

基于节点地位和相似性的社交网络边符号预测

边符号预测即根据网络拓扑结构挖掘符号相关隐含信息,旨在揭示用户之间的潜在关系。节点地位和相似性能够较好地体现边符号属性,为改善预测效果提供了理论基础。通过探究二者与边符号属性之间的强相关性,建立符号预测模型。首先,利用排序算法prestige评估用户节点的社会地位,同时使用余弦相似度表示用户的社交偏好;然后,在逻辑回归学习模型的基础上融合二者建立边符号预测模型LR-SN;最后,在模型训练过程中采用随机梯度上升算法优化求解。三个真实网络数据集的实验结果表明,相比于现有基准方法,LR-SN模型的符号预测准确率显著提高且具有一定的推广性,说明通过融合局部信息与全局信息能够进一步改善预测效果。     

符号网络的局部标注特征与预测方法

当复杂网络的边具有正、负属性时称为符号网络。符号为正表示两用户间具有相互信任（朋友）关系,相反,符号为负表示不信任（敌对）关系。符号网络中的一个重要研究任务是给定部分观测的符号网络,预测未知符号。分析发现,具有弱结构平衡特征的符号网络,其邻接矩阵呈现全局低秩性,在该特征下链路符号预测问题可以近似表达为低秩矩阵分解问题。但基本低秩模型中,相邻节点间符号标注的局部行为特征未得到充分利用,论文提出了一种带偏置的低秩矩阵分解模型,将邻居节点的出边和入边符号特征作为偏置信息引入模型,以提高符号预测的精度。利用真实符号网络数据进行的实验证明,所提模型能够获得较其他基准算法好的预测效果且算法效率高。     

融合多元影响力节点识别指标MPR的链接预测

多元网络通常是指节点之间存在多种维度链接关系的图结构.多元网络链接预测算法在构建相似度指标时,多数仅考虑单一维度网络的拓扑结构属性,未挖掘不同维度子网络之间存在的关联,影响链接预测的效果.针对该问题,提出一种基于多元全局节点影响力识别指标MPR的多元网络链接预测算法.通过定义一个多维度节点影响力排序指标MPR,度量多元网络空间中影响力较大的节点,并把影响力排名函数转化为潜在节点对之间的相似度得分,从而应用到多元网络链接预测场景中.在2个真实多元网络数据集上的实验结果表明,该算法的预测效果优于PR、EDC、ANC等对比算法,且具有较好的稳定性.     

基于投影的二分网络链接预测

提出基于投影的二部网络链接预测算法。算法首先将二部图投影为一个单部图,在此基础上定义了潜在边的概念,使得对二分网络链接的预测仅在潜在边中进行,大大降低了预测算法的复杂度。定义了潜在边所覆盖的模式以及模式的权重,通过潜在边所覆盖的模式的权重来计算潜在边的可信度,并将其作为该潜在边上存在实际链接的评分。实验结果表明,所提算法能够有效地提高链接预测的速度和结果的精度。     

基于低秩和局部约束矩阵估计的链接预测方法

在大数据时代,互联网社会网络和其他复杂网络中的链接预测问题研究成为热门领域。链接预测相关的方法已被广泛地应用于社会网络关系挖掘、个性化推荐和生物制药等领域。在链接预测问题中,通常使用相似性矩阵来表示网络中任意节点之间存在链接的可能性,因此相似性矩阵的计算是链接预测中至关重要的一步。近年来的研究中,大多数方法是基于已知网络中数据的分析,通过网络潜在结构设计机器学习算法构造相似性矩阵。在全局低秩的网络结构假设下,结合网络中节点特征的局部约束,提出了一种基于数据的链接预测优化算法,并针对复杂网络数据链接预测问题设计了可扩展的分治方法,便于分布式环境中对大规模数据进行求解。通过在多个真实数据集上的实验和结果分析,基于低秩结构和局部约束矩阵估计的链接预测分治方法能够取得较好的效果,并对复杂的网络结构数据具有较强的可扩展性。     

基于节点表示和子图结构的动态网络链接预测

动态链接预测的关键是建模网络动态性和抽取局部结构特征.为此,文中提出基于节点表示和子图结构的动态链接预测方法.为了建模节点的动态演化特性,引入节点向量模型,按序拼接各个历史快照的节点表示.为了建模链接的局部子图结构信息,引入图同构算法,编码局部子图的拓扑结构.最终目标链接的特征表示融合每个历史快照中目标节点对的向量表征和局部子图的拓扑结构.实验表明文中方法性能较优.     

相似性特征对链路预测的影响与增强

链路预测的主要任务是设计一个能够更加准确地描述给定网络机制的预测算法,从而得到更准确的预测结果。在分析现有研究成果基础上发现,网络的相似性特征对采用的链路预测方法有较大的影响：在节点间标签相似性较低的网络中,提高标签的相似性可以提高预测的准确性;而在节点间标签相似性较高的网络中,则应更加关注结构信息对于链路预测的贡献来提高预测的准确性。随后,通过对标签进行加权处理,提出带权值的标签相似性算法,在低相似性网络中能够提高链路预测的准确性。同时,在较高相似性网络中,将网络的结构信息引入到节点的相似性计算中,并通过偏好链接机制来提升链路预测的准确性。在四个真实网络上的实验结果表明,所提算法相对于标签系统间的余弦相似性（CSTS）算法、偏好链接（PA）等算法取得了最高的准确率。根据网络相似性特征,采用所提出的对应算法进行链路预测能够得到更准确的预测结果。     

基于节点亲密度的链路预测算法

链路预测作为复杂网络分析的一个重要分支,在不同领域中有着广泛的应用。现有的链路预测算法通常根据共同邻居节点的结构信息来度量节点对之间的相似性,忽略了节点对与其共同邻居节点之间的连接紧密程度。针对此问题,提出了一种基于节点亲密度的链路预测算法。该算法利用边聚集系数来测量节点对与其共同邻居节点之间的紧密程度,以AUC值作为链路预测的精确度评价指标。在4个真实网络上的实验结果表明,相比于其他相似性算法,所提出的算法提高了链路预测的预测精度。     

基于K-shell分解与邻居节点度去噪的链路预测方法

链路预测是研究复杂网络结构和演化机制的重要工具,提高链路预测的精度具有重要价值。针对传统的基于网络拓扑结构相似性算法预测精度偏低的问题,从网络优化去噪的角度进行分析,提出了一种基于K-shell分解与邻居节点度（KSDNN）去噪的链路预测方法。该方法首先从全局的角度通过K-shell分解对复杂网络中所有节点进行重要性排序,然后从局部的角度结合节点邻居节点的度对节点重要性进行综合评判,最后对网络数据进行优化后进行链路预测。通过在四个不同的真实网络进行验证,实验结果表明,所提方法预测精度优于K-shell去噪的方法,且相较于传统算法预测精度平均提升了2%左右。     

基于拓扑稳定性的有向网络链路预测方法

作为复杂网络研究的热门方向,有向网络链路预测旨在挖掘网络中未知的连边。网络演化机制是许多链路预测方法的理论来源和依据。现有有向相似性指标计算节点间存在连边的可能性时,忽略了实际网络演化过程中节点自身拓扑稳定性和网络结构稳定性。基于此,提出了基于拓扑稳定性的预测方法。该方法首先计算趋于稳定的节点对之间的相似度,然后计算预测节点对之间的拓扑稳定性。在三个衡量标准AUC、precision和排序分下,九个真实网络中的实验分析表明,提出方法具有较高的预测精度。     

一种时序有向网络中的链路预测方法

真实网络大多是有向的，且网络结构随时间动态变化，传统的链路预测方法大多适用于无向网络，其分析方法不能有效挖掘真实网络中的信息。针对以上问题，提出了一种基于归一化AA和LAS的时序有向的链路预测算法，该算法基于共同邻居、节点度属性及局部社团相似性，为每个链接分配时间影响因子并将其引入NALAS指标进行计算，考虑了网络有向性和网络历史结构的影响。在真实社会网络数据集上对该算法进行了仿真并与Salton、Jaccard等算法进行对比。结果表明，提出的算法与其他算法相比，预测精度得到了提高，说明该算法可以有效地在时序有向的社会网络中进行链路预测。     

移动社交网络中基于网络中心度的链路预测方法*

移动社交网络中的链路预测是指通过已知的网络节点以及移动社交网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性。基于网络中心度的思想,提出一种适用于移动社交网络的链路预测算法。在该算法中,根据节点网络中心度和共同邻居数来计算两个节点的相似性指标,两个节点的共同邻居数越多、共同邻居的网络中心度越高,则两个节点的相似度越高。另外,由于移动社交网络的动态性特征,还将考虑时间因素对预测结果的影响。将该方法与其他4种常用的链路预测方法进行比较,实验结果显示所提方法要优于其他方法。     

基于矩阵分解的DeepWalk链路预测算法

现有的链路预测方法的数据来源主要是基于邻居、路径和随机游走的方法,使用的是节点相似性假设或者最大似然估计,尚缺少基于神经网络的链路预测研究。基于神经网络的一些研究表明,基于神经网络的DeepWalk网络表示学习算法可以更加有效地挖掘到网络中的结构特征,已有研究证明DeepWalk等同于分解目标矩阵。因此,提出了一种基于矩阵分解的DeepWalk链路预测算法（LPMF）。该算法首先基于矩阵分解的DeepWalk算法分解得到网络的表示向量;然后通过余弦相似度计算每对节点之间的相似度,构建目标网络的相似度矩阵;最后利用相似度矩阵,在三个真实的引文网络中进行链路预测实验。实验结果表明,提出的链路预测算法性能优于现存的20余种链路预测算法。这充分表明了LPMF能够有效地挖掘网络中节点之间的结构关联性,而且在实际网络的链路预测中能够发挥出较为优异的性能。     

信息熵改进主成分分析模型的链路预测算法

针对传统的链路预测在不同结构特征的网络中的计算结果不稳定的问题,提出了基于信息熵改进主成分分析（PCA）模型的链路预测算法。首先,用随机森林（RF）确定7个相似性指标作为最佳特征集合;然后,将七个相似性指标组合在一起提出基于信息熵改进PCA的特征信息融合模型,在对特征信息赋予权重后,把该模型与单机制算法结合后在6个真实数据集上验证其正确性以及校验效果;最后,通过与混合链路预测算法比较曲线下面积（AUC）值来验证基于所提模型的链路预测算法的可行性和有效性。实验结果表明,所提出的链路预测算法比有序加权平均算法（OWA）和集成模型链路预测算法（EMLP）在预测精度AUC值上分别提升了2.5~12.46个百分点和0.47~9.01个百分点,具有较好的稳定性和准确性。可见,将所提算法应用到不同结构特征的网络中能得到更稳定、更准确的链路预测结果。