Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks

Abstract

Numerous problems of both theoretical and practical interest are related to finding shortest (or otherwise optimal) paths in networks, frequently in the presence of some obstacles or constraints. A somewhat related class of problems focuses on finding optimal distributions of weights which, for a given connection topology, maximize some kind of flow or minimize a given cost function. We show that both sets of problems can be approached through an analysis of the large-deviation functions of random walks. Specifically, a study of ensembles of trajectories allows us to find optimal paths, or design optimal weighted networks, by means of an auxiliary stochastic process (the generalized Doob transform). In contrast to standard approaches, the paths are not limited to shortest paths and the weights must not necessarily optimize a given function. Paths and weights can in fact be tailored to a given statistics of a time-integrated observable, which may be an activity or current, or local functions marking the passing of the random walker through a given node or link. We illustrate this idea with an exploration of optimal paths in the presence of obstacles, and networks that optimize flows under constraints on local observables.

arXiv comment16 pages, 3 figures

References in corpus (44)

• The diameter of the world wide web
• The large deviation approach to statistical mechanics
• Random walks and diffusion on networks
• Efficient routing on complex networks
• First-order dynamical phase transition in models of glasses: an approach based on ensembles of histories
• Thermodynamic formalism for systems with Markov dynamics
• Direct evaluation of large-deviation functions
• Nonequilibrium Markov processes conditioned on large deviations
• Entanglement and alpha entropies for a massive Dirac field in two dimensions
• Improved routing strategies for Internet traffic delivery
• Synchronization is optimal in non-diagonalizable networks
• Large deviations and ensembles of trajectories in stochastic models
• Simulating rare events in dynamical processes
• Entropy Rate of Diffusion Processes on Complex Networks
• Localization of maximal entropy random walk
• Designing optimal transport networks
• Simple bounds on fluctuations and uncertainty relations for first-passage times of counting observables
• Construction of a Coordinate Bethe Ansatz for the asymmetric simple exclusion process with open boundaries
• Making rare events typical in Markovian open quantum systems
• Finite-Size Scaling of a First-Order Dynamical Phase Transition: Adaptive Population Dynamics and an Effective Model
• Epidemic extinction and control in heterogeneous networks
• Exact fluctuations of nonequilibrium steady states from approximate auxiliary dynamics
• Learning to grow: control of material self-assembly using evolutionary reinforcement learning
• Rare events and discontinuous percolation transitions
• Extreme events and event size fluctuations in biased random walks on networks
• Diffusions conditioned on occupation measures
• A reinforcement learning approach to rare trajectory sampling
• Adaptive sampling of large deviations
• Fluctuating observation time ensembles in the thermodynamics of trajectories
• Non-equilibrium steady states : maximization of the Shannon entropy associated to the distribution of dynamical trajectories in the presence of constraints
• Building continuous time crystals from rare events
• Vortices in the two-dimensional Simple Exclusion Process
• Large deviation theory of percolation on multiplex networks
• Large deviations of random walks on random graphs
• Epidemic Extinction Paths in Complex Networks
• Entanglement statistics in Markovian open quantum systems: a matter of mutation and selection
• Degree Dispersion Increases the Rate of Rare Events in Population Networks
• Large deviation induced phase switch in an inertial majority-vote model
• Condensation of degrees emerging through a first-order phase transition in classical random graphs
• Local structure of current fluctuations in diffusive systems beyond one dimension
• Experimental implementation of maximally synchronizable networks
• Random walks on weighted networks: Exploring local and non-local navigation strategies
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Random Walks on Complex Networks

Cited by in corpus (10)

• Large deviations in chaotic systems: exact results and dynamical phase transition
• Graph-combinatorial approach for large deviations of Markov chains
• 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
• 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
• Making rare events typical in $d$-dimensional chaotic maps