链路预测的方法与发展综述

链路预测对网络结构特征的演化趋势进行挖掘有着不可磨灭的促进作用。为了对网络的未来结构变化进行预测，学者们提出了许多算法。综述了4类较为常见的链路预测方法，分别是基于节点属性、基于网络拓扑结构、基于机器学习以及基于最大似然的方法，比较了4类预测方法的优劣，并概述了几种常见的衡量链路预测算法精确度标准。最后总结并展望了链路预测的未来研究方向和发展前景。     

基于复杂网络动力学模型的链路预测方法

链路预测是复杂网络中研究缺失连边和未来形成连边的重要组成部分,当前基于网络结构的链路预测方法成果丰富,而基于复杂网络动力学模型的链路预测研究较少。针对无权无向网络,首先构建了复杂网络动力学模型,然后给出了基于复杂网络动力学模型的链路预测节点中心性的量化评价指标,最后通过给出的节点中心性量化指标,提出了由复杂网络动力学模型定义的链路预测方法。通过在真实网络数据集上进行的实验表明,提出的链路预测方法较基准方法有明显的预测精度的提升。     

基于SkipGram模型的链路预测方法

现有的基于节点相似性的链路预测算法,在提升预测准确度时往往无法兼顾计算复杂度。受自然语言概率图模型在词向量表征上的运用启发,提出一种基于SkipGram模型的链路预测方法。首先提出基于概率的随机游走方法,通过这种方法得到网络节点的采样序列;然后结合SkipGram模型将网络节点映射到一个低维向量空间来降低复杂度;最终以向量间的距离作为衡量网络节点间相似性的指标,进而完成链路预测。通过在6个具有代表性的真实网络中进行实验和比较发现,提出的模型在预测准确度上得到大幅提高。     

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

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

基于神经网络的链路预测算法

针对当前基于网络拓扑结构相似性的链路预测算法普遍存在精确度较低且适应性不强的问题,研究发现融合算法能够有效改善这些问题。提出了一种基于神经网络的融合链路预测算法,主要通过神经网络对不同链路预测相似性指标进行融合。该算法使用神经网络对不同相似性指标的数值特征进行学习,同时采用标准粒子群算法对神经网络进行了优化,并通过优化学习后的神经网络模型计算出融合指标。多个真实网络数据集上实验表明,该算法的预测精度明显高于融合之前的各项指标,并且优于现有融合方法的精度。     

基于网络资源流量的链路预测方法

在复杂网络中,现有基于结构相似性的链路预测方法较少考虑全局和局部拓扑信息之间平衡性、准确度和复杂度之间平衡性以及网络资源动态流动的问题。将网络资源流量作为相似性判断依据,提出一种准局部链路预测方法。根据网络中节点重要性的不同来为它们分配对应的资源,以保证资源分配的合理性。针对网络资源提出一种动态流动机制,将节点对双向流动的资源之和作为相似程度的量化指标。引入节点对之间中间路径节点的概念,分析中间路径节点在资源流动过程中的稀释作用。在此基础上,计算初始资源量和稀释作用量从而得到网络资源流量方法的性能评估指标值。在Jazz、NS等11个真实世界的网络中进行实验,对比该方法与CN、Salton等常见基准方法在准确度和鲁棒性方面的性能表现,结果表明,所提方法能够充分利用准局部信息,既能考虑资源流动性又能解决平衡性问题,可有效提高链路预测性能。     

基于共同邻居惩罚的复杂网络链路预测方法

链接预测是确定用户间关系的基本工具。通过相似性度量进行链路预测是一种常见的方法,提出一种基于相似度的链路预测算法,根据网络结构及拓扑特性来确定相似度,引入优化链路预测度量方法,将聚类系数作为网络结构性质。此外,并考虑共享邻域,得到较其他同类链路预测方法更好的性能。实验结果表明,提出的算法性能优于经典算法。结合在Facebook、Twitter与新浪微博等社交网络环境中的实验结果可知,SLP-CNP法较其他算法具有更优精度与效率。在未来的工作中,还可尝试在所提方法的基础上,提升在加权网络、有向网络和二部网络中的适用性。     

