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.
20 pages, 12 figures, 1 table
References in corpus (11)
- The large deviation approach to statistical mechanics
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- Entropy Rate of Diffusion Processes on Complex Networks
- Maximal-entropy random walks in complex networks with limited information
- Extreme events on complex networks
- Mean first-passage time for maximal-entropy random walks in complex networks
- Maximal entropy random walk in community finding
- Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
- Large order fluctuations, switching, and control in complex networks
- Biased random walkers and extreme events on the edges of complex networks
- Random Walks on Complex Networks