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

Abstract

We present analytical results for the distribution of first return (FR) times of non-backtracking random walks (NBWs) on undirected configuration model networks consisting of $N$ nodes with degree distribution $P(k)$. We focus on the case in which the network consists of a single connected component. Starting from a random initial node $i$ at time $t=0$, an NBW hops into a random neighbor of $i$ at time $t=1$ and at each subsequent step it continues to hop into a random neighbor of its current node, excluding the previous node. We calculate the tail distribution $P(T_{\mathrm{FR}}>t)$ of first return times from a random initial node to itself. It is found that $P(T_{\mathrm{FR}}>t)$ is given by a discrete Laplace transform of the degree distribution $P(k)$. This result exemplifies the relation between structural properties of a network, captured by the degree distribution, and properties of dynamical processes taking place on the network. Using the tail-sum formula, we calculate the mean first return time $\mathbb{E}[T_{\mathrm{FR}}]$. Surprisingly, $\mathbb{E}[T_{\mathrm{FR}}]$ coincides with the result obtained from Kac's lemma that applies to simple random walks (RWs). We also calculate the variance $\mathrm{Var}(T_{\mathrm{FR}})$, which accounts for the variability of first return times between different NBW trajectories. We apply this formalism to Erd{\H o}s-Rényi networks, random regular graphs and configuration model networks with exponential and power-law degree distributions and obtain closed-form expressions for $P(T_{\mathrm{FR}}>t)$ as well as its mean and variance. These results provide useful insight on the advantages of NBWs over simple RWs in network exploration, sampling and search processes.

arXiv comment33 pages, 9 figures

References in corpus (35)

• Random graphs with arbitrary degree distributions and their applications
• Generation of uncorrelated random scale-free networks
• Random walks and diffusion on networks
• Spectral redemption: clustering sparse networks
• Cut-offs and finite size effects in scale-free networks
• Percolation on sparse networks
• Non-backtracking random walks mix faster
• Articulation Points in Complex Networks
• First Passage Properties of the Erdos-Renyi Random Graph
• Cutoff phenomena for random walks on random regular graphs
• Return times of random walk on generalized random graphs
• The diameter of sparse random graphs
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Non-backtracking random walk
• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Distribution of shortest cycle lengths in random networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi networks
• First encounters on Bethe Lattices and Cayley Trees
• The average number of distinct sites visited by a random walker on random graphs
• Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs
• Exact clesed form of the return probability on the Bethe lattice
• Statistical analysis of articulation points in configuration model networks
• Assortative and disassortative mixing investigated using the spectra of graphs
• 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
• The mean and variance of the distribution of shortest path lengths of 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
• Statistical analysis of edges and bredges in configuration model networks
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Effects of clustering heterogeneity on the spectral density of sparse networks
• The distribution of the number of cycles in directed and undirected random 2-regular graphs
• First return times on sparse random graphs
• An approximation for return time distributions of random walks on sparse networks