# Density Independent Algorithms for Sparsifying k-Step Random Walks

arXiv: https://arxiv.org/abs/1702.06110 · HTML: https://mlsanity.com/paper/1702.06110/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)

## Abstract (arXiv)

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