First return times on sparse random graphs
arXiv:2408.10530 · doi:10.1088/1751-8121/adb084
Abstract
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.
arXiv commentv2: comments and references added, published version
References in corpus (23)
- Quantum Field Theory in the Large N Limit: a review
- Solution of the 2-star model of a network
- Sparse random matrices: the eigenvalue spectrum revisited
- Spectra of Euclidean Random Matrices
- Spectra of Sparse Random Matrices
- Renormalization group, secular term resummation and AdS (in)stability
- First Passage Properties of the Erdos-Renyi Random Graph
- Return times of random walk on generalized random graphs
- Finite size correction to the spectrum of regular random graphs: an analytical solution
- Stress Relaxation of Near-Critical Gels
- Analytical results for the distribution of first return times of random walks on random regular graphs
- The average number of distinct sites visited by a random walker on random graphs
- The two-star model: exact solution in the sparse regime and condensation transition
- Random matrices with row constraints and eigenvalue distributions of graph Laplacians
- The distribution of first hitting times of random walks on Erdős-Rényi networks
- Statistical properties of eigenvectors and eigenvalues of structured random matrices
- The distribution of first hitting times of random walks on directed Erdős-Rényi networks
- Analytical results for the distribution of cover times of random walks on 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
- The integrated density of states of the random graph Laplacian
- Entropy of microcanonical finite-graph ensembles
- A Gaussian integral that counts regular graphs