Jindal, Gorav
[VerfasserIn];
Kolev, Pavel
[VerfasserIn];
Peng, Richard
[VerfasserIn];
Sawlani, Saurabh
[VerfasserIn]
;
Gorav Jindal and Pavel Kolev and Richard Peng and Saurabh Sawlani
[MitwirkendeR]
Density Independent Algorithms for Sparsifying k-Step Random Walks
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.