Network exploration using true self-avoiding walks

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, τTSAW, approaches the theoretical minimum τth/N=12 on synthetic networks whose degree-degree correlations are positive. On the other hand, for biased random walks (BRWs) we find that the MFPT, τBRW, depends on the parameter α, which controls the degree-dependent bias. More importantly, we find that the minimum MFPT of BRWs, τminBRW, always satisfies the inequality τminBRW>τTSAW 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.