基于三阶路径自适应度惩罚的链路预测方法_陈广福.pdf
《基于三阶路径自适应度惩罚的链路预测方法_陈广福.pdf》由会员分享,可在线阅读,更多相关《基于三阶路径自适应度惩罚的链路预测方法_陈广福.pdf(9页珍藏版)》请在咨信网上搜索。
1、第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)摘要:链路预测目标是根据已知网络结构来预测缺失链接。现存大部分基于相似度方法仅考虑二阶路径而忽略三阶路径与网络拓扑特征关联程度,这将导致预测准确
2、度下降而不适用于稀疏网络。针对以上不足,提出基于三阶路径自适应度惩罚(THADP)的链路预测算法改善稀疏网络预测精度。首先,统一泛化基于三阶路径相似度方法包括CN-L3、AA-L3和RA-L3,构建THADP框架保持节点所有三阶路径信息;其次,该框架与节点平均最短路径融合有利于捕获整个网络节点信息增强THADP鲁棒性;最后,在8个真实网络上,采用AUC和F1评价所提指标和基准方法性能,实验结果表明所提指标AUC和F1值最高分别提升了35.5%和21.5%。关键词:复杂网络;链路预测;3阶路径;最短路径;自适应度惩罚中图分类号:TP391文献标志码:A引言真实世界大量的复杂系统可由复杂网络来描述
3、和表示,其中节点代表实体、连边表示实体间的关系。然而,由于真实网络数据收集总是部分的,因此如何寻找缺失链接间关系是复杂网络研究中最有挑战的问题。链路预测目标是根据已知网络结构及其节点属性等信息去推断节点对形成链接的可能性1。此外,链路预测还具有以下功能:1)预测缺失链接、识别虚假链接及消除网络噪音;2)根据当前网络结构信息探寻网络演化机制。因此,链路预测广泛应用于不同的领域。例如在社会网络,链路预测可用于检测用户异常信息,保护用户信息安全2;社交网为不同用户推荐新朋友,可获得更好的用户体验3;此外,在生物网络中,可用于预测蛋白质间先前未知的相互作用,从而降低经验方法的成本等4。当前,大部分链路
4、预测算法的研究都集中在基于相似度方法,该方法根据网络结构信息、节点聚类系数及节点属性等信息计算每个节点对相似度分数,分数越高产生链接可能性就越高。基于相似度算法又可以划分为局部、半局部和全局方法。局部相似度方法通过节点间的共同邻居数量来描述节点间产生链接的可能性,其中具有代表性的是共同 邻 居(Common Neighbors,CN)5、资 源 分 配(Resource Allocation,RA)6和 Adamic-Adar(AA)指收稿日期:2022-03-27基金项目:福建省自然科学基金项目(2021J011146);武夷学院引进人才科研启动基金项目(YJ202017)作者简介:陈广福(
5、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数量。然而上述研究讨论的都是二阶路径方法,存在着脆弱于稀疏网络而偏好于稠密网路的问题。最近有研
6、究认为三阶路径相似度在大部分真实网络性能优于二阶路径方法。文献12针对蛋白质网结构特性提出三阶路径的相似度算法,该方法有效改善了蛋白质网中潜在相互作用关系的预测准确度。文献13在文献12基础上融合了CN、AA和RA构建三阶路径的局部相似度算法,结果表明在部分网络中三阶路径预测准确度胜过二阶路径方法。全局相似度方法利用整个网络的拓扑结构信息去计算节点间相似度分数。如顾秋阳等14提出了高阶相似度预测算法,该算法以高阶路径信息为判别特征并惩罚节点有效长路径保持网络全局结构;文献15提出了线性优化(Linear Optimization,LO)指标捕获高阶路径信息。该类指标存在设计复杂且耗时的缺点,因
7、而有研究者提出用半局部相似度方法融合局部和全局优点来调节性能与时间复杂度的平衡关系。如文献16提出自适应度惩罚(Adapative Degree Penalization,ADP)的链路预测方法,该方法通过泛化局部相似度算法,并融合节点聚类系数以提高预测准确度,同时验证了与网络结构的关联强度;文献17在文献16基础上提出共同邻 居 度 惩 罚 算 法(Common Neighbors DegreePenalization,CNDP),考虑了CN数量是否影响网络拓扑结构对泛化的局部相似度的影响;刘树新等18考虑任意节点双向资源匹配量,提出了资源传输匹配度算法。文献16-17提出自适应度惩罚的链路
8、预测算法证实了共同邻居度与网络拓扑结构存在密切联系。然而,此类方法有以下两个明显的不足之处:1)泛化基于二阶路径局部方法无法捕获更多的节点路径信息导致预测准确度低;2)泛化基于二阶路径局部相似度框架性能依赖于网络拓扑结构信息,而平均节点聚类信息仅适用于稠密网络而脆弱于稀疏网络。针对以上不足,本文要解决以下两个问题:1)泛化基于三阶路径相似度构建一个泛化三阶路径自适应惩罚框架;2)通过融合该框架与平均最短距离改善预测准确度。围绕这两个待解决的问题展开研究,具体思路如下:首先在三阶路径(L3)指标基础上融合CN、AA和RA 3个局部指标,提出CN-L3、AA-L3与RA-L3;然后将以上3个方法泛
9、化成统一的带参数三阶路径自适应度惩罚(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表 示
10、网 络 所 有 可 能 边 的 集 合 且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期陈广福,等:基
11、于三阶路径自适应度惩罚的链路预测方法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
12、是表示节点度。以上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.3T
13、HADP指标三阶泛化链路预测框架(式(4))预测的准确度依赖于,而与有直接关联的是平均节点最短路径以及平均聚类系数,本文采用节点平均最短路径方法。复杂网络求解最短路径方法较多,由于是无向无权网络,若节点间存在链接,那么值均大于0,因此使用经典的Dijkstra算法计算所有节点对间的最短路径,设节点对间最短路径的矩阵为D,其节点平均最短距离定义如下:Davg=DN(N-1)(5)其中N为网络节点数。由三阶泛化链路预测框架,将平均最短距离融合泛化框架构建统一链路预测指标 THADP,定义如下:STHADPij=xi,yjaxy()kxky-12Davg(6)泛化框架构建统一链路预测指标THADP有
14、以下两优点: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)
15、。最后节点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)综合性度量,可更全面而有效地评价
16、算法性能,其定义为: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)选航线数据库构建。该网络中的节点表示机
17、场或服务中心,链接由NFDC推荐的首选路线字符串创建。4)论文引用网络(KOHonen,KOH)21:该网络是“自组织映射”引用网。节点表示论文,链接代表论文间引用关系。5)EPA21,该网络将200页的响应集扩展到一个搜索引擎查询来构建。6)电力网(POwerGrid,POG)21:该网络是美国西部各州电网的信息。一条边代表一条电源线路。一个节点可以是发电机、变压器或变电站。7)蛋白质交互网络(VIDal,VID)21是人类蛋白质之间相互作用的网络,节点表示蛋白质,方向链接代表蛋白质间交互关系。8)论文引用网络(SmaGr,SG)21:该网络是关于网络理论与实验的引用网络,它由 1024 个
18、节点和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.05
19、760.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和
20、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)构建统
21、一框架并融合节点聚类系数,任意节点相似度定义如下: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(
22、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个实
23、验,将原始网络按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性能最差
24、,这表明平均最短相对较大时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)几乎在所有的数据集中获得最差的性能,其
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 路径 自适应 惩罚 预测 方法 陈广福
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。