Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917141927690240 |
|---|---|
| author | Lev-Ari, Dor Tishby, Ido Biham, Ofer Katzav, Eytan Krapf, Diego |
| author_facet | Lev-Ari, Dor Tishby, Ido Biham, Ofer Katzav, Eytan Krapf, Diego |
| contents | 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ényi 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12341 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks Lev-Ari, Dor Tishby, Ido Biham, Ofer Katzav, Eytan Krapf, Diego Statistical Mechanics Physics and Society 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ényi 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. |
| title | Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks |
| topic | Statistical Mechanics Physics and Society |
| url | https://arxiv.org/abs/2412.12341 |