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

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

基于聚类分析的复杂网络链路预测性能研究

链路预测问题是复杂网络中数据挖掘领域的重要研究方向,然而复杂网络的结构与预测方法性能之间关系却很少受到关注。从聚类分析的角度探讨复杂网络结构对现有基于相似性度量的六种链路预测方法的性能影响,通过对合成复杂网络和真实复杂网络的对比实验进行分析。结果表明：随着聚类簇的增加,这六种方法在预测精度方面的性能均得到了极大的提升。对于具有较低聚类簇的稀疏复杂网络,叠加随机游动（SRW）预测性能表现最佳,而对于具有较高聚类簇的密集复杂网络,资源分配指数（RA）预测性能表现最佳。因此,对于不同类型的复杂网络应采用不同的方法进行链路预测。     

基于改进AdaBoost算法的复杂网络链路预测

链路预测是复杂网络的重要研究方向,当前的链路预测算法因可利用的网络信息有限,导致预测算法的精确度受限。为了提高预测算法的性能,采用改进的AdaBoost算法进行链路预测。首先根据复杂网络样本建立邻接矩阵,完成样本的矩阵化处理;然后采用AdaBoost算法进行分类训练,通过权重投票获取预测结果;最后,考虑到复杂网络弱分类器预测正负误差分布的不均衡问题,设置权重调整因子η及其调整范围[η1,η2],并根据η值动态调整AdaBoost算法的多个弱分类器分类结果的权重,从而获得准确的链路预测结果。实验结果证明,相比其他常用网络链路预测算法及传统AdaBoost算法,改进的AdaBoost算法的预测准确率优势明显,且在节点数量较多时,其预测时间性能和其他算法的差距较小。     

基于复杂网络节点重要性的链路预测算法

提升链路预测精度是复杂网络研究的基础问题之一,现有的基于节点相似的链路预测指标没有充分利用网络节点的重要性,即节点在网络中的影响力。针对以上问题提出基于节点重要性的链路预测算法。该算法在基于局部相似性链路预测算法的共同邻居（CN）、Adamic-Adar（AA）、Resource Allocation（RA）相似性指标的基础上,充分利用了节点度中心性、接近中心性及介数中心性的信息,提出考虑节点重要性的CN、AA、RA链路预测相似性指标。在4个真实数据集上进行仿真实验,以AUC值作为链路预测精度评价指标,实验结果表明,改进的算法在4个数据集上的链路预测精度均高于共同邻居等对比算法,能够对复杂网络结构产生更精确的分析预测。     

基于拓扑相似和XGBoost的复杂网络链路预测方法

为了提高复杂网络链路预测的性能,采用拓扑相似和XGBoost算法来完成复杂网络链路预测.利用复杂网络拓扑结构建立邻接矩阵,求解共同邻居集合,然后根据拓扑相似理论计算复杂网络相似得分函数,将各个时间窗的得分函数和权重参数作为输入,采用XGBoost算法实现复杂网络的链路预测.通过差异化设置XGBoost算法的两个正则化系数,测试其对链路预测准确率的影响,获取最优正则化系数,从而得到稳定的XGBoost链路预测模型.实验证明,时间窗数量设置合理的情况下,相比常用网络链路预测算法,基于拓扑相似和XGBoost算法的预测准确率优势明显,且预测时间性能和其他算法的差距较小,尤其适用于大规模的复杂网络链路预测.     

MapReduce 环境下的并行复杂网络链路预测

为使链路预测应用于大型复杂网络,设计并实现了一种基于MapReduce计算模型的并行链路预测算法,包含了9种基于局部信息的相似性指标,在稀疏网络上的时间复杂度为O(N).首先,在公共数据集上验证了并行算法的有效性,随着抽取因子的增加,召回率升高而准确率下降.在不同类型的10个大规模复杂网络数据集上的实验结果表明,基于MapReduce计算模型的并行链路预测算法比传统算法具有更高的效率,算法的运行时间随着并行程度的增加而下降.提出并证明了AUC(area under a receiver operating characteristic curve)评价指标的上下界,实验表明,上下界的中值和实际AUC值很接近,并且AUC评价指标侧重于预测分数值是否为0而不是分数值的大小.在网络拓扑性质中,平均聚集系数对AUC值的影响最大,并且AUC值随着网络平均聚集系数的增加而提高.     

