Approximation for return time distributions of random walks on sparse networks

2025/06/11 by Erik Hormann, Renaud Lambiotte, George T. Cantwell · 1 voice
Physics and Astronomy · Mathematics · #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #Stochastic processes and statistical mechanics

paper · pdf · doi:10.1103/physreve.111.064306

openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

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 behaviors, 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.

Discussions

• The Kac formula says the average return time for a random walker is a wonderfully simple combination of global and local structure: 2m/k_i. Inspired by this result we characterize the full distributio [bsky, 2 points, 1 comments]

Related

• An approximation for return time distributions of random walks on sparse networks
• Return times of random walk on generalized random graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Embedding networks with the random walk first return time distribution
• First-passage time distribution for random walks on complex networks using inverse Laplace transform and mean-field approximation