First return times on sparse random graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917921145487360 |
|---|---|
| author | Evnin, Oleg Horinouchi, Weerawit |
| author_facet | Evnin, Oleg Horinouchi, Weerawit |
| contents | We consider random walks in the form of nearest-neighbor hopping on Erdos-Renyi random graphs of finite fixed mean degree c as the number of vertices N tends to infinity. In this regime, using statistical field theory methods, we develop an analytic theory of the first return time probability distribution. The problem turns out closely related to finding the spectrum of the normalized graph Laplacian that controls the continuum time version of the nearest-neighbor-hopping random walk. In the infinite graph limit, where loops are highly improbable, the returns operate in a manner qualitatively similar to c-regular trees, and the expressions for probabilities resemble those on random c-regular graphs. Because the vertex degrees are not exactly constant, however, the way c enters the formulas differs from the dependence on the graph degree of first return probabilities on random regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10530 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | First return times on sparse random graphs Evnin, Oleg Horinouchi, Weerawit Disordered Systems and Neural Networks Statistical Mechanics Mathematical Physics Probability We consider random walks in the form of nearest-neighbor hopping on Erdos-Renyi random graphs of finite fixed mean degree c as the number of vertices N tends to infinity. In this regime, using statistical field theory methods, we develop an analytic theory of the first return time probability distribution. The problem turns out closely related to finding the spectrum of the normalized graph Laplacian that controls the continuum time version of the nearest-neighbor-hopping random walk. In the infinite graph limit, where loops are highly improbable, the returns operate in a manner qualitatively similar to c-regular trees, and the expressions for probabilities resemble those on random c-regular graphs. Because the vertex degrees are not exactly constant, however, the way c enters the formulas differs from the dependence on the graph degree of first return probabilities on random regular graphs. |
| title | First return times on sparse random graphs |
| topic | Disordered Systems and Neural Networks Statistical Mechanics Mathematical Physics Probability |
| url | https://arxiv.org/abs/2408.10530 |