Return times of random walk on generalized random graphs

Abstract

Random walks are used for modeling various dynamics in, for example, physical, biological, and social contexts. Furthermore, their characteristics provide us with useful information on the phase transition and critical phenomena of even broader classes of related stochastic models. Abundant results are obtained for random walk on simple graphs such as the regular lattices and the Cayley trees. However, random walks and related processes on more complex networks, which are often more relevant in the real world, are still open issues, possibly yielding different characteristics. In this paper, we investigate the return times of random walks on random graphs with arbitrary vertex degree distributions. We analytically derive the distributions of the return times. The results are applied to some types of networks and compared with numerical data.

3 figures

References in corpus (13)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Epidemic spreading in scale-free networks
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Epidemic threshold in structured scale-free networks
• Spectra and eigenvectors of scale-free networks
• Random spread on the family of small-world networks
• Transmission of severe acute respiratory syndrome in dynamical small-world networks
• Scaling of random spreading in small world networks
• Branching annihilating random walk on random regular graphs
• Criticality in confined ionic fluids

Cited by in corpus (17)

• Voter Model on Heterogeneous Graphs
• Random walks and diffusion on networks
• The noisy voter model on complex networks
• First Passage Properties of the Erdos-Renyi Random Graph
• Spectral dimensions of hierarchical scale-free networks with shortcuts
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Kinetic growth walks on complex networks
• Extremal dynamics on complex networks: Analytic solutions
• Analysis of fluctuations in the first return times of random walks on regular branched networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• First return times on sparse random graphs
• An approximation for return time distributions of random walks on sparse networks
• Statistical field theory of random graphs with prescribed degrees
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Universal scaling hypothesis of quantum spatial search in complex networks