文章基本信息

标题：Density Independent Algorithms for Sparsifying k-Step Random Walks
本地全文：下载
作者：Gorav Jindal ; Pavel Kolev ; Richard Peng 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：14:1-14:17
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：random walks; graph sparsification; spectral graph theory; effective resistances