Maximal dispersion of adaptive random walks
arXiv:2202.13923 · doi:10.1103/PhysRevResearch.4.L042051
Abstract
Maximum entropy random walks (MERWs) are maximally dispersing and play a key role in optimizing information spreading in various contexts. However, building MERWs comes at the cost of knowing beforehand the global structure of the network, a requirement that makes them totally inadequate in real case scenarios. Here, we propose an adaptive random walk (ARW), which instead maximizes dispersion by updating its transition rule on the local information collected while exploring the network. We show how to derive ARW via a large-deviation representation of MERW and study its dynamics on synthetic and real world networks.
arXiv comment20 pages, 12 figures, 1 table
References in corpus (34)
- Statistical mechanics of complex networks
- Temporal Networks
- The large deviation approach to statistical mechanics
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Entropy production along a stochastic trajectory and an integral fluctuation theorem
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- Nonequilibrium Markov processes conditioned on large deviations
- Nonequilibrium microcanonical and canonical ensembles and their equivalence
- Entropy Rate of Diffusion Processes on Complex Networks
- Localization of maximal entropy random walk
- Network reconstruction and community detection from dynamics
- Variational and optimal control representations of conditioned and driven processes
- Maximal-entropy random walks in complex networks with limited information
- Extreme events on complex networks
- Epidemic extinction and control in heterogeneous networks
- Centrality measures and thermodynamic formalism for complex networks
- Efficient exploration of multiplex networks
- Rare events and discontinuous percolation transitions
- Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity
- Link prediction based on path entropy
- Extreme events and event size fluctuations in biased random walks on networks
- Adaptive sampling of large deviations
- Controlling the uncertain response of real multiplex networks to random damage
- Mean first-passage time for maximal-entropy random walks in complex networks
- Maximal entropy random walk in community finding
- Large deviations of random walks on random graphs
- Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
- Extreme events in stochastic transport on networks
- Rare-Event Properties of the Nagel-Schreckenberg Model
- Maximal-entropy random walk unifies centrality measures
- Large order fluctuations, switching, and control in complex networks
- Biased random walkers and extreme events on the edges of complex networks
- Reactive explorers to unravel network topology
- Random Walks on Complex Networks