Mixing Time of Random Walk on Poisson Geometry Small World

DOI10.1080/15427951.2015.1012608MaRDI QIDQ3389690zbMATH OpenOpenAlexFDO

Authors Xian Yuan Wu

Publication date 23 March 2022

Published in Internet Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

continuous percolationmixing timerandom networksrandom walksmall world

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37)

Abstract: This paper focuses on the problem of modeling for small world effect on complex networks. Let's consider the supercritical Poisson continuous percolation on $d$-dimensional torus $T_n^d$ with volume $n^d$. By adding "long edges (short cuts)" randomly to the largest percolation cluster, we obtain a random graph $mathscr{G}_n$. In the present paper, we first prove that the diameter of $mathscr{G}_n$ grows at most polynomially fast in $lnn$ and we call it the Poisson Geometry Small World. Secondly, we prove that the random walk on $mathscr{G}_n$ possesses the rapid mixing property, namely, the random walk mixes in time at most polynomially large in $lnn$.

Recommendations

• The small world effect on the coalescing time of random walks
• The mixing time of the Newman-Watts small world
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Pseudo-mixing Time of Random Walks
• Mixing times of random walks on dynamic configuration models
• The Mixing Time of the Newman-Watts Small-World Model
• Mixing time of the adjacent walk on the simplex
• Isoperimetric inequalities and mixing time for a random walk on a random point process
• scientific article; zbMATH DE number 1241392

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Collective dynamics of `small-world' networks
• Continuum Percolation
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• Large deviations for discrete and continuous percolation
• Lower bounds for the eigenvalues of Laplacian matrices
• On a continuum percolation model
• Random graph dynamics
• Renormalization group analysis of the small-world network model
• Shuffling Cards and Stopping Times
• The Average Distance in a Random Graph with Given Expected Degrees
• The Diameter of a Cycle Plus a Random Matching
• The diameter of a scale-free random graph
• The Structure and Function of Complex Networks

Cited in

(7)

• Mixing time of molecules inside of nanoporous gold
• Random walks on small world networks
• On the modified Newman-Watts small world and its random walk
• The Mixing Time of the Newman-Watts Small-World Model
• Asymptotic Behaviour of Gossip Processes and Small-World Networks
• The small world effect on the coalescing time of random walks
• The mixing time of the Newman-Watts small world

This page was built for publication: Mixing Time of Random Walk on Poisson Geometry Small World

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