BibSonomy :: publication :: Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Maciej Kurant, Minas Gjoka, Carter T. Butts, and Athina Markopoulou. Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, page 281--292. New York, NY, USA, ACM, (2011)

Abstract

Our objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. We 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. Our 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. Therefore, the edge weights for our random walk should be chosen so as to lead to an equilibrium distribution that strikes a balance between approximating the optimal weights under an independence sampler and achieving fast convergence. We propose a heuristic approach (stratified weighted random walk, or S-WRW) that achieves this goal, while using only limited information about the graph structure and the node properties. We evaluate our technique in simulation, and experimentally, by collecting a sample of Facebook college users. We show that S-WRW requires 13-15 times fewer samples than the simple re-weighted random walk (RW) to achieve the same estimation accuracy for a range of metrics.

Description

Walking on a graph with a magnifying glass

Links and resources

DOI:10.1145/1993744.1993773
URL:http://doi.acm.org/10.1145/1993744.1993773
BibTeX key:Kurant:2011:WGM:1993744.1993773
internal link:
?
You can use this internal link to create references to this post in your discussions. Just copy this internal link and paste it in your discussion text.
search on:

Comments or reviews  
(0)

There is no review or comment yet. You can write one!

Tags

  • Last update 2 years and 6 months ago.
  • Created 2 years and 6 months ago.

Cite this publication

Walking on a graph with a magnifying glass: stratified sampling via weighted random walks

Maciej Kurant, Minas Gjoka, Carter T. Butts, and Athina Markopoulou. Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, page 281--292. New York, NY, USA, ACM, (2011)