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

Random-Walk Probability Computation on Dynamic Weighted Graphs

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

Computing random-walk probabilities on graphs is the subject of extensive research in both graph theory and data mining research.However,existing work mainly focuses on static graphs,and cannot efficiently support dynamic weighted graphs,which are ubiquitous in real-world applications.We study the problem of computing random-walk probabilities on dynamic weighted graphs.We propose to use a sampling schema called coin flip sampling,rather than the more commonly adopted weighted sampling schema,for simulating random walks in dynamic weighted graphs.We demonstrate that simulations based on coin-flip sampling maintain the unbiasedness of the resulting random-walk probability approximations.Moreover,this approach allows us to simultaneously achieve a O(1)near-optimal query time complexity and an optimal update time overhead per edge insertion or deletion.This is a significant improvement over existing methods,which typically incur substantial sampling costs or rely on intricate auxiliary structures that are hard to maintain in a dynamic setting.We present both theoretical analysis and empirical evaluations to substantiate the superiority of our method on dynamic weighted graphs.