Improving Random Walk Estimation Accuracy with Uniform Restarts

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.
Type de document :
Rapport
[Research Report] RR-7394, INRIA. 2010
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00520350
Contributeur : Konstantin Avrachenkov <>
Soumis le : jeudi 23 septembre 2010 - 00:45:38
Dernière modification le : samedi 27 janvier 2018 - 01:31:43
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:30:09

Fichier

RR-7394.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00520350, version 1

Collections

Citation

Konstantin Avrachenkov, Bruno Ribeiro, Don Towsley. Improving Random Walk Estimation Accuracy with Uniform Restarts. [Research Report] RR-7394, INRIA. 2010. 〈inria-00520350〉

Partager

Métriques

Consultations de la notice

329

Téléchargements de fichiers

410