Leveraging History for Faster Sampling of Online Social Networks

Summary: Leverages history to form higher-order Markov walks, CNRW and GNRW, for faster sampling on online social networks. They prove preservation of the stationary distribution and show empirical gains over standard random walks on real and synthetic graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10985
Venue: VLDB
Year: 2015
Pagerank: 9.5379264e-05
Overall Rank: 2,102 | 85.40%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,724	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.00010736699

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
387	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024682268
11,985	Aggregate Estimation Over a Microblog Platform	2014	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,666	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.3824583e-05
338	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00026987013
5,713	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.3595796e-05
5,178	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	5.6384997e-05
4,487	On the Embeddability of Random Walk Distances	2013	VLDB	6.1412716e-05
9,330	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.351469e-05
478	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022183187
1,724	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.00010736699
6,493	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.0344095e-05
5,739	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3454732e-05