NON-BACKTRACKING RANDOM WALKS MIX FASTER

DOI10.1142/S0219199707002551zbMath1140.60301arXivmath/0610550OpenAlexW3100428187MaRDI QIDQ3502774

Sasha Sodin, Noga Alon, Itai Benjamini, Eyal Lubetzky

Publication date: 20 May 2008

Published in: Communications in Contemporary Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Chebyshev polynomialsmixing rateballs and binshigh-girth regular expander

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05)

Related Items (66)

Markov chains on finite fields with deterministic jumps ⋮ Analytical results for the distribution of cover times of random walks on random regular graphs ⋮ Ramanujan graphings and correlation decay in local algorithms ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ A new method for quantifying network cyclic structure to improve community detection ⋮ Cutoff on all Ramanujan graphs ⋮ The cover time of a biased random walk on a random cubic graph ⋮ Mean-field conditions for percolation on finite graphs ⋮ Poisson approximation for non-backtracking random walks ⋮ Functional limit theorems for random regular graphs ⋮ On the exponential generating function for non-backtracking walks ⋮ Séta: Supersingular Encryption from Torsion Attacks ⋮ A new weighted Ihara zeta function for a graph ⋮ CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ Random walks and diffusion on networks ⋮ Supersingular curves you can trust ⋮ Matrix functions in network analysis ⋮ Kemeny's constant for nonbacktracking random walks ⋮ On the almost eigenvectors of random regular graphs ⋮ Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs ⋮ The limit theorem with respect to the matrices on non-backtracking paths of a graph ⋮ Combinatorial statistics and the sciences ⋮ The spectral edge of some random band matrices ⋮ Non-backtracking random walk ⋮ New constructions of collapsing hashes ⋮ Spectral redemption in clustering sparse networks ⋮ Spectral theory of the non-backtracking Laplacian for graphs ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Simple versus nonsimple loops on random regular graphs ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis ⋮ Unnamed Item ⋮ An estimate for the average spectral measure of random band matrices ⋮ On the spectral analysis of second-order Markov chains ⋮ Expander graphs -- both local and global ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ On the Number of Perfect Matchings in Random Lifts ⋮ Beyond non-backtracking: non-cycling network centrality measures ⋮ Analysis of node2vec random walks on networks ⋮ Greedy Random Walk ⋮ Hypercube percolation ⋮ Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk ⋮ Unnamed Item ⋮ Some spectral properties of the non-backtracking matrix of a graph ⋮ Cutoff phenomena for random walks on random regular graphs ⋮ Characterizing limits and opportunities in speeding up Markov chain mixing ⋮ Approximate Moore graphs are good expanders ⋮ Cycle density in infinite Ramanujan graphs ⋮ Reversibility of the non-backtracking random walk ⋮ Recent results of quantum ergodicity on graphs and further investigation ⋮ A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs ⋮ Some observations on the smallest adjacency eigenvalue of a graph ⋮ Deterministic walks with choice ⋮ Spectra of random regular hypergraphs ⋮ Identification protocols and signature schemes based on supersingular isogeny problems ⋮ Balanced Allocation on Graphs: A Random Walk Approach ⋮ Non-Backtracking Alternating Walks ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Comparing mixing times on sparse random graphs ⋮ Nonbacktracking Eigenvalues under Node Removal: X-Centrality and Targeted Immunization ⋮ Mixing time of fractional random walk on finite fields ⋮ The non-backtracking spectrum of the universal cover of a graph ⋮ Non-backtracking PageRank ⋮ Discrete Graphs – A Paradigm Model for Quantum Chaos ⋮ The distribution of first hitting times of non-backtracking random walks on Erdős–Rényi networks ⋮ Analytical results for the distribution of first hitting times of random walks on random regular graphs

Cites Work

• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalues and expanders
• The expected eigenvalue distribution of a large regular graph
• On the second eigenvalue of a graph
• Spectra of regular graphs and hypergraphs and orthogonal polynomials
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Balanced Allocations
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Probability and Computing

This page was built for publication: NON-BACKTRACKING RANDOM WALKS MIX FASTER