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

作者：陈泽; 丁琳琳; 宋宝燕; 王俊陆^*

来源：计算机工程, 2021, 47(01): 72-86.

DOI：10.19678/j.issn.1000-3428.0059192

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

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

• 单位
  辽宁大学; 新汶矿业集团有限责任公司; 土木工程学院