Random walks and diffusion on networks

Abstract

Random walks are ubiquitous in the sciences, and they are interesting from both theoretical and practical perspectives. They are one of the most fundamental types of stochastic processes; can be used to model numerous phenomena, including diffusion, interactions, and opinions among humans and animals; and can be used to extract information about important entities or dense groups of entities in a network. Random walks have been studied for many decades on both regular lattices and (especially in the last couple of decades) on networks with a variety of structures. In the present article, we survey the theory and applications of random walks on networks, restricting ourselves to simple cases of single and non-adaptive random walkers. We distinguish three main types of random walks: discrete-time random walks, node-centric continuous-time random walks, and edge-centric continuous-time random walks. We first briefly survey random walks on a line, and then we consider random walks on various types of networks. We extensively discuss applications of random walks, including ranking of nodes (e.g., PageRank), community detection, respondent-driven sampling, and opinion models such as voter models.

12 figures, 2 tables; [v3] reflects the corrections we made in the two corrigenda (Physics Reports, 745, 96 (2018) and ibid., 851, 37-39 (2020))

References in corpus (77)

• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Maps of random walks on complex networks reveal community structure
• Statistical physics of social dynamics
• Synchronization in complex networks
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Critical phenomena in complex networks
• Statistical Mechanics of Community Detection
• Community detection in networks: A user guide
• Discrete Signal Processing on Graphs
• Vital nodes identification in complex networks
• Diffusion dynamics on multiplex networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Activity driven modeling of time varying networks
• Line Graphs, Link Partitions and Overlapping Communities
• First-passage times in complex scale-invariant media
• The Rich-Club Phenomenon In The Internet Topology
• A survey of random processes with reinforcement
• Mixture models and exploratory analysis in networks
• Robust Detection of Dynamic Community Structure in Networks
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Voter Models on Heterogeneous Networks
• Percolation on sparse networks
• Characterizing the dynamical importance of network nodes and links
• Ranking in evolving complex networks
• Scaling theory of transport in complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Entropy Rate of Diffusion Processes on Complex Networks
• Random walks and search in time-varying networks
• Topology-driven instabilities: the theory of pattern formation on directed networks
• Quantifying patterns of research interest evolution
• Who is the best player ever? A complex network analysis of the history of professional tennis
• Self-similar disk packings as model spatial scale-free networks
• Spectral coarse-graining of complex networks
• Exact mean first-passage time on the T-graph
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Maximal-entropy random walks in complex networks with limited information
• Random walks on weighted networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Effective Distances for Epidemics Spreading on Complex Networks
• The Continuous Time Random Walk, still trendy: Fifty-year history, state of art, and outlook
• A network-based ranking system for American college football
• Eigenfactor : Does the Principle of Repeated Improvement Result in Better Journal Impact Estimates than Raw Citation Counts?
• Exploring Complex Networks through Random Walks
• Random graph models for directed acyclic networks
• Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that
• Spectral Coarse Graining and Synchronization in Oscillator Networks
• Evolutionary dynamics and fixation probabilities in directed networks
• Cover time for random walks on arbitrary complex networks
• Safe Leads and Lead Changes in Competitive Team Sports
• Random walks on complex trees
• Random walks on complex networks with inhomogeneous impact
• The escape problem for mortal walkers
• Tight lower bound for percolation threshold on a quasi-regular graph
• Random walks on activity-driven networks with attractiveness
• Trapping in complex networks
• Record statistics of a strongly correlated time series: random walks and Lévy flights
• Impact of community structure on information transfer
• Random walks on the Apollonian network with a single trap
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Ring structures and mean first passage time in networks
• Return times of random walk on generalized random graphs
• Steady state and mean recurrence time for random walks on stochastic temporal networks
• Depletion-Controlled Starvation of a Diffusing Forager
• Bounding network spectra for network design
• Exact calculations of first-passage properties on the pseudofractal scale-free web
• Non-backtracking random walk
• Impact of hierarchical modular structure on ranking of individual nodes in directed networks
• Analysis of relative influence of nodes in directed networks
• Origin of the hub spectral dimension in scale-free networks
• Starvation Dynamics of a Greedy Forager
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Networks maximizing the consensus time of voter models
• Random Walks on Complex Networks