加权好友推荐模型链路预测算法

链路预测是复杂网络的一个重要研究方向。基于节点结构相似性进行链路预测是目前常用的方法。真实网络中存在大量的局部群落结构,针对不同的网络结构构建算法是链路预测的核心问题。利用社交网络好友推荐策略,中介人倾向于将自己更熟悉的人介绍给目标用户,提出了一种节点相似性度量指标。该指标结合局部特征描述并有效区分了用户节点之间影响力的不同,更适用于一类特定的局部群落结构。依据该指标提出的加权好友推荐模型链路预测算法在12个数据集上的实验结果表明,该算法在AUC和Precision两个评价标准上具有明显优势。     

基于信息融合的概率矩阵分解链路预测方法

作为一种典型的网络大数据,社交信息网络如微博、Tweeter等,不仅包含用户间复杂的网络结构,而且包含大量用户所发表的微博/Tweet信息.现有链路预测算法大多只利用单方面的网络拓扑信息或非拓扑信息,仍然缺乏有效融合社交信息网络中拓扑与非拓扑信息的链路预测方法.为此,从社交信息网络中用户的主题角度出发,提出一种融合主题相似信息的链路预测方法.首先基于用户文本内容抽取用户的主题表示,并定义用户间的主题相似度;然后基于用户主题相似度,构建了一种用户主题相似稀疏网络;进一步将用户主题相似网络与用户间关注/被关注网络融合在统一的概率矩阵分解框架下,通过学习获得用户的潜在特征表示和网络链路参数;最终在此概率矩阵分解框架下,基于用户的潜在特征表示和链路参数计算得到用户间的链路可能性.所提出的模型提供了一种融合多种网络信息的通用策略和学习方法.实验在包含网络结构与文本信息的4组微博与推特数据集中显示,所提出的融合概率矩阵分解链路方法相比其他链路预测方法更有效.     

面向科研专网的链路流量预测模型

当今科研活动已越来越依赖科研数据网络的高效传输,这对科研专网的链路资源规划和运行管理带来了更高要求.面向科研专网的实际需求建立链路流量预测模型能使网络运营者在SDN等先进控制转发技术辅助下更有效进行资源调度的快速决策.现有的预测方法未考虑当前网络流量更具多样化和更高复杂度的深层细粒度特征.通过改进LSTM模型,本文面向...     

基于Katz自动编码器的城市路网链路预测模型

城市交通道路网络（以下简称“路网”）是一种特殊的复杂网络,对路网进行链路预测在城市规划与城市结构演化方面有着重要的应用价值。针对路网的高度稀疏性、高度非线性特点,提出了一种基于Katz相似度自动编码器（Katz Auto Encoder Network Embedding,KAENE）的路网链路预测模型,它是一种基于自动编码器的深度学习网络嵌入模型,使用Katz相似度矩阵保存路网的结构特征,利用多层非线性自动编码器对路网进行网络表征学习,在模型训练阶段通过局部线性嵌入损失函数保存路网的局部特征,在此基础上引入L2范数来提高模型的泛化能力,最后结合路网的方向性特征提高路网的链路预测精确度。通过实验对比了KAENE模型与其他链路预测模型在国内外的不同城市路网数据上的表现以及不同嵌入维度对KAENE模型预测精度的影响,最后通过可视化了解了模型的网络表征学习过程。实验结果表明,KAENE在国内外6个具有代表性的路网数据集的链路预测任务中取得了良好的表现。     

基于链路预测的社会网络事件检测方法

