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.

22 pages, 4 figures

References in corpus (3)

• Collective dynamics of social annotation
• Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
• Extensive load in multitasking associative networks

Cited by in corpus (8)

• Network dynamics of innovation processes
• Analytical results for the distribution of first return times of random walks on random regular graphs
• 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
• Analytical results for the distribution of first hitting 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
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks