Large deviations of random walks on random graphs

Abstract

We study using large deviation theory the fluctuations of time-integrated functionals or observables of the unbiased random walk evolving on Erdös-Rényi random graphs, and construct a modified, biased random walk that explains how these fluctuations arise in the long-time limit. Two observables are considered: the sum of the degrees visited by the random walk and the sum of their logarithm, related to the trajectory entropy. The modified random walk is used for both quantities to explain how sudden changes in degree fluctuations, akin to dynamical phase transitions, are related to localization transitions. For the second quantity, we also establish links between the large deviations of the trajectory entropy and the maximum entropy random walk.

arXiv commentv1: 12 pages, 8 figures. v2: minor typos corrected. v3: minor typos, close to published version

References in corpus (35)

• Epidemic processes in complex networks
• The large deviation approach to statistical mechanics
• Entropy production along a stochastic trajectory and an integral fluctuation theorem
• Direct evaluation of large-deviation functions
• Nonequilibrium Markov processes conditioned on large deviations
• Large deviations and ensembles of trajectories in stochastic models
• Nonequilibrium microcanonical and canonical ensembles and their equivalence
• Entropy Rate of Diffusion Processes on Complex Networks
• Localization of maximal entropy random walk
• A numerical approach to large deviations in continuous-time
• Variational and optimal control representations of conditioned and driven processes
• Maximal-entropy random walks in complex networks with limited information
• Disease extinction in the presence of non-Gaussian noise
• Population dynamics method with a multi-canonical feedback control
• Current large deviations for driven periodic diffusions
• Extreme events on complex networks
• Finite-Size Scaling of a First-Order Dynamical Phase Transition: Adaptive Population Dynamics and an Effective Model
• Epidemic extinction and control in heterogeneous networks
• Cover time for random walks on arbitrary complex networks
• Rare events and discontinuous percolation transitions
• Large deviations of cascade processes on graphs
• Extreme events and event size fluctuations in biased random walks on networks
• Fluctuations in percolation of sparse complex networks
• Diffusions conditioned on occupation measures
• Adaptive sampling of large deviations
• Controlling the uncertain response of real multiplex networks to random damage
• Convergence of large deviation estimators
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Large deviations in the presence of cooperativity and slow dynamics
• Epidemic Extinction Paths in Complex Networks
• Rare Event Extinction on Stochastic Networks
• Manipulation of extreme events on scale-free networks
• Large order fluctuations, switching, and control in complex networks
• Paths counting on simple graphs: from escape to localization
• Rare events in networks with internal and external noise

Cited by in corpus (17)

• Dynamical phase transition in drifted Brownian motion
• Large deviations in chaotic systems: exact results and dynamical phase transition
• Counterexample: scale-free networked graphs with invariable diameter and density feature
• Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
• Graph-combinatorial approach for large deviations of Markov chains
• Varied phenomenology of models displaying dynamical large-deviation singularities
• Dynamical phase transition to localized states in the two-dimensional random walk conditioned on partial currents
• Delocalization-localization dynamical phase transition of random walks on graphs
• Finding the effective dynamics to make rare events typical in chaotic maps
• Dynamical fluctuations of random walks in higher-order networks
• Adaptive power method for estimating large deviations in Markov chains
• Maximal dispersion of adaptive random walks
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Understanding random-walk dynamical phase coexistence through waiting times
• Large-deviations approach to thermalization: the case of harmonic chains with conservative noise
• Non-equilibrium random walks on multiplex networks
• Dimensionality-induced dynamical phase transition in the large deviation of local time density for Brownian motion