从信息学的角度分析复杂网络链路预测

链路预测作为复杂网络分析的一项重要任务,其目的是寻找节点间缺失(新)的链路,识别虚假交互,对于挖掘和分析网络的演化,重塑网络模型具有重要意义.传统的链路预测方法多数采用拓扑结构信息、节点的属性信息和图的结构特征.应用这些特征等外部信息可以得到很好的预测效果.本文从信息学的角度全面分析、回顾和讨论了复杂网络链路预测的发展现状,提出了链路预测技术和问题的系统分类.首次将分层的思想引入链路预测分类体系中,把当前的链路预测方法分为基于监督学习的技术、基于半监督学习的技术、基于无监督学习的技术和基于强化学习的技术.对每种技术的优缺点、复杂性、所使用的具体特征,开源实现及应用建议进行了详细的分析.最后,讨论了当前复杂网络链路预测技术未来的发展方向.     

基于混合深度学习的复杂网络链路预测研究

针对复杂网络链路预测受到网络性质的影响,从而降低复杂网络链路预测效果,提出基于混合深度学习的复杂网络链路预测方法.利用复杂网络在运行过程中的链路变化情况,综合考虑复杂网络历史信息对链路的影响系数,得到了RA指数、AA指数和CN指数等相似指数,基于混合深度学习的反向传播流程,分析复杂网络链路隐藏层的状态,利用复杂网络隐藏层的输出,预测出复杂网络链路输出值,将相似性指标作为复杂网络链路预测的训练样本,构建复杂网络链路预测模型,利用模式分类方法实现多个网络节点之间的链路预测.实验结果表明,基于混合深度学习的复杂网络链路预测方法将时间窗口设为360秒和180秒、样本维度为500和600时,预测效果是最好的,且预测精度较传统方法的预测精度高.     

基于统一描述网络结构模型的链路预测方法

面向网络链路预测的随机分块模型和层次结构模型利用全概率思想计算节点对之间的链路形成概率,但无法有效利用从宏观、中观网络结构到微观低阶环或模体结构中的重叠结构信息,导致链路预测结果的准确率较低。根据笛卡尔积和幂集等概念,借鉴随机分块模型和层次结构模型思想,构建一种对层次结构信息、重叠结构信息和微观结构信息进行统一描述的网络结构模型（USI）。基于USI模型提出一种链路预测方法,依据网络结构信息给出USI模型中的集合划分,利用最大似然估计法计算节点对之间的链路形成概率,最终根据概率并联策略得到链路预测结果。实验结果表明,与基于节点相似性的经典链路预测方法相比,该方法在LT、ER、OP网络数据集上的AUC值提升了0.075~0.143,具有更高的链路预测准确性,并且验证了网络规模对链路形成具有一定的影响。     

基于拓扑连接紧密度的相似性链路预测算法

许多链路预测方法仅仅关注预测的准确度衡量指标,忽略了精确度衡量标准在实际应用中的重要作用,且没有考虑共同邻居与预测节点间紧密度对相似性刻画的影响。针对上述问题,提出了一种基于拓扑连接紧密度的相似性链路预测算法。该方法通过局部拓扑结构定义共同邻居紧密度,并引入参数调节不同网络中紧密程度,最终刻画网络节点间的相似度。6个实际网络测试表明,相比共同邻居（CN）、资源分配（RA）、Adamic-Adar（AA）、局部路径（LP）、Katz等相似性指标,该算法提升了链路预测的预测精度。     

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

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

基于密集连接卷积神经网络的链路预测模型

现有的基于网络表示学习的链路预测算法主要通过捕获网络节点的邻域拓扑信息构造特征向量来进行链路预测，该类算法通常只注重从网络节点的单一邻域拓扑结构中学习信息，而对多个网络节点在链路结构上的相似性方面研究不足。针对此问题，提出一种基于密集连接卷积神经网络（DenseNet）的链路预测模型（DenseNet-LP）。首先，利用基于网络表示学习算法node2vec生成节点表示向量，并利用该表示向量将网络节点的结构信息映射为三维特征数据；然后，利用密集连接卷积神经网络来捕捉链路结构的特征，并建立二分类模型实现链路预测。在四个公开的数据集上的实验结果表明，相较于网络表示学习算法，所提模型链路预测结果的ROC曲线下方面积（AUC）值最大提高了18个百分点。     

