Analysis of Relaxation Time in Random Walk with Jumps

Abstract : We study the relaxation time in the random walk with jumps. The random walk with jumps combines random walk based sampling with uniform node sampling and improves the performance of network analysis and learning tasks. We derive various conditions under which the relaxation time decreases with the introduction of jumps.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01936065
Contributor : Konstantin Avrachenkov <>
Submitted on : Tuesday, November 27, 2018 - 11:27:48 AM
Last modification on : Friday, November 8, 2019 - 3:48:02 PM
Long-term archiving on: Thursday, February 28, 2019 - 1:24:55 PM

File

Paper14WAW18.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01936065, version 1

Collections

Citation

Konstantin Avrachenkov, Ilya Bogdanov. Analysis of Relaxation Time in Random Walk with Jumps. Algorithms and Models for the Web Graph. WAW 2018., Anthony Bonato; Pawel Pralat; Andrei Raigorodskii, May 2018, Moscow, Russia. pp.70-82. ⟨hal-01936065⟩

Share

Metrics

Record views

53

Files downloads

114