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: 10984
Venue: VLDB
Year: 2015
Pagerank: 9.5327714e-05
Overall Rank: 2,108 | 85.34%
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,740	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.0001071792

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
388	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024662272
11,977	Aggregate Estimation Over a Microblog Platform	2014	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
337	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00027011645
5,702	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.36473e-05
5,177	Remember Where You Came From: On The Second-Order Random Walk Based Proximity Measures	2017	VLDB	5.6439245e-05
4,527	On the Embeddability of Random Walk Distances	2013	VLDB	6.1083926e-05
9,325	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.3556432e-05
486	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022068545
1,740	A General Framework for Estimating Graphlet Statistics via Random Walk	2017	VLDB	0.0001071792
6,498	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.0392468e-05
5,730	Walk, Not Wait: Faster Sampling Over Online Social Networks	2015	VLDB	5.3506029e-05