An approximation for return time distributions of random walks on sparse networks

Abstract

We propose an approximation for the first return time distribution of random walks on undirected networks. We combine a message-passing solution with a mean-field approximation, to account for the short- and long-term behaviours respectively. We test this approximation on several classes of large graphs and find excellent agreement between our approximations and the true distributions. While the statistical properties of a random walk will depend on the structure of the network, the observed agreement between our approximations and numerical calculations implies that while local structure is clearly very influential, global structure is only important in a relatively superficial way, namely through the total number of edges.

References in corpus (8)

• Maps of random walks on complex networks reveal community structure
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Phase transition in the detection of modules in sparse networks
• Return times of random walk on generalized random graphs
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Preferential Behaviour and Scaling in Diffusive Dynamics on Networks
• Heterogeneous message passing for heterogeneous networks

Cited by in corpus (1)

• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks