Random Walk with Memory on Complex Networks
arXiv:1907.08222 · doi:10.1103/PhysRevE.102.042315
Abstract
We study random walk on complex networks with transition probabilities which depend on the current and previously visited nodes. By using an absorbing Markov chain we derive an exact expression for the mean first passage time between pairs of nodes, for a random walk with a memory of one step. We have analyzed one particular model of random walk, where the transition probabilities depend on the number of paths to the second neighbors. The numerical experiments on paradigmatic complex networks verify the validity of the theoretical expressions, and also indicate that the flattening of the stationary occupation probability accompanies a nearly optimal random search.
References in corpus (15)
- Emergence of scaling in random networks
- Maps of random walks on complex networks reveal community structure
- Synchronization in complex networks
- The spread of epidemic disease on networks
- Random walks and diffusion on networks
- Navigability of Complex Networks
- Localization of maximal entropy random walk
- Global mean first-passage times of random walks on complex networks
- Biased random walks on complex networks: the role of local navigation rules
- Quantifying patterns of research interest evolution
- A spectrum of routing strategies for brain networks
- Long-Range Navigation on Complex Networks using Lévy Random Walks
- Characteristic times of biased random walks on complex networks
- Search in Complex Networks : a New Method of Naming
- Random Walks on Complex Networks