Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More

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...

Full description

Bibliographic Details
Main Authors: Peng, Richard, Sidford, Aaron, Cohen, Michael B., Kelner, Jonathan Adam, Peebles, John Lee Thompson, Vladu, Adrian Valentin
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Published: Institute of Electrical and Electronics Engineers (IEEE) 2018
Online Access: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

Internet

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

Similar Items