8493 articles  [version française]

inria-00520350, version 1

Improving Random Walk Estimation Accuracy with Uniform Restarts

Konstantin Avrachenkov () 1, Bruno Ribeiro () a, 2, Don Towsley () a, 2

N° RR-7394 (2010)

Abstract: This work proposes and studies the properties of a hybrid sampling scheme that mixes independent uniform node sampling and random walk (RW)-based crawling. We show that our sampling method combines the strengths of both uniform and RW sampling while minimizing their drawbacks. In particular, our method increases the spectral gap of the random walk, and hence, accelerates convergence to the stationary distribution. The proposed method resembles PageRank but unlike PageRank preserves time-reversibility. Applying our hybrid RW to the problem of estimating degree distributions of graphs shows promising results.

  • a –  University of Massachusetts Amherst
  • 1:  MAESTRO (INRIA Sophia Antipolis)
  • INRIA – Université Montpellier II - Sciences et techniques
  • 2:  Department of Computer Science [Amherst]
  • University of Massachusetts
  • Domain : Computer Science/Networking and Telecommunication
  • Keywords : Sampling – Random Walk – Spectral Gap – PageRank – Online Social Network
  • Internal note : RR-7394
 
  • inria-00520350, version 1
  • http://hal.inria.fr/inria-00520350
  • oai:hal.inria.fr:inria-00520350
  • From: Konstantin Avrachenkov <>
  • Submitted on: Thursday, 23 September 2010 00:45:38
  • Updated on: Friday, 19 November 2010 15:40:02