Actions
  • share
Powered by OpenAIRE Research Graph
See an issue? Give us feedback
share
auto_awesome_motion View all 3 versions
Publication . Conference object . Preprint . Article . 2016

Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs

Michael B. Cohen; Jonathan A. Kelner; John Peebles; Richard Peng; Anup Rao; Aaron Sidford; Adrian Vladu;
Open Access   English  

doi: 10.1145/3055399.3055463

Published: 02 Nov 2016
Country: United States
Abstract
In this paper we introduce a notion of spectral approximation for directed graphs. While there are many potential ways one might define approximation for directed graphs, most of them are too strong to allow sparse approximations in general. In contrast, we prove that for our notion of approximation, such sparsifiers do exist, and we show how to compute them in almost linear time. Using this notion of approximation, we provide a general framework for solving asymmetric linear systems that is broadly inspired by the work of [Peng-Spielman, STOC`14]. Applying this framework in conjunction with our sparsification algorithm, we obtain an almost linear time algorithm for solving directed Laplacian systems associated with Eulerian Graphs. Using this solver in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16], we obtain almost linear time algorithms for solving a directed Laplacian linear system, computing the stationary distribution of a Markov chain, computing expected commute times in a directed graph, and more. For each of these problems, our algorithms improves the previous best running times of $O((nm^{3/4} + n^{2/3} m) \log^{O(1)} (n \kappa \epsilon^{-1}))$ to $O((m + n2^{O(\sqrt{\log{n}\log\log{n}})}) \log^{O(1)} (n \kappa \epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the number of edges, $\kappa$ is a natural condition number associated with the problem, and $\epsilon$ is the desired accuracy. We hope these results open the door for further studies into directed spectral graph theory, and will serve as a stepping stone for designing a new generation of fast algorithms for directed graphs.
Subjects by Vocabulary

ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS

Microsoft Academic Graph classification: Time complexity Directed graph Graph (abstract data type) Spectral graph theory Solver Stationary distribution Discrete mathematics Markov chain Algorithm Mathematics Combinatorics Condition number

Subjects

Computer Science - Data Structures and Algorithms

Related Organizations
View all
40 references, page 1 of 4

~xm;~ya6=x0 p~x>UA~x ~y>UA~y

[3] Gely P Basharin, Amy N Langville, and Valeriy A Naumov. The life and work of aa markov. Linear Algebra and its Applications, 386:3-26, 2004.

[4] Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. SIAM Journal on Computing, 41(6):1704-1721, 2012.

[5] Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56(8):87-94, August 2013.

[6] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in O~(n2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of computing, STOC '96, pages 47-55, New York, NY, USA, 1996. ACM.

[7] Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng. cient sampling for Gaussian graphical models via spectral sparsification. ings of The 28th Conference on Learning Theory, pages 364-390, 2015. http://jmlr.org/proceedings/papers/v40/Cheng15.pdf.

[10] Fan Chung and Olivia Simpson. Computing heat kernel pagerank and a local clustering algorithm. In Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers, pages 110-121, 2014.

[11] Fan Chung and Wenbo Zhao. A sharp pagerank algorithm with applications to edge ranking and graph sparsification. In International Workshop on Algorithms and Models for the WebGraph, pages 2-14. Springer, 2010.

[12] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. arXiv preprint arXiv:1608.03270, 2016.

[13] Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup Rao, and Shen Chen Xu. Solving SDD linear systems in nearly m log1=2 n time. In STOC, pages 343-352, 2014.

Powered by OpenAIRE Research Graph
See an issue? Give us feedback
Funded by
NSF| Graduate Research Fellowship Program
Project
Graduate Research Fellowship Program
  • Funder: National Science Foundation (NSF)
  • Project Code: 1122374
  • Funding stream: Directorate for Education & Human Resources | Division of Graduate Education
, NSF| AF: Medium: Taming Masssive Data with Sub-Linear Algorithms
Project
AF: Medium: Taming Masssive Data with Sub-Linear Algorithms
  • Funder: National Science Foundation (NSF)
  • Project Code: 1065125
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
, NSF| AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
Project
AF: Large: Collaborative Research: Algebraic Graph Algorithms: The Laplacian and Beyond
  • Funder: National Science Foundation (NSF)
  • Project Code: 1111109
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
Download fromView all 4 sources
lock_open
http://dl.acm.org/ft_gateway.c...
Conference object
Providers: UnpayWall