计算机工程

作者：陈泽, 丁琳琳, 宋宝燕, 王俊陆

单位：1. 辽宁大学 信息学院, 沈阳 110036;2. 山东能源新汶矿业集团有限责任公司, 山东 泰安 271200;3. 东北大学 资源与土木工程学院, 沈阳 110004

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

基金：国家自然科学基金（61472169，61502215）；中国博士后基金面上项目（2020M672134）；辽宁省重点研发计划（2017231011）；辽宁省教育厅科学研究项目（LJC201913）；沈阳市中青年科技创新人才支持计划（RC180244）。

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

来源：2021年第1期

《计算机工程》期刊编辑部

查看计算机工程杂志2021年第1期