Random walks on graphs: ideas, techniques and results

Abstract

Random walks on graphs are widely used in all sciences to describe a great variety of phenomena where dynamical random processes are affected by topology. In recent years, relevant mathematical results have been obtained in this field, and new ideas have been introduced, which can be fruitfully extended to different areas and disciplines. Here we aim at giving a brief but comprehensive perspective of these progresses, with a particular emphasis on physical aspects.

LateX file, 34 pages, 13 jpeg figures, Topical Review

References in corpus (4)

• Geometrical universality in vibrational dynamics
• The Type-problem on the Average for random walks on graphs
• Diffusion on non exactly decimable tree-like fractals
• Spectral partitions on infinite graphs

Cited by in corpus (96)

• Random walks and diffusion on networks
• Global mean first-passage times of random walks on complex networks
• Exact mean first-passage time on the T-graph
• Random walks on weighted networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Random Walks on deterministic Scale-Free networks: Exact results
• Entropy production and coarse-graining in Markov processes
• Determining global mean-first-passage time of random walks on Vicsek fractals using eigenvalues of Laplacian matrices
• Determining mean first-passage time on a class of treelike regular fractals
• Random walks in weighted networks with a perfect trap: An application of Laplacian spectra
• Synchronization in Network Geometries with Finite Spectral Dimension
• Lévy walks and scaling in quenched disordered media
• Eigenvalues of normalized Laplacian matrices of fractal trees and dendrimers: Analytical results and applications
• Diffusion and subdiffusion of interacting particles on comb-like structures
• Random walks on the Apollonian network with a single trap
• Trapping in dendrimers and regular hyperbranched polymers
• Network Geometry and Complexity
• Exact analytical results for quantum walks on star graph
• Effective target arrangement in a deterministic scale-free graph
• Trapping in scale-free networks with hierarchical organization of modularity
• Mean first-passage time for random walks on the T-graph
• Does the brain behave like a (complex) network? I. Dynamics
• On the Fluctuation-Dissipation Relation in non-equilibrium and non-Hamiltonian systems
• Complex active optical networks as a new laser concept
• The topological Dirac equation of networks and simplicial complexes
• Random walks in modular scale-free networks with multiple traps
• Mean first-passage time for maximal-entropy random walks in complex networks
• Quantum Gravity as an Information Network: Self-Organization of a 4D Universe
• Role of fractal dimension in random walks on scale-free networks
• Exact Results on Itinerant Ferromagnetism and the 15-puzzle Problem
• The two-particle problem in comb-like structures
• Phase-ordering kinetics on graphs
• Slow Encounters of Particle Pairs in Branched Structures
• On anomalous diffusion and the out of equilibrium response function in one-dimensional models
• The meeting problem in the quantum random walk
• Autonomous search for a diffusive source in an unknown environment
• Complete spectrum of stochastic master equation for random walks on treelike fractals
• Aging dynamics and the topology of inhomogenous networks
• Right-side-stretched multifractal spectra indicate small-worldness in networks
• The LANER: optical networks as complex lasers
• Anomalous diffusion and response in branched systems: a simple analysis
• Heterogeneous excitable systems exhibit Griffiths phases below hybrid phase transitions
• Occupation times on a comb with ramified teeth
• Spectral properties of hyperbolic nano-networks with tunable aggregation of simplexes
• Lévy-type diffusion on one-dimensional directed Cantor Graphs
• The average number of distinct sites visited by a random walker on random graphs
• Random Holographic "Large Worlds" with Emergent Dimensions
• Geometry, Topology and Simplicial Synchronization
• Mixed random walks with a trap in scale-free networks including nearest-neighbor and next-nearest-neighbor jumps
• Universal features of information spreading efficiency on $d$-dimensional lattices
• Reaction Spreading on Graphs
• Probability distribution functions of sub- and super-diffusive systems
• Infinite networks and variation of conductance functions in discrete Laplacians
• Einstein relation in superdiffusive systems
• Multifractal cross-correlation effects in two-variable time series of complex network vertex observables
• Networks with many structural scales: a Renormalization Group perspective
• Network Renormalization
• Walk-Sums, Continued Fractions and Unique Factorisation on Digraphs
• Equilibrium statistical mechanics on correlated random graphs
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Topological regulation of activation barriers on fractal substrates
• Optimal scale-free network with a minimum scaling of transport efficiency for random walks with a perfect trap
• Network science Ising states of matter
• Multi-scale Laplacian community detection in heterogeneous networks
• Reaction spreading on percolating clusters
• Eigenvector localization as a tool to study small communities in online social networks
• Field theories and quantum methods for stochastic reaction-diffusion systems
• Crafting networks to achieve, or not achieve, chaotic states
• Phase ordering and universality for continuous symmetry models on graphs
• Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
• Local and average behavior in inhomogeneous superdiffusive media
• Non-equilibrium critical properties of the Ising model on product graphs
• Efficient network exploration by means of resetting self-avoiding random walkers
• Exactly solvable tight-binding models on two scale-free networks with identical degree distribution
• Information Dimension of Stochastic Processes on Networks: Relating Entropy Production to Spectral Properties
• Thermalization of isolated harmonic networks under conservative noise
• Deterministic Random Walk Model in NetLogo and the Identification of Asymmetric Saturation Time in Random Graph
• Symmetry-based coarse-graining of evolved dynamical networks
• Critical dynamics of long range models on Dynamical Lévy Lattices
• Target annihilation by diffusing particles in inhomogeneous geometries
• Relations between connected and self-avoiding walks in a digraph
• The asymptotic shape theorem for the frog model on finitely generated abelian groups
• Diffusion on asymmetric fractal networks
• Multiple predator based capture process on complex networks
• Understanding random-walk dynamical phase coexistence through waiting times
• From Laplacian-to-Adjacency Matrix for Continuous Spins on Graphs
• Local time of random walks on graphs
• Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Random walks on bifractal networks
• Linear and anomalous front propagation in system with non Gaussian diffusion: the importance of tails
• Dynamics of soft interacting particles on a comb
• Uniqueness of Gibbs fields with unbounded random interactions on unbounded degree graphs
• Leveraging History for Faster Sampling of Online Social Networks
• Asymptotic versus mesoscopic spectral dimensions in networks and inhomogeneous structures