Scale-free percolation mixing time

DOI10.1016/J.SPA.2023.104236MaRDI QIDQ6145597zbMATH OpenOpenAlexFDO

Authors Alessandra Cipriani, Michele Salvi

Publication date 9 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• Bootstrap percolation on geometric inhomogeneous random graphs
• Clustering and the hyperbolic geometry of complex networks
• Cutoff phenomena for random walks on random regular graphs
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Geometric inhomogeneous random graphs
• Graph distances in scale-free percolation: the logarithmic case
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Large degrees in scale-free inhomogeneous random graphs
• Large deviations of sums of independent random variables
• 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.
• Notes on random walks in the Cauchy domain of attraction
• On a conditionally Poissonian graph process
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Random walks on small world networks
• Random walks on the random graph
• Recurrence versus transience for weight-dependent random connection models
• Rumors spread slowly in a small-world spatial network
• Scale-free percolation
• Scale-free percolation in continuous space: quenched degree and clustering coefficient
• Scale-free percolation in continuum space
• Simple random walk on long range percolation clusters. I: Heat kernel bounds
• Spatial preferential attachment networks: power laws and clustering coefficients
• Spectral gap of random hyperbolic graphs and related parameters
• Structures in supercritical scale-free percolation
• The age-dependent random connection model
• The diameter of long-range percolation clusters on finite cycles
• Ultra-small scale-free geometric networks

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)