Jindal, Gorav
[Author];
Kolev, Pavel
[Author];
Peng, Richard
[Author];
Sawlani, Saurabh
[Author]
;
Gorav Jindal and Pavel Kolev and Richard Peng and Saurabh Sawlani
[Contributor]
Density Independent Algorithms for Sparsifying k-Step Random Walks
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
We give faster algorithms for producing sparse approximations of the transition matrices of k-step random walks on undirected and weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with n vertices and m edges, our algorithm produces a graph with about nlog(n) edges that approximates the k-step random walk graph in about m + k^2 nlog^4(n) time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.