2015/01/31 by Caterina De Bacco, Satya N. Majumdar, Satya N Majumdar +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Graph theory and applications #Random graph #Random variable #Random walk #Random walker algorithm #Sequence (biology) #Theoretical and Computational Physics #cond-mat.dis-nn #cond-mat.stat-mech #physics.data-an
paper · pdf · doi:10.1088/1751-8113/48/20/205004
published as J. Phys. A: Math. Theor. 48 (2015) 205004 · 22 pages, 4 figures
arxiv created 2015/03/30 · openalex publication_date 2015/04/29 · arxiv updated 2015/05/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
We study the linear large- n behaviour of the average number of distinct sites S ( n ) visited by a random walker after n steps on a large random graph. An expression for the graph topology-dependent prefactor B in S ( n ) = Bn is proposed. We use generating function techniques to relate this prefactor to the graph adjacency matrix and then devise message-passing equations to calculate its value. Numerical simulations are performed to evaluate the agreement between the message passing predictions and random walk simulations on random graphs. Scaling with system size and average graph connectivity are also analysed.