Search for: All records

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_{\rm FR} > t )$$ of first return times from a random initial node to itself. It is found that $$P ( T_{\rm 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_{\rm FR} ]$$. Surprisingly, $${\mathbb E}[ T_{\rm FR} ]$$ coincides with the result obtained from Kac's lemma that applies to simple random walks (RWs). We also calculate the variance $${\rm Var}(T_{\rm FR})$$, which accounts for the variability of first return times between different NBW trajectories. We apply this formalism to Erd{\H o}s-R\'enyi networks, random regular graphs and configuration model networks with exponential and power-law degree distributions and obtain closed-form expressions for $$P( T_{\rm 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.