网络演化分析与事件检测,是当前社会网络研究的热点和难点.现有的研究工作主要是针对网络提出不同的模型,并用网络特征指标对仿真结果进行评价.这些方法存在如下问题:(1) 每种方法仅针对特定网络,通用性不高;(2) 特征指标多种多样,不同模型的表现情况缺乏统一的评价标准;(3) 未考虑网络演化的时间特性,难以描述网络演化的波动性,无法检测事件.针对上述问题,提出一种基于链路预测的社会网络事件检测方法LinkEvent(由相似性计算算法SimC和事件检测算法EventD组成),它可以对不同网络的波动性进行统一评价,并依此建立事件检测模型.主要工作包括:(1) 证明了链路预测可以反映网络演化机制,相同机制下的模型演化法和链路预测在分析网络演化上具有内在的一致性;(2) 基于链路预测,提出一种网络相似性计算算法SimC(similar computing),并在考虑微观因素的基础上进行改进;(3) 利用相似性计算结果,提出一种事件检测算法EventD(event detecting)检测出新事件.在不同特征的网络上进行实验,结果表明:所提出的LinkEvent方法能够较好地解决网络演化波动性问题,实现事件检测;同时也证明了利用链路预测技术进行网络演化分析的可行性以及相似性计算和事件检测算法的有效性.     

融合拓扑和属性的动态网络链路预测方法

网络数据中出现的大量节点属性和随时间变化的特征,给链路预测提出了新挑战。基于注意力机制和循环神经网络对随时间演化网络进行建模,提出了DTA-LP模型。与传统的静态链路预测算法相比,DTA-LP使用LSTM捕获时序信息,动态预测可以更好应用于现实网络;与基于网络拓扑的动态链路预测算法相比,DTA-LP可以聚集高阶拓扑特征,有效挖掘网络邻域信息;与基于属性网络的动态链路预测算法相比,DTA-LP可以加权融合网络拓扑属性,提高预测精度。在4种真实数据上的实验结果表明,该方法能结合网络已有先验知识,以较高的MAP值来预测未来网络中的边,验证了模型的有效性。     

无标度网络中的链路预测问题研究

研究无标度网络中的链路预测问题。针对人造网络和实际社会网络,分别介绍静态和动态2种链路预测的实现过程,探究利用相似性进行链路预测的可行性,并验证多种相似度计算方法的准确性。对预测结果进行有效性分析,同时根据不同网络特性给出相应的预测算法。     

基于模体的朴素贝叶斯链路预测方法

在具有模体特征的食物链网络、社交网络中,局部朴素贝叶斯（LNB）的链路预测方法通过准确区分每个共邻节点的贡献以提高链路预测的精确度,但忽略了每个共邻节点对所在路径的贡献不同以及网络模体结构对链接形成的作用。针对LNB链路预测方法存在的局限性问题,结合路径模体特征与朴素贝叶斯理论,提出基于模体的朴素贝叶斯链路预测方法。定义模体密度以量化路径结构上模体的聚集程度。考虑路径结构上模体密度对链接形成的影响,构建每条路径的角色贡献函数,以量化每条路径结构的模体特征对节点相似性的影响。在此基础上,根据朴素贝叶斯理论与角色贡献函数推导节点相似性指标。在Football、USAir、C.elegans、FWMW、FWEW和FWFW 6个真实网络上进行实验,结果表明,该方法能有效提高预测性能且具有较优的鲁棒性,其中在具有显著模体特征的FWMW、FWEW、FWFW网络上,相比现有相似性指标中较优的Katz指标,所提相似性指标的AUC值提升了2%~7%。     

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

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

基于模体演化的时序链路预测方法

时序链路预测是动态网络分析的重要组成部分,具有极大的理论和应用价值. 传统的时序链路预测方法往往直接对边的演化规律进行分析,忽略了网络中其他微观结构的演化对链路形成的影响. 基于此分析,本文引入非负张量分解和时间序列分析对网络模体的演化规律进行研究,进而提出一种基于模体演化的链路预测方法. 在三个真实数据集上的实验结果表明,该方法能有效提高链路预测精度.