Skip to Main content Skip to Navigation
Conference papers

Comparison of Random Walk Based Techniques for Estimating Network Averages

Abstract : Function estimation on Online Social Networks (OSN) is an important field of study in complex network analysis. An efficient way to do function estimation on large networks is to use random walks. We can then defer to the extensive theory of Markov chains to do error analysis of these estimators. In this work we compare two existing techniques, Metropolis-Hastings MCMC and Respondent-Driven Sampling, that use random walks to do function estimation and compare them with a new reinforcement learning based technique. We provide both theoretical and empirical analyses for the estimators we consider.
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Konstantin Avrachenkov <>
Submitted on : Friday, November 25, 2016 - 10:59:10 AM
Last modification on : Monday, March 29, 2021 - 2:47:23 PM
Long-term archiving on: : Monday, March 20, 2017 - 7:44:50 PM


Files produced by the author(s)




Konstantin Avrachenkov, Vivek Borkar, Arun Kadavankandy, Jithin Sreedharan. Comparison of Random Walk Based Techniques for Estimating Network Averages. Computational Social Networks, Hien T. Nguyen; Vaclav Snasel, Aug 2016, Ho Chi Minh, Vietnam. pp.27 - 38, ⟨10.1007/978-3-319-42345-6_3⟩. ⟨hal-01402800⟩