Mean first-passage time for maximal-entropy random walks in complex networks
arXiv:1406.3680 · doi:10.1038/srep05365
Abstract
We perform an in-depth study for mean first-passage time (MFPT)---a primary quantity for random walks with numerous applications---of maximal-entropy random walks (MERW) performed in complex networks. For MERW in a general network, we derive an explicit expression of MFPT in terms of the eigenvalues and eigenvectors of the adjacency matrix associated with the network. For MERW in uncorrelated networks, we also provide a theoretical formula of MFPT at the mean-field level, based on which we further evaluate the dominant scalings of MFPT to different targets for MERW in uncorrelated scale-free networks, and compare the results with those corresponding to traditional unbiased random walks (TURW). We show that the MFPT to a hub node is much lower for MERW than for TURW. However, when the destination is a node with the least degree or a uniformly chosen node, the MFPT is higher for MERW than for TURW. Since MFPT to a uniformly chosen node measures real efficiency of search in networks, our work provides insight into general searching process in complex networks.
Definitive version accepted for publication in Scientific Reports
References in corpus (11)
- Critical phenomena in complex networks
- First-passage times in complex scale-invariant media
- Entropy Rate of Diffusion Processes on Complex Networks
- Exact mean first-passage time on the T-graph
- Maximal-entropy random walks in complex networks with limited information
- Exact solution for mean first-passage time on a pseudofractal scale-free web
- Random walks on weighted networks
- Langevin approach for the dynamics of the contact process on annealed scale-free networks
- Trapping in complex networks
- Maximal entropy random walk in community finding
- Maximal Entropy Random Walk: solvable cases of dynamics