动态有权图上的随机游走概率计算

来源：计算机研究与发展杂志2024年第8期北京时间：

作者：王涵之,易璐,魏哲巍,甘骏豪,袁野,文继荣,杜小勇,

摘要：图上的随机游走概率计算是传统图论与现代数据挖掘领域普遍关注的问题之一.现有工作普遍关注静态图上的随机游走概率计算，却鲜少关注与实际应用场景更贴合的权重动态图.针对动态有权图上的随机游走概率计算问题，提出了一种基于硬币翻转采样的随机游走概率计算方法.相比于传统的基于权重采样的随机游走概率计算方法，所提方法可以在保证随机游走概率计算结果无偏的前提下，同时做到近似最优的随机游走概率计算复杂度和最优的采样结构更新复杂度.作为对比，现有方法或具有较大的计算时间复杂度，或依赖于复杂的索引结构而难以在动态图上即时更新.对所提方法做出了详细的理论分析，并在真实图数据集上进行模拟实验，实验结果证实了所提方法的有效性.

关键词：随机游走概率计算, 动态有权图, 硬币翻转采样, 实时更新, 大规模图,