Scale-free percolation mixing time

DOI10.1016/J.SPA.2023.104236zbMATH Open1530.05171arXiv2111.05201OpenAlexW3212097972MaRDI QIDQ6145597FDOQ6145597

Authors: Alessandra Cipriani, Michele Salvi 

Publication date: 9 January 2024

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: Assign to each vertex of the one-dimensional torus i.i.d. weights with a heavy-tail of index $au-1>0$. Connect then each couple of vertices with probability roughly proportional to the product of their weights and that decays polynomially with exponent $alpha>0$ in their distance. The resulting graph is called scale-free percolation. The goal of this work is to study the mixing time of the simple random walk on this structure. We depict a rich phase diagram in $alpha$ and $au$. In particular we prove that the presence of hubs can speed up the mixing of the chain. We use different techniques for each phase, the most interesting of which is a bootstrap procedure to reduce the model from a phase where the degrees have bounded averages to a setting with unbounded averages.

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

Recommendations

• Scale-free percolation
• Long-Range Percolation Mixing Time
• The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
• Random walks on the random graph
• Graph distances in scale-free percolation: the logarithmic case

zbMATH Keywords

random graphmixing timedegree distributionscale-free percolation

Mathematics Subject Classification ID

Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Title not available (Why is that?)
• On a conditionally Poissonian graph process
• Large deviations of sums of independent random variables
• Random walks on the random graph
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Cutoff phenomena for random walks on random regular graphs
• Scale-free percolation
• Ultra-small scale-free geometric networks
• The diameter of long-range percolation clusters on finite cycles
• Simple random walk on long range percolation clusters. I: Heat kernel bounds
• Long-Range Percolation Mixing Time
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Notes on random walks in the Cauchy domain of attraction
• Random walks on small world networks
• Scale-free percolation in continuum space
• Clustering and the hyperbolic geometry of complex networks
• Spectral gap of random hyperbolic graphs and related parameters
• Geometric inhomogeneous random graphs
• Spatial preferential attachment networks: power laws and clustering coefficients
• Bootstrap percolation on geometric inhomogeneous random graphs
• Structures in supercritical scale-free percolation
• Large degrees in scale-free inhomogeneous random graphs
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Rumors spread slowly in a small-world spatial network
• The age-dependent random connection model
• Recurrence versus transience for weight-dependent random connection models
• Scale-free percolation in continuous space: quenched degree and clustering coefficient
• Graph distances in scale-free percolation: the logarithmic case

Cited In (1)

• Cover and hitting times of hyperbolic random graphs

This page was built for publication: Scale-free percolation mixing time

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