On random walk based graph sampling

Publication Type:
Conference Proceeding
Proceedings - International Conference on Data Engineering, 2015, 2015-May pp. 927 - 938
Issue Date:
Filename Description Size
[2015 ICDE] On Random Walk Based Graph Sampling.pdfPublished version319.43 kB
Adobe PDF
Full metadata record
© 2015 IEEE. Random walk based graph sampling has been recognized as a fundamental technique to collect uniform node samples from a large graph. In this paper, we first present a comprehensive analysis of the drawbacks of three widely-used random walk based graph sampling algorithms, called re-weighted random walk (RW) algorithm, Metropolis-Hastings random walk (MH) algorithm and maximum-degree random walk (MD) algorithm. Then, to address the limitations of these algorithms, we propose two general random walk based algorithms, named rejection-controlled Metropolis-Hastings (RCMH) algorithm and generalized maximum-degree random walk (GMD) algorithm. We show that RCMH balances the tradeoff between the limitations of RW and MH, and GMD balances the tradeoff between the drawbacks of RW and MD. To further improve the performance of our algorithms, we integrate the so-called delayed acceptance technique and the non-backtracking random walk technique into RCMH and GMD respectively. We conduct extensive experiments over four real-world datasets, and the results demonstrate the effectiveness of the proposed algorithms.
Please use this identifier to cite or link to this item: