基于节点匹配度和共同邻居的链路预测算法实现

摘要目前大部分的链路预测基于相似度算法没有充分利用节点间相互作用的强度和局部拓扑特征，为了解决这个不足，本文提出了一种基于节点匹配度和共同邻居的链路预测算法，该算法可以同时保持两个端点邻居和共同邻居信息。首先，计算节点对两个端点的度，根据两个端点的度计算节点匹配度相似度;其次通过整合节点共同邻居的信息，以提高对局部特征的捕捉能力;最后，综合节点的匹配度和共同邻居节点的加权相似性，构建全面的预测模型。通过对实际网络数据集的实验，证明所提算法在AUC、Recall和其他评估指标上相对于经典的共同邻居（CN）和资源分配（RA）传统算法提高了预测准确性，验证了其有效性和鲁棒性。关键词：复杂网络；链接预测；节点匹配；共同邻居；AbstractCurrently,mostlinkpredictionmethodsbasedonsimilarityalgorithmsdonotfullyutilizethestrengthofinteractionsbetweennodesandlocaltopologicalfeatures.Toaddressthisshortcoming,thispaperproposesalinkpredictionalgorithmbasedonnodematchingdegreeandcommonneighbors,whichcansimultaneouslymaintaintheinformationofbothendpointneighborsandcommonneighbors.Firstly,thedegreesofthenodepairforthetwoendpointsarecalculatedtodeterminethenodematchingdegreesimilaritybasedonthedegreesofthetwoendpoints;secondly,informationfromthecommonneighborsofthenodesisintegratedtoenhancetheabilitytocapturelocalfeatures;finally,acomprehensivepredictionmodelisconstructedbycombiningthenodematchingdegreeandtheweightedsimilarityofcommonneighbornodes.ExperimentsconductedonrealnetworkdatasetsdemonstratethattheproposedalgorithmimprovespredictionaccuracyintermsofAUC,Recall,andotherevaluationmetricswhencomparedtoclassiccommonneighbor(CN)andresourceallocation(RA)traditionalalgorithms,validatingitseffectivenessandrobustness.Keywords:Complexnetworks;Linkprediction;Nodematching;Commonneighbors目录TOC\o"1-3"\h\u1引言 )4实验结果与分析4.1评价度量AUC（AreaUndertheCurve）被用来衡量链路预测的准确度。AUC的数值范围通常在0.5到1.0之间，小数点取到后五位。AUC数值越接近1.0，说明算法的链路预测效果越优越；AUC数值越接近0.5时说明算法的链路预测效果越不好。AUC的定义式子如下:召回率指标(Recall)REF_Ref22432\r\h[16]也是用来衡量算法预测准确度的方法，该指标主要是从测试集选取边与总边数比率，其中，M表示边总数，m表示选取中边，则Recall定义式为: 4.2结果分析本文章选择AUC指标作为算法精确度指标，将6个基准算法的指标（CN、AA、RA、LNBCN、LNBAA、LNBRA、HDI)与本文所提出基于节点匹配度和共同邻居的链路预测算法的指标（ADCN、ADAA、ADRA）分别在6个（Yeast网络、Foodweb网络、Pdzbase网络、Baydry网络、SmaGri网络、Mangwet网络）中比较AUC的值,比较结果如下表所示。表中AUC数值与精确程度成正比，可通过AUC数值来反映算法的优越性。表4-1各算法链路预测AUC数值YeastFoodwebPdzbaseBaydrySmaGriMangwetCN0.734870.75610.488820.608140.85060.70012AA0.734980.750360.488690.611070.85520.71924RA0.737080.761310.49530.618880.860010.71769LNBCN0.737820.831030.494950.629590.863140.71534LNBAA0.736990.834790.499410.645990.857020.73078LNBRA0.73010.840040.498950.656940.854220.73228HDI0.728910.676980.498570.531090.79390.63874ADCN0.871470.814540.720980.690270.843820.76005ADAA0.886530.825990.819130.700430.860940.77135ADRA0.90880.839430.868210.708260.896910.7693从上表的AUC数值可以观察到，无论是在Yeast网络、Foodweb网络、Pdzbase网络、Baydry网络、SmaGri网络还是Mangwet网络的任一网络中，ADCN、ADAA、ADRA中任意网络的AUC指标皆高于CN、AA、RA、LNBCN、LNBAA、LNBRA、HDI在不同网络中的指标。在Yeast网络中，指数最高的是ADRA算法所检测的数据，次高的是ADAA。在Foodweb网络中，指数最高的是ADRA算法所检测的数据，次高的是ADAA基准指标。在Mangwet网络中，指数最高的是ADAA算法所检测的数据，次高的是ADRA基准指标。在剩余的两个网络中，最高值和次高值均处于ADCN、ADAA、ADRA算法之中，说明节点匹配度和共同邻居的链路预测算法，相较于其它算法更加精确，预测的准确度更高。表4-2各算法链路预测RECALL数值YeastFoodwebPdzbaseBaydry1SmaGriMangwetCN0.0920250.279040.0060.28650.13970.36632AA0.190660.452650.0060.509740.339250.56939RA0.203960.44960.0110670.510110.350320.5675LNBCN0.230850.494430.00733330.582640.363240.58624LNBAA0.231610.504440.0116670.578120.365110.59606LNBRA0.227510.508810.0816670.584940.362670.58952HDI0.218140.434270.00980.450790.396080.52756ADCN0.547330.647870.560240.595680.645040.62512ADAA0.679390.654340.65150.598450.680670.63621ADRA0.632370.660360.594780.607290.698610.63331在表4-2中展现了各类链路预测算法对应的RECALL数值，可以观察出ADCN、ADAA、ADRA算法无论是在Yeast网络、Foodweb网络、Pdzbase网络、Baydry网络、SmaGri网络还是Mangwet网络都是以极高的优势存在，最高值都在他们之间。本文算法中召回率指标都在0.6附近，其中最高的是0.69861，对于其他算法的数值来说这算是很高的。在Pdzbase网络和Yeast网络中,ADCN、ADAA、ADRA、CN、AA、RA、LNBCN、LNBAA、LNBRA和HDI的召回率都很低，表明在这两个网络中可见边不足导致了Recall指标不高，但是本文的算法还是有着0.54的预测值，这足够说明本文的算法十分优越，准确度为所有算法中最高的。网络可以划分成训练集与测试集，本实验通过改变训练集、针对不同的训练集比例和十个预测算法，将训练集比例设置为0.3、0.4、0.5、0.6、0.7、0.8、0.9，并在CN、AA、RA、LNBCN、LNBAA、LNBRA、HDI以及本文的ADCN、ADAA与ADRA算法来观察AUC和Recall数值的变化，得到了十个柱状图。见下图4-1(a)(b)，图4-2(a)(b)，图4-3(a)(b)，图4-4(a)(b)，图4-5(a)(b)与图4-6(a)(b)，横坐标是由十个预测算法表示，每个柱状图由0.4-0.9六个训练集比例表示，AUC与Recall数值用纵坐标来表示。图4-SEQ图4-\*ARABIC1(a)Yeast网络下不同训练集比例在各算法对应的AUC图4-1(b)Yeast网络下不同训练集比例在各算法对应的Recall在REF_Ref31457\h图4-1(a)和(b)两个图中可以观察到，在Yeast网络下，本文所提到的ADCN、ADAA与ADRA这三个算法与其他几个预测算法相比看出，无论训练集比例是多少，AUC和Recall指标都为最高的。随着训练集比例的升高，本文的算法在AUC和Recall指标也逐渐升高，AUC的值上升速度会较为缓慢一点，但也处于稳定增长的状态，并且一直都是十个预测算法中的最佳数值，甚至ADCN、ADAA与ADRA这三个算法训练集比例为最低的0.4时的数值都比其他算法训练集比例最高0.9时的数值都更大。ADRA算法中AUC和Recall在0.4-0.9的训练集比例中数值从0.87-0.90，0.39-0.63，体现了该算法在Yeast网络下有着高质量的预测性能。图4-SEQ图4-\*ARABIC2(a)Foodweb网络下不同训练集比例在各算法对应的AUC图4-2(b)Foodweb网络下不同训练集比例在各算法对应的Recall观察REF_Ref32029\h图4-2(a)和(b)两个图表，在Foodweb网络中可以看出ADCN、ADAA与ADRA算法依旧保持了较高的准确率。在AUC中,本文算法与对比算法的数值在不同比例下都比较接近,本文算法在0.4的训练集比例下为十种算法的最高数值，在其他五个训练集比例中本文算法数值仅次于LNBCN、LNBAA、LNBRA算法的数值，相差甚小，并且在实验中会有不可避免的因素导致数据会有点误差。AUC的数值虽然不能直观看出对比，但Recall中就可以直观地看出本文的算法在对比算法中有着优势，不同比例下的数值都远远高于对比算法。通过以上分析可以知道，ADCN、ADAA与ADRA算法在Foodweb网络下的不同训练集都有较高的优势。图4-SEQ图4-\*ARABIC3(a)Pdzbase网络下不同训练集比例在各算法对应的AUC图4-3(b)Pdzbase网络下不同训练集比例在各算法对应的Recall观察REF_Ref32395\h图4-3(a)和(b)两个图表，在Pdzbase网络中可以看出AUC的训练集比例为0.4-0.9时，对比算法的数值十分接近，但都远低于本文算法，从中可以看出本文算法的优势更大。Recall中的对比算法数值都很低，而ADCN、ADAA与ADRA算法在对比算法数值都很低的情况下还保持这么高的准确率，也说明了本文算法的优越性，通过图表也可以十分明显的看出ADCN、ADAA与ADRA算法在Pdzbase网络中，不同训练集比例下都有着十分优秀的预测性能。图4-SEQ图4-\*ARABIC4(a)Baydry网络下不同训练集比例在各算法对应的AUC图4-4(b)Baydry网络下不同训练集比例在各算法对应的Recall从REF_Ref182\h图4-4(a)和(b)可以看出在Baydry网络下，本文所提的算法与其他七个指标相比可得出结论：在训练集比例相同的情况下，本文算法的AUC值与其他算法的AUC值虽比较接近，但本文所提的算法仍然都高于另外七个。在训练集为0.7-0.9时，LNBCN、LNBAA、LNBRA算法的Recall数值与本文算法基本持平,但本文算法仍然高于这三个算法，综上所述，本文的算法在Baydry网络下的不同训练集都有较高的鲁棒性。图4-SEQ图4-\*ARABIC5（a)Smagri网络下不同训练集比例在各算法对应的AUC图4-5(a)Smagri网络下不同训练集比例在各算法对应的Recall观察REF_Ref698\h图4-5(a)和(b)两个图表，在Smagrit网络中可以看出AUC的训练集比例为0.4和0.5时，对比算法低于本文算法，比例在0.6-0.7时，对比算法与本文算法的数值十分接近，但从总体看，本文的算法优势更大。Recall中的对比算法数值从训练集比例为0.4到0.9逐渐上升，但仍远低于本文算法，其中，在训练集比例在0.9时，对比算法recall值最高为0.36，而本文算法最低为0.65。综上所述，算法在Smagri网络中的不同训练集比例下都有着较高的准确率。图4-SEQ图4-\*ARABIC6(a)Mangweb网络下不同训练集比例在各算法对应的AUC图4-6(b)Mangweb网络下不同训练集比例在各算法对应的Recall观察REF_Ref1086\h图4-6(a)和(b)两个图表，在Mangweb网络中可以看出AUC的训练集比例从0.4到0.9，对比算法与本文算法都在缓慢上升，其中，HDI的数值远小于本文算法，而其他算法的数值虽然与本文算法接近，但仍然低于本文算法，所以从总体来看，本文的算法优势更大。Recall中的对比算法数值从训练集比例为0.4到0.9逐渐上升，CN和HDI的数值明显小于本文算法，剩余其他算法虽然比CN和HDI的数值大，但仍然小于本文的算法。通过以上分析，无论是通过AUC还是Recall的数值，都可以判断出本文算法在不同训练值比例的Mangweb网络中的优越性。5总结与展望5.1总结本文的第一章主要是对本课题的研究背景与研究意义以及国内外研究现状进行了简单的阐述与分析。其中，研究意义包括链路预测的重要性、现有方法的局限性以及本研究的意义，讲述了针对现有方法忽视节点异质性、高阶信息利用不足等问题，本研究提出的算法为复杂网络分析了提供新思路。第二章主要讲述节点匹配度和共同邻居的链路预测相关理论。第一节阐述了复杂网络的基本特征，第二节对链路预测的基本理论进行了说明。第三章提出节点匹配度与共同邻居链路预测算法，是本文的核心部分。首先描述了共同邻居的概念，通过公式说明共同邻居相似度的定义，并给出算法执行代码。第二节讲解了节点匹配度相似度的概念与公式。第三节列出了本文所提算法，并给出一系列的算法与公式。第四章对实验数据进行分析，并得出结果，先介绍了两个链路预测评价指标，分别为AUC和Recall（召回率）两个指标。第二节讲述了实验结果的分析，用AUC和召回率两个指标来评价估算，在Yeast网络、Foodweb网络、Pdzbase网络、Baydry网络、SmaGri网络、Mangwet网络这六个不同网络数据集比例下，对本文所提算法ADCN、ADAA、ADRA和已有算法CN、AA、RA、LNBCN、LNBAA和LNBRA之间进行比较，通过实验数据表明，所提的预测模型性能有着显著优势。5.2展望当今科技发展迅速，链路预测面临着许多机遇与挑战，为了提高链路预测算法的优势，本文章提出了节点匹配度和共同邻居的链路预测算法，虽然本文所提算法可以很大提升预测精确度，但仍存在进一步优化的空间。链路预测作为网络科学的核心研究方向，其未来发展将会呈现多学科交叉融合的趋势。随着图神经网络、表示学习等人工智能技术的快速发展，链路预测算法将突破传统方法的局限性，在建模复杂网络特征方面展现出更强的适应性。另外，算法效率优化和大规模网络计算也将成为重要的技术攻关点，为复杂系统的认知与预测提供更强大的分析工具。参考文献邬剑升,李玉珩.基于共同邻居惩罚的复杂网络链路预测方法[J].计算机测量与控制,2023,31(03):71-75+139.王宇伟,牛耘.基于关系相似性的蛋白质交互作用识别[J].计算机技术与发展,2015,25(02):42-46.汤永新,齐敬英.基于共同邻居的小度节点有利链路预测算法[J].现代电子技术,2021,44(05):37-40.李聪,季新生,刘树新,李劲松,李海涛.基于节点匹配度的动态网络链路预测方法[J].网络与信息安全学报,2022,8(04):131-143.王凯,刘树新,于洪涛,李星.基于共同邻居有效性的复杂网络链路预测算法（英文）[J].电子科技大学学报,2019,48(03):432-439.陈广福,连雁平.融合节点中心性和度相关聚类的有向网络链路预测[J].计算机与现代化,2022,(08):36-42.吕琳媛.复杂网络链路预测[J]