动态有权图上的随机游走概率计算
Random-Walk Probability Computation on Dynamic Weighted Graphs
王涵之 1易璐 2魏哲巍 3甘骏豪 4袁野 5文继荣 6杜小勇7
作者信息
- 1. 中国人民大学信息学院 北京 100872
- 2. 中国人民大学高瓴人工智能学院 北京 100872
- 3. 中国人民大学高瓴人工智能学院 北京 100872;琶洲实验室(黄埔) 广州 510555;大数据管理与分析方法研究北京市重点实验室(中国人民大学高瓴人工智能学院) 北京 100872;数据工程与知识工程教育部重点实验室(中国人民大学) 北京 100872
- 4. 墨尔本大学 澳大利亚墨尔本 VIC3010
- 5. 北京理工大学计算机学院 北京 100081
- 6. 中国人民大学信息学院 北京 100872;中国人民大学高瓴人工智能学院 北京 100872;大数据管理与分析方法研究北京市重点实验室(中国人民大学高瓴人工智能学院) 北京 100872
- 7. 中国人民大学信息学院 北京 100872;数据工程与知识工程教育部重点实验室(中国人民大学) 北京 100872
- 折叠
摘要
图上的随机游走概率计算是传统图论与现代数据挖掘领域普遍关注的问题之一.现有工作普遍关注静态图上的随机游走概率计算,却鲜少关注与实际应用场景更贴合的权重动态图.针对动态有权图上的随机游走概率计算问题,提出了一种基于硬币翻转采样的随机游走概率计算方法.相比于传统的基于权重采样的随机游走概率计算方法,所提方法可以在保证随机游走概率计算结果无偏的前提下,同时做到近似最优的随机游走概率计算复杂度和最优的采样结构更新复杂度.作为对比,现有方法或具有较大的计算时间复杂度,或依赖于复杂的索引结构而难以在动态图上即时更新.对所提方法做出了详细的理论分析,并在真实图数据集上进行模拟实验,实验结果证实了所提方法的有效性.
Abstract
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 near-optimal query time complexity and an optimalO(1)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.
关键词
随机游走概率计算/动态有权图/硬币翻转采样/实时更新/大规模图Key words
random-walk probability computation/dynamic weighted graphs/coin-flip sampling/real-time update/large-scale graphs引用本文复制引用
基金项目
国家自然科学基金项目(U2241212)
国家自然科学基金项目(61932001)
北京市自然科学基金项目(4222028)
北京高校卓越青年科学家项目(BJJWZYJH012019100020098)
华为下一代智能信息分发技术研究项目()
中国人民大学 2023年度拔尖创新人才培育资助计划项目()
中央高校建设世界一流大学(学科)和特色发展引导专项资金()
新一代智能搜索与推荐教育部工程研究中心资助()
中国人民大学大型科学仪器共享平台()
出版年
2024
NETL
NSTL
万方数据