Abstract
We study the mean first passage time (MFPT) of true self-avoiding walks (TSAWs) on various networks as a measure of searching efficiency. From the numerical analysis, we find that the MFPT of TSAWs, , approaches the theoretical minimum on synthetic networks whose degree-degree correlations are positive. On the other hand, for biased random walks (BRWs) we find that the MFPT, , depends on the parameter , which controls the degree-dependent bias. More importantly, we find that the minimum MFPT of BRWs, , always satisfies the inequality on any synthetic network. The inequality is also satisfied on various real networks. From these results, we show that the TSAW is one of the most efficient models, whose efficiency approaches the theoretical limit in network explorations.
- Received 27 February 2016
DOI:https://doi.org/10.1103/PhysRevE.94.042309
©2016 American Physical Society