  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.
