Smart random walkers: The cost of knowing the path

In this work we study the problem of targeting signals in networks using entropy information measurements to quantify the cost of targeting. We introduce a penalization rule that imposes a restriction on the long paths and therefore focuses the signal to the target. By this scheme we go continuously from fully random walkers to walkers biased to the target. We found that the optimal degree of penalization is mainly determined by the topology of the network. By analyzing several examples, we have found that a small amount of penalization reduces considerably the typical walk length, and from this we conclude that a network can be efficiently navigated with restricted information.

Figure 1

Simple targeted walks in different network environments which can be solved analytically. Unique path (a), star web (b), and equivalent paths (c) (here $nf=1-p$).

Figure 2

Relative amount of intrinsic information $R_s$ vs $\gamma$ for the unique path [see Fig. 1a]. The curve reaches a minimum value ($R_s^{*}\simeq 0.7$) at ${\gamma }^{*}\simeq 2.5$ (indicated with a dot) which corresponds to the optimal degree of penalization. Inset: Optimal information $S_s^{*}$ (full line) and shortest path information $S_{sp}$ (horizontal red dotted line).

Figure 3

Information as function of the network's size $n$ in a linear-log plot, corresponding to the star web [see Fig. 1b]. Blue full line is the shortest path information $S_{sp}$, and the green dashed line is the optimal information $S_s^{*}$. Inset: The optimal penalization ${\gamma }^{*}$ (full black line). Relative amount of intrinsic information $R_s^{*}$ (red dashed line). Horizontal orange dotted line is the reference value for $R_s^{*}$ at $0.5$.

Figure 4

The optimal information $S_s^{*}$ as a function of system size $n$ (green dashed line), corresponding to the equivalent paths [see Fig. 1c]. This information is compared to the shortest path information $S_{sp}$ (blue full line). Both scale logarithmically with $n$ as indicated by the straight lines in the linear-log plot, and the difference $S_{sp}-S_s^{*}>0$ remains constant. Inset: The optimal penalization ${\gamma }^{*}$ (black full line) grows with $n$. The relative amount of intrinsic information dominates $R_s^{*}>0.5$ for all the sizes (red dashed line). The orange dotted line indicates $R_s^{*}=0.5$.

Figure 5

Each curve in this figure represents the ratio $D/\langle \overrightarrow{q^{*}}\rangle$ (see text) as a function of $\gamma$ for different targets $t$. One can see this ratio remains small in the whole range of $\gamma$ we explored. The largest value of the ratio is $\simeq$0.001 (orange dotted line). The calculations were performed on a random network with $n=10$ and $\langle k\rangle =3$.

Figure 6

In black full circles the relative amount of intrinsic information $R_{\gamma }$ associated with a randomly chosen vertex $t$ [Eq. (16)]. It shows the typical behavior with a minimum at ${\gamma }_t^{*}\simeq 1.105$. The other curves correspond to the relative amount of intrinsic information averaged over all the sources at a fixed distance $L=1,2,\cdots$ from $t$. Inset: The minimum of ${\langle R\rangle }_L$; ${\gamma }_L^{*}$, depends on $L$, but is the same order as ${\gamma }_t^{*}$ (red dotted line).

Figure 7

In black full circles the walk length $\langle wl\rangle$ averaged over different sources for a fixed target $t$ as a function of the penalization $\gamma$. The red dashed line indicates average shortest path length ${\langle L\rangle }_t$ to $t$. The vertical blue full line indicates the optimal value of the penalization ${\gamma }_t^{*}$. Inset: The magenta full circles correspond to the average walk length at optimality ${\langle w{l}^{*}\rangle }_L$ as a function of the distance to $t$. Cyan full squares represents the relative difference $({\langle w{l}^{*}\rangle }_L-L)/L$ and the orange dotted line indicates the value 2.

Figure 8

Walker's information $\langle S_s\rangle$ averaged over all the sources as function of the penalty $\gamma$ (black full circles). The horizontal red dashed line indicates the average shortest path information $\langle S_{sp}\rangle$. Vertical green full line indicates the optimal penalization ${\gamma }_t^{*}$. Inset: Average walker's information ${\langle S_s^{*}\rangle }_L$ at optimal penalty ${\gamma }_t^{*}$ as function of the distance $L$ (magenta full circles) and shortest path information ${\langle S_{sp}\rangle }_L$ (cyan full squares).

Figure 9

Average walk length $\langle w{l}^{*}\rangle$ at optimal penalization ${\gamma }_t^{*}$ (black full circles) and the average shortest path length $\langle L\rangle$ (red full squares) as a function of the target degree $k$. Both quantities decrease as the degree increases. Inset: Average walker's information $\langle S_s^{*}\rangle$ at optimal penalty ${\gamma }_t^{*}$ (magenta full circles) and the shortest path information $\langle S_{sp}\rangle$ (cyan full squares) as a function of the target degree.

Figure 10

Average relative amount of intrinsic information $\langle R^{*}\rangle$ (red full circles) and average of the overall optimal penalization $\langle {\gamma }_t^{*}\rangle$ as a function of the target degree $k$ (green full squares).

Figure 11

Comparison of different magnitudes of fat-tailed networks with degree distribution $P\left(k\right)\sim {(k_0+k)}^{-\alpha }$ (symbols connected with full lines) against the star web (horizontal dotted and dashed lines) as function of $\alpha$. Top: Optimal information $S^{*}(\mathrm{hub}\to t)$ (red circles and dotted line) and shortest path information $S_{sp}(\mathrm{hub}\to t)$ (blue squares and dashed line) averaged over the targets. Center: Optimal penalty ${\gamma }^{*}$ averaged over the targets. Bottom: Optimal intrinsic information $R_s^{*}$ averaged over the targets.