2023/10/18 by Giulio Iacobelli, Iacobelli, Giulio, Guilherme Ost +3
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Complex Network Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2310.12355
We study random walks on Erdös-Rényi random graphs in which, every time the random walk returns to the starting point, first an edge probability is independently sampled according to a priori measure μ, and then an Erdös-Rényi random graph is sampled according to that edge probability. When the edge probability p does not depend on the size of the graph n (dense case), we show that the proportion of time the random walk spends on different values of p -- \it occupation measure -- converges to the a priori measure μ as n goes to infinity. More interestingly, when p=λ/n (sparse case), we show that the occupation measure converges to a limiting measure with a density that is a function of the survival probability of a Poisson branching process. This limiting measure is supported on the supercritial values for the Erdös-Rényi random graphs, showing that self-witching random walks can detect the phase transition.