Bayesian Inference of Online Social Network Statistics via Lightweight Random Walk Crawls
This work addresses the challenge of accurate data estimation for researchers and analysts working with online social networks, representing an incremental improvement in statistical methods for network crawling.
The paper tackled the problem of making reliable statistical inferences from online social networks using limited API crawls, proposing an unbiased estimator for aggregated sums over edges and deriving its approximate posterior distribution, with validation through numerical experiments on real-world networks.
Online social networks (OSN) contain extensive amount of information about the underlying society that is yet to be explored. One of the most feasible technique to fetch information from OSN, crawling through Application Programming Interface (API) requests, poses serious concerns over the the guarantees of the estimates. In this work, we focus on making reliable statistical inference with limited API crawls. Based on regenerative properties of the random walks, we propose an unbiased estimator for the aggregated sum of functions over edges and proved the connection between variance of the estimator and spectral gap. In order to facilitate Bayesian inference on the true value of the estimator, we derive the approximate posterior distribution of the estimate. Later the proposed ideas are validated with numerical experiments on inference problems in real-world networks.