基于有效路径拓扑稳定性的链路预测方法

许多链路预测方法来源于复杂网络中路径上的资源传输过程,但缺少考虑路径周围结构的拓扑稳定性,使得路径上的资源传输有效性不高。针对此问题,提出了基于有效路径拓扑稳定性的链路预测方法。该方法首先利用路径两端节点间所有共同邻居的聚类系数量化路径周围结构的拓扑稳定性;然后再利用两端节点的度和共同邻居个数量化预测节点间二阶路径上的双向资源传输有效性;最终结合量化的拓扑结构稳定性和资源传输有效性定义有效路径拓扑稳定性指标。通过九个网络仿真表明,提出的指标具有较高的预测精度与良好的鲁棒性。     

基于聚类信息和对称非负矩阵分解的链路预测模型研究

现有的大部分基于非负矩阵分解的链路预测方法仅考虑网络拓扑结构信息而忽略节点与链接聚类信息.针对此问题,提出一个融合聚类信息的对称非负矩阵分解的链路预测模型.首先,该模型利用对称非负矩阵分解去捕获网络节点相似度信息;其次,使用基于Jaccard的节点和链接聚类系数去保持网络局部结构信息;最后,启用拉格朗日乘法规则去学习模型参数.在六个真实无向无权和四个加权网络上的实验结果表明,该方法在两种不同类型网络预测精确度分别提升了1.6％和8.9％.     

基于共同邻居邻域拓扑稠密性加权的链路预测方法

链路预测旨在利用已知的网络节点和拓扑结构信息,预测网络中未连接的两个节点之间存在连边的可能性。基于网络拓扑相似性的链路预测方法计算复杂度低且预测效果好,但现有的相似性指标对共同邻居的邻域拓扑信息考虑较少。针对此问题,提出一种基于共同邻居邻域拓扑稠密性加权的链路预测方法。首先,基于邻域拓扑相对稠密指数量化节点的邻域拓扑结构;然后,利用共同邻居的节点度和邻域拓扑相对稠密指数刻画共同邻居及其邻域拓扑的相似性贡献;最后,提出基于共同邻居邻域拓扑稠密性加权的节点相似性指标。在多个实际网络数据上的实验结果表明,与现有相似性指标相比,该方法能够取得更高的预测精度。     

基于高阶自包含协同过滤的有向网络链路预测

针对大部分现存有向网络链路预测方法仅关注有向局部结构及互惠链接信息而忽略有向全局结构的问题,提出高阶自包含协同过滤(HSCF)链路预测框架。首先,利用随机游走方法计算高阶相似度矩阵去保持有向网络的高阶路径信息;其次,将高阶相似度矩阵与协同过滤方法相融合构建HSCF框架;最后,把所提框架分别与有向共同邻居(DCN)、有向Adamic-Adar(DAA)、有向资源分配(DRA)和势能理论Bifan 4个典型有向结构相似度相融合,并由此提出HSCF-DCN、HSCF-DAA、HSCF-DRA和HSCF-Bifan 4个有向网络预测指标。在10个真实有向网络上的实验结果表明,与基准指标相比,HSCF-DCN、HSCF-DAA、HSCF-DRA和HSCF-Bifan的受试者工作特征（ROC）曲线下方面积（AUC）值分别平均提高了8.16%、8.85%、9.64%和10.33%,且F分数值分别平均提高了66.62%、68.32%、68.95%和76.18%。     

基于用户复杂网络特征分类的协同过滤模型

协同过滤算法被广泛应用的同时一直存在着伸缩性和可扩展性困难的问题。针对该问题,提出了一种基于用户复杂网络特征分类的推荐系统协同过滤模型。首先,在用户集中基于度值选择特征用户,建立相似性阈值实现非特征用户分组;然后,构建用户—用户相似性网络,通过K-core分解完成网络中的社区标记;最后,目标用户在组内选择邻居,实现电影评分预测。基于MovieLens和Netflix数据集的实验结果表明,该算法与经典协同过滤算法相比,提升了时间和空间的性能,展现了更为出色的伸缩性和可扩展性。     

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

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