Random Walks and Evolving Sets: Faster Convergences and Limitations

DOI10.1137/1.9781611974782.121zbMATH Open1410.05182arXiv1507.02069OpenAlexW792200198MaRDI QIDQ4575867FDOQ4575867

Authors: Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Analyzing the mixing time of random walks is a well-studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analysis of random walks and evolving sets using more combinatorial graph structures, and show some implications in approximating small-set expansion. On the other hand, we provide examples showing the limitations of using random walks and evolving sets in disproving the small-set expansion hypothesis. - We define a combinatorial analog of the spectral gap, and use it to prove the convergence of non-lazy random walks. A corollary is a tight lower bound on the small-set expansion of graph powers for any graph. - We prove that random walks converge faster when the robust vertex expansion of the graph is larger. This provides an improved analysis of the local graph partitioning algorithm using the evolving set process. - We give an example showing that the evolving set process fails to disprove the small-set expansion hypothesis. This refutes a conjecture of Oveis Gharan and shows the limitations of local graph partitioning algorithms in approximating small-set expansion.

Full work available at URL: https://arxiv.org/abs/1507.02069

Recommendations

• Scaling random walks on arbitrary sets
• Publication:4206154
• Random walks with stochastically bounded increments: Foundations and characterization results
• scientific article; zbMATH DE number 759594
• A bound for the distribution of the hitting time of arbitrary sets by random walk
• The rate of convergence of the walk on spheres algorithm
• Limit theorems for random walks that avoid bounded sets, with applications to the largest gap problem
• Estimation of the evolution of a random set
• Random Walks on Randomly Evolving Graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random walks on graphs (05C81)

Cited In (2)

• Gap amplification for small-set expansion via random walks
• Mean field analysis of personalized PageRank with implications for local graph clustering

This page was built for publication: Random Walks and Evolving Sets: Faster Convergences and Limitations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575867)