hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
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 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 $n\log{n}$ edges that
approximates the $k$-step random walk graph in about $m + n \log^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.
