Walking on a Graph With a Magnifying Glass: Stratified Sampling Via Weighted Random Walks
The authors' objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. They design a random walk on an appropriately defined weighted graph that achieves high efficiency by preferentially crawling those nodes and edges that convey greater information regarding the target metric. Their approach begins by employing the theory of stratification to find optimal node weights, for a given estimation problem, under an independence sampler. While optimal under independence sampling, these weights may be impractical under graph crawling due to constraints arising from the structure of the graph.