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

Dor Lev-Ari, Ido Tishby, Ofer Biham, Eytan Katzav, Diego Krapf · 2024

Read Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks by Dor Lev-Ari, Ido Tishby, Ofer Biham, Eytan Katzav, Diego Krapf (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12341.txt.

Introduction

Dor Lev-Ari and co-authors solve a random walk problem in 2024 on random networks. Their walker hops between connected nodes but never steps back to the node it just came from. Starting from a random node, they ask how long until the walker first returns to its start.

The tail of that return-time spread turns out to be a clean transform of the network's degree spread, the count of links per node. The mean return time matches, surprisingly, the classic value for ordinary walks that may backtrack. They also compute the spread's variance and give closed forms for several standard network families, including random and scale-free ones. The results tie network shape to walk timing.

Catalog record

CREATORDor Lev-Ari, Ido Tishby, Ofer Biham, Eytan Katzav, Diego Krapf
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-12341

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks Dor Lev-Ari, Ido Tishby, Ofer Biham, Eytan Katzav, Diego Krapf 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 N nodes with degree distribution P ⁡ ( k ) P(k) . We focus on the case in which the network consists of a single connected component. Starting from a random initial node i i at time t = 0 t=0 , an NBW hops into a random neighbor of i i at time t = 1 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 FR > t ) P(T_{\rm FR}>t) of first return times from a random initial node to itself. It is found that P ⁡ ( T FR > t ) P(T_{\rm FR}>t) is given by a discrete Laplace transform of the degree distribution P ⁡ ( k ) 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 𝔼 ⁡ [ T FR ] {\mathbb{E}}[T_{\rm FR}] . Surprisingly, 𝔼 ⁡ [ T FR ] {\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 Var ⁡ ( T FR ) {\rm Var}(T_{\rm FR}) , which accounts for the variability of first return times between different NBW trajectories. We apply this formalism to Erdő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 FR > t ) 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. , , , , Keywords : Random network, configuration model, random walk, first return time. ∗ Author to whom any correspondence should be addressed. 1 Introduction Random walk (RW) models [ 1 ] provide useful tools for the analysis of dynamical processes on random networks [ 2 , 3 , 5 , 4 , 6 , 7 ] . Here we focus on the case of undirected networks. Starting at time t=0 from a random initial node i , at each time step t\geq 1 an RW (also referred to as a simple RW) hops randomly to one of the neighbors of its current node. In some of the time steps the RW visits nodes that have not been visited before, while in other time steps it revisits nodes that have already been visited at an earlier time. The mean number \langle S\rangle_{t} of distinct nodes visited by an RW on a random network up to time t was studied in Ref. [ 8 ] . It was found that in the infinite network limit, in which random networks exhibit a tree structure, \langle S\rangle_{t}\simeq rt , where the coefficient r<1 depends on the network topology. In this case, the revisits are due to backtracking steps in which the RW hops back to the previous node and subsequent retroceding steps in which it keeps hopping backwards along its own path [ 9 ] . In order to perform systematic studies of random walks on random networks, it is useful to focus on configuration model networks. The configuration model is an ensemble of uncorrelated random networks consisting of N nodes, whose degree sequences are drawn from a given degree distribution P(k) . The admissible degrees are often restricted to a finite range k_{\rm min}\leq k\leq k_{\rm max} , where k_{\rm min} is the minimal degree and k_{\rm max} is the maximal degree, such that for any value of k outside this range P(k)=0 . The mean degree \langle K\rangle is denoted by c . To ensure that an RW starting from any initial node i will be able to reach any other node j , we focus on the case in which the whole network consists of a single connected component. Using the terminology of percolation theory, these are networks in which the giant component encompasses the whole network. In the large network limit, a sufficient condition for a configuration model network to consist of a single connected component is that k_{\rm min}\geq 3 [ 10 , 6 ] . In fact, a weaker condition of k_{\rm min}\geq 2 is sufficient in the large network limit as long as a finite fraction of the nodes satisfy k\geq 3 [ 11 ] . We thus avoid isolated nodes of degree k=0 and leaf nodes of degree k=1 , which may form isolated tree structures. The first return (FR) time T_{\rm FR} of an RW is the first time at which it returns to the initial node i [ 12 ] . The first return time varies between different instances of the random walk trajectory and its properties can be captured by a suitable distribution. The distribution of first return times may depend on the specific realization of the random network and on the choice of the initial node i . The distribution of first return times from a random node to itself in a given ensemble of random networks is denoted by P(T_{\rm FR}=t) . A classical result regarding first return times is Kac’s lemma, which states that the mean first return time of an RW from a given node i to itself is given by [ 13 , 14 , 15 ] {\mathbb{E}}[T_{\rm FR}(i)]=\frac{1}{P_{i}(\infty)}, (1) where P_{i}(\infty) is the probability that an RW will reside at node i at a given time step under steady state conditions (which are achieved in the long time limit t\rightarrow\infty ). In the case of undirected networks, Eq. ( 1 ) can be expressed in a more explicit form, namely [ 15 ] {\mathbb{E}}[T_{\rm FR}(i)]=\frac{Nc}{k_{i}}, (2) where k_{i} is the degree of node i . This implies that the mean first return time from a random node to itself is given by {\mathbb{E}}[T_{\rm FR}]=\bigg\langle\frac{Nc}{K}\bigg\rangle, (3) where \langle X\rangle is the average of the random variable X over the degree distribution P(k) . One can distinguish between two types of first return trajectories: first return trajectories in which the RW retrocedes its own steps backwards all the way back to the initial node i and first return trajectories in which the RW returns to i via a path that does not retrocede its own steps [ 9 , 16 ] . In the retroceding trajectories, each edge that belongs to the RW trajectory is crossed the same number of times in the forward and backward directions. In the non-retroceding trajectories the RW path includes at least one cycle. In the infinite system limit, in which the network exhibits a tree structure, the only way to return to the initial node is via a retroceding trajectory [ 17 , 18 ] . In finite networks both scenarios

Read the complete text