Optimal exploration of random walks with local bias on networks
arXiv:2112.09033 · doi:10.1103/PhysRevE.105.044318
Abstract
We propose local-biased random walks on general networks where a Markovian walker can choose between different types of biases in each node to define transitions to its neighbors depending on their degrees. For this ergodic dynamics, we explore the capacity of the random walker to visit all the nodes characterized by a global mean first passage time. This quantity is calculated using eigenvalues and eigenvectors of the transition matrix that defines the dynamics. In the first part, we illustrate how our framework leads to optimal transport for small-size graphs through the analysis of all the possible bias configurations. In the second part, we explore optimal bias in each node by using simulated annealing. This heuristic algorithm allows obtaining approximate solutions of the optimal bias in different types of networks. The results show how the local bias can optimize the exploration of the network in comparison with the unbiased random walk. The methods implemented in this research are general and open the doors to a broad spectrum of tools applicable to different random walk strategies and dynamical processes on networks.
arXiv comment10 pages, 6 figures
References in corpus (21)
- Emergence of scaling in random networks
- Cooperative Game Theory Approaches for Network Partitioning
- Random walks and diffusion on networks
- Quantum Simulations of Classical Annealing Processes
- Biased random walks on complex networks: the role of local navigation rules
- Google matrix analysis of directed networks
- Exploring complex networks by walking on them
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Long-Range Navigation on Complex Networks using Lévy Random Walks
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Flow graphs: interweaving dynamics and structure
- Cover time for random walks on arbitrary complex networks
- Efficient exploration of multiplex networks
- Extreme events and event size fluctuations in biased random walks on networks
- Epidemic spreading driven by biased random walks
- A markovian random walk model of epidemic spreading
- Nonlocal biased random walks and fractional transport on directed networks
- Mean encounter times for multiple random walkers on networks
- Aging in transport processes on networks with stochastic cumulative damage
- Diffusion-annihilation proecesses in weighted scale-free networks with identical degree sequence
- Random walks on networks with preferential cumulative damage: Generation of bias and aging