大规模动态图中概率游走约束的节点相似Top-k查询方法

摘要：

大规模动态图节点相似Top-k查询方法对大规模图查询效率较低,且当图发生动态变化时难以对查询结果进行自适应更新,导致查询结果准确度不高.利用大规模动态图概率路径游走约束条件,提出一种节点相似Top-k查询方法.通过引入PageRank概率游走机制实现将基大图生成多个小规模单向图,并利用单边弱化因子对PageRank进行概率游走约束,避免单向图反复选取少数边的情况.采用Monte Carlo模拟法进行单向图集上的相似度累积计算,以Top-k取值为衡量准则递增游走步数,避免次优相似度叠加问题.结合图的动态性特点,依据局部自适应原则提出基大图触发更新策略与单向图集联动更新策略,在保证查询准确度的同时最大限度地降低更新维护代价.实验结果表明,与FR、KM、SimRank、P-SimRank等方法相比,该方法可有效提高查询效率、查询准确度与更新效率.

关键词：大规模动态图、PageRank机制、概率游走约束、自适应更新、Top-k查询方法

所属期刊栏目：47

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金;中国博士后基金面上项目;辽宁省重点研发计划;辽宁省教育厅科学研究项目;沈阳市中青年科技创新人才支持计划

在线出版日期：2021-01-20（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：72-78,86