Cited by in corpus (200)

• Networks beyond pairwise interactions: structure and dynamics
• Social physics
• COVID-19 lockdown induces disease-mitigating structural changes in mobility networks
• The Statistical Physics of Real-World Networks
• What are higher-order networks?
• Network Geometry
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Network Analysis of Particles and Grains
• The synchronized dynamics of time-varying networks
• Multi-body Interactions and Non-Linear Consensus Dynamics on Networked Systems
• A spectrum of routing strategies for brain networks
• Random walks on networks with stochastic resetting
• Defining a historic football team: Using Network Science to analyze Guardiola's F.C. Barcelona
• Measuring the academic reputation through citation networks via PageRank
• Epidemic Spreading on Activity-Driven Networks with Attractiveness
• Extractive Multi-document Summarization Using Multilayer Networks
• Laplacian Renormalization Group for heterogeneous networks
• Detecting sequences of system states in temporal networks
• Core-periphery structure requires something else in the network
• Diffusion coefficient of a Brownian particle in equilibrium and nonequilibrium: Einstein model and beyond
• Statistical physics of complex information dynamics
• Neuromorphic scaling advantages for energy-efficient random walk computation
• Diffusive transport on networks with stochastic resetting to multiple nodes
• Does the brain behave like a (complex) network? I. Dynamics
• Complex Quantum Networks: a Topical Review
• Predicting quantum advantage by quantum walk with convolutional neural networks
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Multilayer Network Science: from Cells to Societies
• Laplacian paths in complex networks: information core emerges from entropic transitions
• Complex Network Modelling with Power-law Activating Patterns and Its Evolutionary Dynamics
• Diffusive behavior of multiplex networks
• Complex networks with complex weights
• Extreme first passage times for random walks on networks
• Enhancing transport properties in interconnected systems without altering their structure
• Random walks on complex networks with first-passage resetting
• Universality of the stochastic block model
• Ranking influential nodes in networks from partial information
• Turing patterns on discrete topologies: from networks to higher-order structures
• From classical to quantum walks with stochastic resetting on networks
• Synwalk -- Community Detection via Random Walk Modelling
• Complex networks with tuneable dimensions as a universality playground
• Hopping in the crowd to unveil network topology
• Random walks on complex networks under node-dependent stochastic resetting
• Explicit and implicit network connectivity: Analytical formulation and application to transport processes
• Operationally Accessible Uncertainty Relations for Thermodynamically Consistent Semi-Markov Processes
• Blind identification of stochastic block models from dynamical observations
• Flow stability for dynamic community detection
• Search Optimization, Funnel Topography, and Dynamical Criticality on the String Landscape
• Source-independent quantum random number generator against tailored detector blinding attacks
• Diffusion geometry of multiplex and interdependent systems
• Random walks on complex networks under time-dependent stochastic resetting
• Exact results for the first-passage properties in a class of fractal networks
• Nonlocal biased random walks and fractional transport on directed networks
• Exact Blind Community Detection from Signals on Multiple Graphs
• Generalized network density matrices for analysis of multiscale functional diversity
• Spreading and Structural Balance on Signed Networks
• Broken detailed balance and entropy production in directed networks
• Machine learning transfer efficiencies for noisy quantum walks
• Mean encounter times for multiple random walkers on networks
• Link prediction with continuous-time classical and quantum walks
• Classical and quantum random-walk centrality measures in multilayer networks
• Energy landscape analysis based on the Ising model: Tutorial review
• A novel framework to analyze complex network dynamics
• Random walks with long-range steps generated by functions of Laplacian matrices
• Blind Inference of Eigenvector Centrality Rankings
• Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
• Higher-Order Networks Representation and Learning: A Survey
• Physical networks as network-of-networks
• Analysis of node2vec random walks on networks
• Random walks on complex networks with multiple resetting nodes: a renewal approach
• Aging in transport processes on networks with stochastic cumulative damage
• Reactive random walkers on complex networks
• Classes of critical avalanche dynamics in complex networks
• Random walks with stochastic resetting in complex networks: a discrete time approach
• A Lower Lower-Critical Spin-Glass Dimension from Quenched Mixed-Spatial-Dimensional Spin Glasses
• Relative, local and global dimension in complex networks
• The Dynamics of Knowledge Acquisition via Self-Learning in Complex Networks
• Activation thresholds in epidemic spreading with motile infectious agents on scale-free networks
• Random walk on temporal networks with lasting edges
• An integrative dynamical perspective for graph theory and the study of complex networks
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• From random walks on networks to nonlinear diffusion
• Network meta-analysis and random walks
• Generative models of simultaneously heavy-tailed distributions of inter-event times on nodes and edges
• Epidemic extinction in networks: Insights from the 12,110 smallest graphs
• Customer mobility and congestion in supermarkets
• Community detection based on first passage probabilities
• Inference from gated first-passage times
• Network Renormalization
• Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models
• Mathematical Modeling of Local Balance in Signed Networks and Its Applications to Global International Analysis
• Multilayer modeling of adoption dynamics in energy demand management
• Koopman-based spectral clustering of directed and time-evolving graphs
• Universal cover-time distribution of heterogeneous random walks
• Classes of random walks on temporal networks with competing timescales
• Random Walk with Memory on Complex Networks
• Thermodynamics of network model fitting with spectral entropies
• Opinion Dynamics with Multi-Body Interactions
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Random walks on networks with preferential cumulative damage: Generation of bias and aging
• State aggregations in Markov chains and block models of networks
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Entropy rate of random walks on complex networks under stochastic resetting
• Thermal Fracture Kinetics of Heterogeneous Semiflexible Polymers
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Geometric unfolding of synchronization dynamics on networks
• Evolution of transport under cumulative damage in metro systems
• Multi-hop assortativities for networks classification
• Deep learning based parameter search for an agent based social network model
• Multi-scale Laplacian community detection in heterogeneous networks
• Delocalization-localization dynamical phase transition of random walks on graphs
• Optimal exploration of random walks with local bias on networks
• The Impact of Global Structural Information in Graph Neural Networks Applications
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time
• Frustrated Random Walks: A Faster Algorithm to Evaluate Node Distances on Connected and Undirected Graphs
• The influence of a transport process on the epidemic threshold
• Generalized Markov stability of network communities
• Fractional dynamics on circulant multiplex networks: optimal coupling and long-range navigation for continuous-time random walks
• Spectral partitioning of time-varying networks with unobserved edges
• Prediction and Control of Focal Seizure Spread: Random Walk with Restart on Heterogeneous Brain Networks
• On Some General Operators of Hypergraphs
• Entrograms and coarse graining of dynamics on complex networks
• Emergent information dynamics in many-body interconnected systems
• Iterative embedding and reweighting of complex networks reveals community structure
• Structured networks and coarse-grained descriptions: a dynamical perspective
• Spectral properties, localization transition and multifractal eigenvectors of the Laplacian on heterogeneous networks
• Multiple structural transitions in interacting networks
• Laplacian Renormalization Group: An introduction to heterogeneous coarse-graining
• Reactive explorers to unravel network topology
• Centralities in complex networks
• Amplitude death and restoration in networks of oscillators with random-walk diffusion
• Random walk models for the propagation of signalling molecules in one-dimensional spatial networks and their continuum limit
• Efficient network exploration by means of resetting self-avoiding random walkers
• Impact of individual actions on the collective response of social systems
• Chaos in Nonlinear Random Walks with Non-Monotonic Transition Probabilities
• Quasi-periodic dynamics and a Neimark-Sacker bifurcation in nonlinear random walks on complex networks
• Epidemic dynamics on metapopulation networks with node2vec mobility
• Dynamics of senses of new physics discourse: co-keywords analysis
• Mean first-encounter times of simultaneous random walkers with resetting on networks
• Random Walks on Intersecting Geometries
• Eigenvector localization in hypergraphs: pair-wise vs higher-order links
• Hubs-biased resistance distances on graphs and networks
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Deterministic Random Walk Model in NetLogo and the Identification of Asymmetric Saturation Time in Random Graph
• Information retrieval and structural complexity of legal trees
• Unexpected advantages of exploitation for target searches in complex networks
• Photonic random walks with traps
• Antifragility of stochastic transport on networks with damage
• Graph sampling by lagged random walk
• Copula-based analysis of the autocorrelation function for simple temporal networks
• Relaxation of saturated random sequential adsorption packings of discorectangles aligned on a line
• Dynamics of micro and nanoscale systems in the weak-memory regime: A mathematical framework beyond the Markov approximation
• Perturbation theory for evolution of cooperation on networks
• On the dual nature of adoption processes in complex networks
• Metapopulation models imply non-Poissonian statistics of interevent times
• Antifragility and response to damage in the synchronization of oscillators on networks
• A measure of dissimilarity between diffusive processes on networks
• Network Meta-Analysis: A Statistical Physics Perspective
• Local topological moves determine global diffusion properties of hyperbolic higher-order networks
• Dynamical processes on metric networks
• Copula-based analysis of the generalized friendship paradox in clustered networks
• Maximally Random Discrete-Spin Systems with Symmetric and Asymmetric Interactions and Maximally Degenerate Ordering
• Indirect Influence on Network Diffusion
• Probing Black Hole Microstate Evolution with Networks and Random Walks
• Analytical approach to the generalized friendship paradox in networks with correlated attributes
• Cooperation and the social brain hypothesis in primate social networks
• Modeling advection on distance-weighted directed networks
• Diffusion and synchronization dynamics reveal the multi-scale patterns of spatial segregation
• Fast solver for diffusive transport times on dynamic intracellular networks
• Non-equilibrium random walks on multiplex networks
• Hierarchical route to the emergence of leader nodes in real-world networks
• Effects of topological structure and destination selection strategies on agent dynamics in complex networks
• Understanding random-walk dynamical phase coexistence through waiting times
• Multi-target search in bounded and heterogeneous environments: a lattice random walk perspective
• Meta-plasticity and memory in multi-level recurrent feed-forward networks
• An approximation for return time distributions of random walks on sparse networks
• Structural prediction of super-diffusion in multiplex networks
• Sampling nodes and hyperedges via random walks on large hypergraphs
• Averaging plus Learning Models and Their Asymptotics
• Thermodynamic Geometric Constraint on the Spectrum of Markov Rate Matrices
• Coarse-graining nonequilibrium diffusions with Markov chains
• Reaction-diffusion on random spatial networks with scale-free jumping rates via effective medium theory
• Spreader events and the limitations of projected networks for capturing dynamics on multipartite networks
• Renormalization group for spectral collapse in random matrices with power-law variance profiles
• Target-density formation in swarms with stochastic sensing and dynamics
• Path Counting on Tree-like Graphs with a Single Entropic Trap: Critical Behavior and Finite Size Effects
• Broken Detailed Balance and Non-Equilibrium Dynamics in Noisy Social Learning Models
• Density-dependent stochastic resetting: a large deviations framework for achieving target distributions over networks
• Prime stars multiplexes
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Multiscale methods for signal selection in single-cell data
• Random walks on bifractal networks
• Network growth under opportunistic attachment
• Markov chain approach to anomalous diffusion on Newman-Watts networks
• Random Walk of Bipartite Spins in a Classicalized Holographic Tensor Network
• "Spectrally gapped" random walks on networks: a Mean First Passage Time formula
• Consensus dynamics on temporal hypergraphs
• Statistics of the non-zero eigenvalues and singular values of low-rank random matrices with non-negative entries
• Optimization of multisite reactions in complex compartmentalized media
• Walk based Laplacians for Modeling Diffusion on Complex Networks