Density Independent Algorithms for Sparsifying $k$-Step Random Walks

Gorav Jindal, Pavel Kolev, Richard Peng +1

We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also for…