Can I read Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More on EtoBox?

Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More by Cohen, Michael B.; Kelner, Jon; Peebles, John; Peng, Richard; Sidford, Aaron; Vladu, Adrian is a scholarly article available to read on EtoBox.

What is Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More about?

In this paper, we provide faster algorithms for computing various fundamental quantities associated with random walks on a directed graph, including the stationary distribution, personalized PageRank vectors, hitting times, and escape probabilities. In particular, on a directed graph with $n$ vertices and $m$ edges, we show how to compute each quantity in time $\tilde{O}(m^{3/4}n+mn^{2/3})$, where the $\tilde{O}$ notation suppresses polylogarithmic factors in $n$, the desired accuracy, and the appropriate condition number (i.e. the mixing time or restart probability). Our result improves upon the previous fastest running times for these problems; previous results either invoke a general purpose linear system solver on a $n\times n$ matrix with $m$ non-zero entries, or depend polynomially on the desired error or natural condition number associated with the problem (i.e. the mixing time or restart probability). For sparse graphs, we obtain a running time of $\tilde{O}(n^{7/4})$, breaking the $O(n^{2})$ barrier of the best running time one could hope to achieve using fast matrix multiplication. We achieve our result by providing a similar running time improvement for solving directed

Author

Cohen, Michael B.; Kelner, Jon; Peebles, John; Peng, Richard; Sidford, Aaron; Vladu, Adrian

Published

2016

Language

EN