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, ${\tau }^{\mathrm{TSAW}}$, approaches the theoretical minimum ${\tau }^{\mathrm{th}}/N=\frac{1}{2}$ on synthetic networks whose degree-degree correlations are positive. On the other hand, for biased random walks (BRWs) we find that the MFPT, ${\tau }^{\mathrm{BRW}}$, depends on the parameter $\alpha$, which controls the degree-dependent bias. More importantly, we find that the minimum MFPT of BRWs, ${\tau }_{\min }^{\mathrm{BRW}}$, always satisfies the inequality ${\tau }_{\min }^{\mathrm{BRW}}>{\tau }^{\mathrm{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.

Figure 1

(a) Plot of $\tau$ vs $\alpha$ for BRWs on SF networks generated by CM with $N={10}^4,\gamma =2.5,r=0$, and $〈k〉=47$. (b) Plot of the obtained ${\alpha }_{\min }$ for various values of $r$ in three types of networks. $〈k〉=40$ for ER and BA networks and $〈k〉=46.5$ for the CM with $\gamma =2.5$. (c) Plot of ${\alpha }_{\min }$ of BRW vs $N$ for CM with $\gamma =2.5$ and $〈k〉=10$. (d) ${\tau }_{\min }^{\mathrm{BRW}}$ and ${\tau }^{\mathrm{TSAW}}$ vs $N$ on the CM with $r=0.1,\gamma =2.5$, and $〈k〉=10$. Solid and dashed lines in (d) represent the relation $\tau \sim N$.

Figure 2

Plots of ${\tau }_{\min }^{\mathrm{BRW}}/N$ of BRWs (open symbols) and ${\tau }^{\mathrm{TSAW}}/N$ of TSAWs (filled symbols) with (a) $〈k〉=40$ and (b) $〈k〉=10$. The solid line represents $\tau /N=1/2$, which is the theoretical minimum with $N={10}^4$.