Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

Rui Wang; Yongkun Li; Shuai LinWeiJie WuHong XieYinlong XuJohn C.S. Lui

首页> 外文期刊>IEEE Transactions on Knowledge and Data Engineering >Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

【24h】

Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

机译：Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient “unbiased sampling” schemes, and we also design two variant algorithms which can reduce sampling cost and speed up the convergence. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms; and to achieve the same estimation accuracy, our approach reduces the query cost significantly. Last, we use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

著录项

来源
《IEEE Transactions on Knowledge and Data Engineering》 |2023年第5期|4570-4584|共15页
作者
Rui Wang; Yongkun Li; Shuai LinWeiJie WuHong XieYinlong XuJohn C.S. Lui;
展开▼
作者单位

University of Science and Technology of China, Hefei, Anhui, China;

University of Science and Technology of China, Hefei, Anhui, China|USTC Tang Scholar, Hefei, Anhui, China;

Independent Researcher, California, CA, USAChongqing University, Chongqing, ChinaChinese University of Hong Kong, Hong Kong;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类计算技术、计算机技术;
关键词
Convergence; Legged locomotion; Estimation; Costs; Task analysis; Markov processes; Social networking (online);

Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

摘要

著录项

相关主题

期刊订阅