基于三阶路径自适应度惩罚的链路预测方法_陈广福.pdf

第36卷第3期2023年6月Vol.36 No.3Jun.2023四川轻化工大学学报（自然科学版）Journal of Sichuan University of Science&Engineering(Natural Science Edition)基于三阶路径自适应度惩罚的链路预测方法陈广福1,2，连雁平1,2，李晓飞1,2（1.武夷学院数学与计算机学院，福建武夷山353400；2.福建省茶产业大数据应用与智能化重点实验室，福建武夷山353400）摘要：链路预测目标是根据已知网络结构来预测缺失链接。现存大部分基于相似度方法仅考虑二阶路径而忽略三阶路径与网络拓扑特征关联程度，这将导致预测准确度下降而不适用于稀疏网络。针对以上不足，提出基于三阶路径自适应度惩罚（THADP）的链路预测算法改善稀疏网络预测精度。首先，统一泛化基于三阶路径相似度方法包括CN-L3、AA-L3和RA-L3，构建THADP框架保持节点所有三阶路径信息；其次，该框架与节点平均最短路径融合有利于捕获整个网络节点信息增强THADP鲁棒性；最后，在8个真实网络上，采用AUC和F1评价所提指标和基准方法性能，实验结果表明所提指标AUC和F1值最高分别提升了35.5%和21.5%。关键词：复杂网络；链路预测；3阶路径；最短路径；自适应度惩罚中图分类号：TP391文献标志码：A引言真实世界大量的复杂系统可由复杂网络来描述和表示，其中节点代表实体、连边表示实体间的关系。然而，由于真实网络数据收集总是部分的，因此如何寻找缺失链接间关系是复杂网络研究中最有挑战的问题。链路预测目标是根据已知网络结构及其节点属性等信息去推断节点对形成链接的可能性1。此外，链路预测还具有以下功能：1）预测缺失链接、识别虚假链接及消除网络噪音；2）根据当前网络结构信息探寻网络演化机制。因此，链路预测广泛应用于不同的领域。例如在社会网络，链路预测可用于检测用户异常信息，保护用户信息安全2；社交网为不同用户推荐新朋友，可获得更好的用户体验3；此外，在生物网络中，可用于预测蛋白质间先前未知的相互作用，从而降低经验方法的成本等4。当前，大部分链路预测算法的研究都集中在基于相似度方法，该方法根据网络结构信息、节点聚类系数及节点属性等信息计算每个节点对相似度分数，分数越高产生链接可能性就越高。基于相似度算法又可以划分为局部、半局部和全局方法。局部相似度方法通过节点间的共同邻居数量来描述节点间产生链接的可能性，其中具有代表性的是共同 邻 居（Common Neighbors，CN）5、资 源 分 配（Resource Allocation，RA）6和 Adamic-Adar（AA）指收稿日期：2022-03-27基金项目：福建省自然科学基金项目(2021J011146);武夷学院引进人才科研启动基金项目(YJ202017)作者简介：陈广福(1979-),男,讲师,博士,研究方向为链路预测和网络表示等,(E-mail)文章编号：20967543（2023）03005909DOI:10.11863/j.suse.2023.03.082023年6月四川轻化工大学学报（自然科学版）标7。王凯等8分析CN所有链接、节点首位端点和拓扑有效性提出了高效CN预测指标；王鑫等9提出了融合 CN 节点紧密度和贡献链路预测指标；Lee等10提出了协同过滤框架并与CN、AA和RA相融合提高节点间获得CN的能力；李星等11融合CN和邻域拓扑两类信息刻画了节点CN数量。然而上述研究讨论的都是二阶路径方法，存在着脆弱于稀疏网络而偏好于稠密网路的问题。最近有研究认为三阶路径相似度在大部分真实网络性能优于二阶路径方法。文献12针对蛋白质网结构特性提出三阶路径的相似度算法，该方法有效改善了蛋白质网中潜在相互作用关系的预测准确度。文献13在文献12基础上融合了CN、AA和RA构建三阶路径的局部相似度算法，结果表明在部分网络中三阶路径预测准确度胜过二阶路径方法。全局相似度方法利用整个网络的拓扑结构信息去计算节点间相似度分数。如顾秋阳等14提出了高阶相似度预测算法，该算法以高阶路径信息为判别特征并惩罚节点有效长路径保持网络全局结构；文献15提出了线性优化（Linear Optimization，LO）指标捕获高阶路径信息。该类指标存在设计复杂且耗时的缺点，因而有研究者提出用半局部相似度方法融合局部和全局优点来调节性能与时间复杂度的平衡关系。如文献16提出自适应度惩罚（Adapative Degree Penalization，ADP）的链路预测方法，该方法通过泛化局部相似度算法，并融合节点聚类系数以提高预测准确度，同时验证了与网络结构的关联强度；文献17在文献16基础上提出共同邻 居 度 惩 罚 算 法（Common Neighbors DegreePenalization，CNDP），考虑了CN数量是否影响网络拓扑结构对泛化的局部相似度的影响；刘树新等18考虑任意节点双向资源匹配量，提出了资源传输匹配度算法。文献16-17提出自适应度惩罚的链路预测算法证实了共同邻居度与网络拓扑结构存在密切联系。然而，此类方法有以下两个明显的不足之处：1）泛化基于二阶路径局部方法无法捕获更多的节点路径信息导致预测准确度低；2）泛化基于二阶路径局部相似度框架性能依赖于网络拓扑结构信息，而平均节点聚类信息仅适用于稠密网络而脆弱于稀疏网络。针对以上不足，本文要解决以下两个问题：1）泛化基于三阶路径相似度构建一个泛化三阶路径自适应惩罚框架；2）通过融合该框架与平均最短距离改善预测准确度。围绕这两个待解决的问题展开研究，具体思路如下：首先在三阶路径（L3）指标基础上融合CN、AA和RA 3个局部指标，提出CN-L3、AA-L3与RA-L3；然后将以上3个方法泛化成统一的带参数三阶路径自适应度惩罚（Three-Hop Adapative Degree Penalization，THADP）链路预测框架。本文将平均最短路径融合三阶泛化框架中，提出THADP链路预测指标，通过惩罚三阶路径获得更多网络结构信息，再融合平均最短路径去挖掘更多网络结构信息。1基于THADP链路预测方法1.1问题描述给定一个有向无权网络G(V,E)，其中V=iNi=1是节点集，E表示链接集，且每条边e E是一个有序对e=(i,j)。这里不允许多个链接和自循环存在。用A=aijNN来表示G的邻接矩阵。G是无向无权网络，如果节点之间存在链接，则aij=1，否则aij=0。用U表 示 网 络 所 有 可 能 边 的 集 合 且U=N(N-1)2，显然，不存在边集合可表示为U-E。链路预测目标是从集合U-E中查找缺失链路。为了验证算法的性能，将观测到的链路集E分成两部分：训练集ET和测试集EP，前者是已知信息，后者仅用于测试。显然，ET EP=和ET EP=E。1.2泛化三阶路径相似度大部分真实网络是稀疏的，基于二阶路径相似度方法依赖于节点CN数量，对于稀疏网络来说，获得节点CN数量是有限的。因此，基于三阶路径相似度方法尽可能获得所有节点三阶路径信息弥补以上方法的不足。文献16考虑三阶路径长度提出3 个基于三阶路径相似度方法分别是 CN-L3、60第36卷第3期陈广福，等：基于三阶路径自适应度惩罚的链路预测方法AA-L3和 RA-L3。任意节点i和j的基于三阶路径相似度的定义如式（1）（3）所示。（a）CN-L3 指标，该指标是尽可能寻找节点间所有三阶路径的数，其定义如下：SCN-L3ij=xi,yjaxy（1）（b）AA-L3指标，该指标类似AA指标惩罚较大的三阶节点度，其定义如下：SAA-L3ij=xi,yjaxylogkxlogky（2）（c）RA-L3指标，该指标类似RA指标三阶节点间资源传递，其定义如下：SRA-L3ij=xi,yjaxykxky（3）其中，i和j的邻居集合i和j中分别存在着节点x和y。S表示节点i和j相似度，aij表示节点x和y的边，k是表示节点度。以上3个指标在不同真实网络中所获得节点间三阶路径信息是不一致的，表明链路预测准确度取决于不同网络结构特征。为提高以上方法适用于不同网络结构而获得最佳的预测结构，采自适应度惩罚方法去泛化基于三阶路径相似度方法构建一个统一的三阶泛化链路预测框架，其定义如下：SADPij=xi,yjaxy()kxky-12（4）其中为可调参数。由式（4）可知，当=0时，式（4）就退化为：SCN-L3ij=xi,yjaxy；当=1时，式（4）就 退 化为：SRA-L3ij=xi,yjaxykxky；当 (0,1)时，式（4）就 退 化 为：SAA-L3ij=xi,yjaxylogkxlogky。1.3THADP指标三阶泛化链路预测框架（式(4)）预测的准确度依赖于，而与有直接关联的是平均节点最短路径以及平均聚类系数，本文采用节点平均最短路径方法。复杂网络求解最短路径方法较多，由于是无向无权网络，若节点间存在链接，那么值均大于0，因此使用经典的Dijkstra算法计算所有节点对间的最短路径，设节点对间最短路径的矩阵为D，其节点平均最短距离定义如下：Davg=DN(N-1)（5）其中N为网络节点数。由三阶泛化链路预测框架，将平均最短距离融合泛化框架构建统一链路预测指标 THADP，定义如下：STHADPij=xi,yjaxy()kxky-12Davg（6）泛化框架构建统一链路预测指标THADP有以下两优点：1）克服二阶路径相似度方法仅考虑节点CN，THADP可从特别稀疏网络中获得更多节点的信息；2）利用平均最短路径获得网络全局结构信息提高预测准确度。为更深入理解泛化框架构建统一链路预测指标THADP，设5个节点的部分网络来举例说明，如图1所示。使用式（6）方法计算节点i和j相似度具体过程如下：节点i和j间存在以下 3条三阶路径：iaxj，ixaj和ixbj。节点a、b与x的度分别为：ka=6，kb=3，kx=4，节点i与j最短路径为2，因此节点i和j相似度分数为：STHADPij=(kakx)-122+(kakx)-122+(kbkx)-122=2 (0.0417)+(0.0833)。最后节点i和j相似度分数依赖于可调参数。iabjx图15节点网络示意图612023年6月四川轻化工大学学报（自然科学版）2实验结果与分析2.1评价度量本文用AUC和F1两个度量来衡量所有方法的性能19，以F1值作为综合性指标。两个度量的值越高表示该方法预测准确度越高。1）AUC为在测试集EP中的链接分数大于随机选择的一个不存在集U-E中的链接分数的概率。独立地比较m次，若有m1次测试集中的链接的分数值大于不存在集中的链接的分数，有m2次两者分数值相等，AUC定义为：AUC=m1+0.5 m2m（7）2）F1为召回率（Recall）和准确率（Precision）综合性度量，可更全面而有效地评价算法性能，其定义为：F1=2 Recall PrecisionRecall+Precision（8）2.2数据集2.2.1无向无权网络的数据集1）美国航空运输网络（USAir，USA）20：该网络由 332个链接和 2126个节点组成链接。节点表示机场，链接代表两个机场之间联系。2）犯罪网络（CRIme，CRI）20是二部图犯罪网，左节点表示一个人，右节点表示一个罪行。两个节点之间的“边”代表左节点参与了由右节点所代表的犯罪案件。3）空中交通管制网（Air Traffic Control，ATC）21：该网络由美国联邦航空管理局国家飞行数据中心（NFDC）选航线数据库构建。该网络中的节点表示机场或服务中心，链接由NFDC推荐的首选路线字符串创建。4）论文引用网络（KOHonen，KOH）21：该网络是“自组织映射”引用网。节点表示论文，链接代表论文间引用关系。5）EPA21，该网络将200页的响应集扩展到一个搜索引擎查询来构建。6）电力网（POwerGrid，POG）21：该网络是美国西部各州电网的信息。一条边代表一条电源线路。一个节点可以是发电机、变压器或变电站。7）蛋白质交互网络(VIDal，VID)21是人类蛋白质之间相互作用的网络，节点表示蛋白质，方向链接代表蛋白质间交互关系。8）论文引用网络（SmaGr，SG）21：该网络是关于网络理论与实验的引用网络，它由 1024 个节点和4916条链接组成。链接方向表示引用关系。2.2.2真实世界无向网络拓扑特征本文采用8个真实世界无向无权网络评价所有方法的性能，其拓扑结构特征统计见表1。表18个真实世界无向网络拓扑特征统计网络USAATCKOHCRIEPAPOGVIDSGN332122644698294471494131331024|E2126130712 7191474889065946438491612.80722.13135.69213.55613.72672.66914.10959.60162.73815.21822.52125.04003.556818.98923.81882.9814AC0.62520.05760.21050.00580.06370.08010.06350.3071Density0.03870.00170.00130.00430.00070.00050.00130.0094表1中，N为节点数，|E表示E链接集合的链接数，表示平均度，表示平均最短距离，AC表示节点平均聚类系数，Density表示网络稀疏程度。2.3基准方法为验证所提算法性能，本文用11个最近几年的代表性方法与之比较。11 个链路预测方法介绍如下。1）3 个基于三阶路径相似度（CN-L3，AA-L3，RA-L3）已在本文1.2节作了详细说明。2）3个基于协同过滤框架融合CN、AA与RA构成SCF-CN、SCF-AA和SCF-RA 3个预测指标10，其协同过滤框架定义为：SSCF=(A+I)S+(A+I)S T（9）其中，A为任意网络邻接矩阵，I是单位矩阵，S为任意相似度。62第36卷第3期陈广福，等：基于三阶路径自适应度惩罚的链路预测方法3）线性最优化（Linear Optimization，LO）15：该指标假设两个节点之间存在链接的可能性可以通过相邻节点贡献的线性求和来展开，其定义为：SLO=A3-2A5+3A7-4A9+（10）其中0 1。4）自 适 应 度 惩 罚 指 标（Adapative DegreePenalization，ADP）16：该方法通过泛化基于局部相似度（CN、AA和RA）构建统一框架并融合节点聚类系数，任意节点相似度定义如下：SADP(x,y)=zxy|z-C（11）其中C为节点平均聚类系数。5）共同邻居度惩罚指标（Common NeighborsDegree Penalization，CNDP）17：该方法是在ADP方法基础考虑CN数，任意节点相似度定义为：SCNDP(x,y)=zxy|Cz()|z-C（12）其中|Cz是共同邻居数。6）局部路径指标（Local Path，LP）6：该指标扩展CN指标，考虑三阶路径因素，其定义为：SLPxy=A2+A3（13）其中为可调参数。7）Katz指标22：该方法考虑整个网络所有节点的路径，其定义为：S=(I-A)-1-I（14）其中，I为单位矩阵，为可调参数。2.4结果分析本实验硬件平台为Intel Core i57200U CPU笔记 本，主 频2.71 GHz，内 存4 G，操 作 系 统 为Windows 10，所有方法使用Matlab R2016b实现。此外，所提方法含可调参数，为公平比较所有的方法，所有数据集设=0.5。对于 LO方法的参数设为0.1，LP的参数设为0.001，ADP和CNDP的参数设为1.5及Katz参数设为0.01。本文做3个实验评估所提方法的性能。首先，用AUC和F1两个度量全面评估所有 12 个指标性能；其次，对12个算法健壮性进行对比；最后，对可调参数敏感性分析。对于第1个实验，将原始网络按9 1的比例划分为训练集和测试集，再用AUC和F1度量评估所有方法性能，其实验结果见表2。通过分析基准方法与THADP在8个网络上对应AUC和F1值可以得到以下结果。1）本文所提方法在 8个数据集上与 11个指标相比较，AUC和F1度量值均获得最优。从表 2 可知，8个真实网络均是十分稀疏，表明本文方法通过泛化三阶路径相似度能够有效捕获更多节点三阶路径信息，并可以融合平均节点最短路径获得全局结构信息。2）分析表2中列出所有数据集节点平均最短距离路径，可观察到节点平均最短距离相对较小是USA、KOH和SG，较大的是POG。从表2可知，本文所提方法在POG数据集AUC和F1性能最差，这表明平均最短相对较大时THADP无法捕获更多三阶路径信息；而在USA、KOH和SG上，THADP获得最佳预测准确度，这表明节点平均最短距离直接影响THADP是否能有效捕获三阶路径信息。3）THADP 与最优基准算法相比较，在 USA、ATC、KOH、CRI、EPA、POG、VID和SG上，AUC分别提 升 1.8%、12.3%、8.3%、35.5%、18.9%、15.3%、20.2%、9.8%，F1分别提升0.9%、7.6%、6.6%、21.5%、13.6%、9.5%、13.7%、6.0%。4）基于三阶路径相似度（CN-L3、AA-L3 和RA-L3）几乎在所有的数据集中获得最差的性能，其主要原因是由于网络稀疏性导致无法获得足够节点三阶路径的信息。相比之下，本文所提方法的性能获得显著提升。例如在ATC数据集中，THADP指标与基于三阶路径相似度的最优指标相比，AUC和F1度量预测准确度分别提升了27%和35%；在CRI数据集中，THADP指标与基于三阶路径相似度的最优指标相比，AUC和F1度量预测准确度分别提升了35%和40%。在泛化基础引入网络拓扑特征-节点平均最短路径后AUC和F1值均获得显著的提升，这632023年6月四川轻化工大学学报（自然科学版）表明泛化后预测准确度与网络拓扑特征有着强关联。5）基于自包含协同过滤系列链路预测方法性能较基于三阶路径相似度系列方法有所提高，主要原因是该系列方法采用自包含协同过滤的对称性方法计算节点相似度，可获得更多局部节点信息。然而，与THADP相比较，THADP获得的质量性能更高，其主要原因是THADP能够捕获更多三阶路径信息。例如在EPA数据集中，THADP方法与其他性能最优异方法相比AUC和F1度量预测准确度分别提升了21%和34%，在其余数据集均有显著提高。6）LO和Katz是全局相似度方法，其中Katz最接近本文方法，该方法利用整个网络节点对的信息获得相似度分数矩阵来弥补网络稀疏性的不足。而LO性能略低于Katz，主要原因是该方法仅考虑节点所有邻居贡献值线性求和。LO和Katz与THADP比较，后者预测准确度高于前者。从网络结构角度分析，THADP指标同时保持高阶路径长度和全局结构信息。7）THADP、CNDP和ADP3个指标均采用类似技术路线，THADP性能显著优于CNDP和ADP方法。CNDP和ADP性能较差的主要原因是泛化基于二阶路径局部相似度仅考虑局部结构信息而平均节点聚类系数也只能反映网络局部节点关系。尤其在特别稀疏网络CRI中表现尤为明显，THADP指标的AUC和F1最多提高44%和57%。表2基准方法与THADP在8个网络上对应AUC和F1值指标CN-L3AA-L3RA-L3SCF-CNSCF-AASCF-RALPLOCNDPADPKatz本文方法USAAUC0.8960.8920.8890.9070.9090.9340.9690.9250.9390.9420.9250.987F10.6620.7070.7190.6690.7410.7550.7810.7090.7070.7160.7570.789ATCAUC0.6630.6780.6980.7740.7790.7890.7110.5970.7830.6260.8480.971F10.4210.4050.4160.4740.4970.5020.4410.6050.4990.3720.6970.773KOHAUC0.8810.8520.8600.8900.8980.9030.8920.8000.8700.8190.8870.986F10.2970.5790.5800.3040.6570.6630.4080.6900.6830.4280.7220.788CRIAUC0.6070.5980.5910.5990.5860.5930.5820.5650.5240.5090.5580.962F10.3480.2690.2610.3360.2420.2580.2800.5630.2060.2460.5320.778EPAAUC0.7890.7880.7960.7770.7380.7680.7860.7150.7420.5880.7350.985F10.2270.4950.5060.2210.4050.4490.2790.6510.5140.1920.6350.787POGAUC0.5960.5680.5990.6330.6410.6360.6360.5530.6530.5940.6680.821F10.1830.1430.1920.1900.2130.2100.1640.5780.2190.1850.6130.708VIDAUC0.7590.7340.7520.7580.7620.7620.7600.7000.7660.6200.7470.968F10.2230.4030.4250.2300.4650.4670.2820.6440.5280.2300.6410.781SGAUC0.8650.8480.8310.8720.8950.8990.8740.8160.8390.8420.8800.997F10.4340.6700.6550.4400.7260.7290.5310.7020.5840.5060.7340.794对于第二个实验，测试6种代表性指标鲁棒性。通过改变训练集大小来改变原始网络的稀疏性。本实验设训练集大小范围为 0.4、0.5、0.6、0.7、0.8、0.9，若训练集比例太小会破坏网络结构导致预测不准确，其实验结果如图2所示。从图2 中可以看出：1）本文所提指标在不同训练集下AUC值的波动不明显，而有些指标在训练集变化时产生较大的波动，例如在ATC和POG数据集中CN-L3指标。2）当训练集仅占40%时、测试集占60%的情况下，本文所提指标AUC值胜过其余5个指标，这表明在极端稀疏情况下，THADP 指标依然获得最佳的预测准度，同时也表明该方法适用于处理稀疏网络的链路预测问题。3）本文所提方法在训练集仅占40%情况下，在所有稀疏网络中AUC值均优于其余5个指标，表明该方法具备良好的鲁棒性。64第36卷第3期陈广福，等：基于三阶路径自适应度惩罚的链路预测方法(a)USA训练集下对应的AUC变化(b)ATC训练集下对应的AUC变化(c)KOH训练集下对应的AUC变化(d)CRI训练集下对应的AUC变化(e)EPA训练集下对应的AUC变化(f)SG训练集下对应的AUC变化(g)PG训练集下对应的AUC变化(h)VID训练集下对应的AUC变化图2不同训练集下对应AUC变化最后，分析可调参数对性能的影响。可调参数与网络结构特征有着强关联，通过调整使THADP获得最佳性能。设置变化为-1.0、-0.5、0、0.5、1.0和1.5，其实验结果如图3所示。由图3可看出：当为负数时，AUC和F1值均处于最差，主要是因为当为负数时无有效惩罚度，导致获得的性能最差；当=0时式（6）退化为式（1），性能有所提高；当大于0时，性能开始快速提高并获得恒定水平，主要原因是可产生有效惩罚度并获得全局结构信息。上述表明泛化后框架的最佳性能依赖于网络结构信息。因此，当=0.5时所有网络均获得最优性能。(a)不同参数在8个网络上对应的AUC(b)不同参数在8个网络上对应的F1值图3不同参数在8个网络上对应的AUC和F1值652023年6月四川轻化工大学学报（自然科学版）3结束语如何融合不同网络的不同类型拓扑结构信息来提高链路预测的准确度是当前研究的热点之一。本文提出了基于三阶路径自适应度惩罚的链路预测指标，该方法核心是泛化基于三阶路径相似度算法（CN-L3，AA-L3，RA-L3）统一构建三阶路径自适应度惩罚的框架。将平均最短路径与自适应度可调参数相结合组成三阶路径自适应度惩罚的链路预测指标。在8个真实网络上与最近的代表性方法比较，结果表明本文方法更具优势。此外，实验结果表明所提指标预测准确度与网络拓扑的拓扑特征有密切关联。相对于无向网络的链路预测，如何泛化三阶路径相似方法以适用于有向网络链路预测，以及验证有向网络结构是否同样与泛化后框架有关联程度，是值得进一步研究的课题。参考文献：1 李艳丽,周涛.链路预测中的局部相似性指标J.电子科技大学学报,2021,50(3):422-427.2 KAGAN D,ELOVICHI Y,FIRE M.Generic anomalous vertices detection utilizing a link prediction algorithmJ.Social Network Analysis andMining,2018,8(1):1-13.3 WU S,SUN J,TANG J.Patent partner recommendation in enterprise social networksC/Proceedings of the SixthACM International Conference onWeb Search and Data Mining,Italy,Rome,February 4-8,2013:43-52.4 YU S,ZHAO M,FU C,et al.Target defense against link-prediction-based attacks via evolutionary perturbationsJ.IEEE Transactions on Knowledgeand Data Engineering,2019,33(2):754-767.5 LIBEN-NOWELL D,KLEINBERG J.The link-prediction problem for social networksJ.Journal of the American Society for InformationScience and Technology,2007,58(7):1019-1031.6 ZHOU T,L L,ZHANGYC.Predicting missing links via local informationJ.European Physical Journal B,2009,71(4):623-630.7ADAMIC LA,ADAR E.Friends and neighbors on the webJ.Social Networks,2003,25(3):211-230.8 王凯,刘树新,于洪涛,等.基于共同邻居有效性的复杂网络链路预测算法J.电子科技大学学报,2019,48(3):432-439.9 王鑫,陈喜,钱付兰,等.结合共同邻居贡献度的节点相似性链路预测算法J.数据采集与处理,2018,33(5):900-910.10 LEEYL,ZHOU T.Collaborative filtering approach to link predictionJ.PhysicaA:Statistical Mechanics and itsApplications,2021:126107.11 李星,朱宇航,柏溢,等.基于共同邻居邻域拓扑稠密性加权的链路预测方法J.计算机应用研究,2021,38(5):1503-1507.12 KOVCS IA,LUCK K,SPIROHN K,et al.Network-based prediction of protein interactionsJ.Nature Communications,2019,10(1):1240.13 ZHOU T,LEE Y L,WANG G.Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithmsJ.Physica A:StatisticalMechanics and itsApplications,2021,564:125532.14 顾秋阳,吴宝,池仁勇.基于高阶路径相似度的复杂网络链路预测方法J.通信学报,2021,42(7):61-69.15 PECH R,HAO D,LEE Y L,et al.Link prediction via linear optimizationJ.Physica A:Statistical Mechanics and its Applications,2019,528:121319.16 MARTNEZV,BERZALF,CUBERO J C.Adaptive degree penalization for link predictionJ.Journal of Computational Science,2016,13:1-9.17 RAFIEE S,SALAVATI C,ABDOLLAHPOURI A.CNDP:link prediction based on common neighbors degree penalizationJ.Physica A:Statistical Mechanics and itsApplications,2020,539:122950.18 刘树新,李星,陈鸿昶,等.基于资源传输匹配度的复杂网络链路预测方法J.通信学报,2020,41(6):70-79.19YANGY,LICHTENWALTER R N,CHAWLAN V.Evaluating link prediction methodsJ.Knowledge and Information Systems,2015,45(3):66第36卷第3期陈广福，等：基于三阶路径自适应度惩罚的链路预测方法751-782.20 ROSSI R A,AHMED N K.The network data repository with interactive graph analytics and visualizationC/Proceedings of the Twenty-NinthAAAI Conference onArtificial Intelligence,Texas,USA,January 25-30,2015:4292-4293.21 KUNEGIS J.Konect:the koblenz network collectionC/Proceedings of the 22nd International Conference on World Wide Web Companion,Rio de Janeiro,Brazil,May 13-17,2013:1343-1350.22 KATZ L.Anew status index derived from sociometric analysisJ.Psychometrika,1953,18(1):39-43.引用格式：中文:陈广福,连雁平,李晓飞.基于三阶路径自适应度惩罚的链路预测方法J.四川轻化工大学学报(自然科学版),2023,36(3):59-67.英文:CHEN G F,LIAN Y P,LI X F.Link prediction method based on three-hop adaptive degree penalizationJ.Journal of Sichuan Universityof Science&Engineering(Natural Science Edition),2023,36(3):59-67.Link Prediction Method Based on Three-Hop Path Adaptive Degree PenalizationCHEN Guangfu1,2,LIAN Yanping1,2,LI Xiaofei1,2（1.College of Mathematics and Computer,Wuyi University,Wuyishan 354300,China;2.Fujian Key Laboratoryof Big Data Application and Intellectualization for Tea Industry,Wuyishan 354300,China)Abstract:The goal of link prediction is to predict missing links according to the known network structure.Most of the existing methods based similarity only focus on the 2-hop path while ignore the association betweenthe three-hop path and the topology,which leads to the reduction of prediction accuracy and is not suitable forsparse networks.In view of this shortcomings,a link prediction algorithm based on three-hop path adaptivedegree penalty(THADP)has been proposed to improve the prediction accuracy of sparse networks.Firstly,themethods based on three-hop path similarity including CN-L3,AA-L3 and RA-L3 are generally unified,which areused to construct THADP framework to maintain all three-hop path information of nodes.Secondly,theframework and the average shortest path of nodes are fused,which is conducive to capture the node informationof the whole network and enhance the robustness of THADP.Finally,the AUC and F1 are used to evaluate theperformances of the proposed metrics and the baseline method on eight real networks,and the experimentalresults show that the AUC and F1 of the proposed metrics are improved by 35.5%and 21.5%,respectively.Key words:complex network;link prediction;three-hop path;shortest path;adaptive degree penalization67