The average number of distinct sites visited by a random walker on random graphs

Abstract

We study the linear large $n$ behavior of the average number of distinct sites $S(n)$ visited by a random walker after $n$ steps on a large random graph. An expression for the graph topology dependent prefactor $B$ in $S(n)=Bn$ is proposed. We use generating function techniques to relate this prefactor to the graph adjacency matrix and then devise message-passing equations to calculate its value. Numerical simulations are performed to evaluate the agreement between the message passing predictions and random walk simulations on random graphs. Scaling with system size and average graph connectivity are also analysed.

arXiv comment22 pages, 4 figures

References in corpus (10)

• Emergence of scaling in random networks
• Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
• Random walks on graphs: ideas, techniques and results
• Diffusion, localization and dispersion relations on ``small-world'' lattices
• Collective dynamics of social annotation
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Extensive load in multitasking associative networks
• Networking - A Statistical Physics Perspective
• Exact distributions of the number of distinct and common sites visited by N independent random walkers
• Number of Common Sites Visited by N Random Walkers

Cited by in corpus (14)

• Network dynamics of innovation processes
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Dynamic topologies of activity-driven temporal networks with memory
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Analytical results for the distribution of first hitting times of random walks on random regular graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• The joint distribution of first return times and of the number of distinct sites visited by a 1D random walk before returning to the origin
• First return times on sparse random graphs
• Exit probability and first passage time of a lazy Pearson walker: Scaling behaviour
• Model and Statistical Analysis of the Motion of a Tired Random Walker in Continuum
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks