Density Independent Algorithms for Sparsifying k-Step Random Walks

الأصل · EN

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 nn edges that approximates the k-step random walk graph in about m + n ⁴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.