Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
In this paper, we provide faster algorithms for computing variousfundamental quantities associated with random walks on a directedgraph, including the stationary distribution, personalized PageRankvectors, hitting times, and escape probabilities. In particular, ona directed graph with n vertices and...
Main Authors: | Peng, Richard, Sidford, Aaron, Cohen, Michael B., Kelner, Jonathan Adam, Peebles, John Lee Thompson, Vladu, Adrian Valentin |
---|---|
Outros Autores: | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
Formato: | Artigo |
Publicado em: |
Institute of Electrical and Electronics Engineers (IEEE)
2018
|
Acesso em linha: | http://hdl.handle.net/1721.1/115974 https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0002-4257-4198 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0003-0722-304X |
Registos relacionados
-
High-precision Estimation of Random Walks in Small Space
Por: Ahmadinejad, AmirMahdi, et al.
Publicado em: (2021) -
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
Por: Peng, Richard, et al.
Publicado em: (2018) -
Faster generation of random spanning trees
Por: Kelner, Jonathan Adam, et al.
Publicado em: (2010) -
Faster approximate multicommodity flow using quadratically coupled flows
Por: Miller, Gary L., et al.
Publicado em: (2013) -
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Por: Cohen, Michael B., et al.
Publicado em: (2021)