Biased random walks in complex networks: The role of local navigation rules

We study the biased random-walk process in random uncorrelated networks with arbitrary degree distributions. In our model, the bias is defined by the preferential transition probability, which, in recent years, has been commonly used to study the efficiency of different routing protocols in communication networks. We derive exact expressions for the stationary occupation probability and for the mean transit time between two nodes. The effect of the cyclic search on transit times is also explored. Results presented in this paper provide the basis for a theoretical treatment of transport-related problems in complex networks, including quantitative estimation of the critical value of the packet generation rate.

Figure 1

Stationary probability distributions $P_j^{\infty }\left(k\right)$ calculated for different values of the parameter $\alpha$ in classical random graphs and scale-free networks. Solid lines correspond to the theoretical prediction of Eq. (8). In the case of classical random graphs, $⟨k⟩=5$ was assumed. In scale-free networks $\gamma =3$ and $⟨k⟩=6$ were chosen.

Figure 2

Mean first return time $T_{ii}$ vs node degree $k_i$ (main panels), and $⟨T_{ii}⟩$ vs $\alpha$ (insets) in classical random graphs $\left(⟨k⟩=5\right)$ and scale-free networks ($\gamma =3$, $⟨k⟩=6$).

Figure 3

First return time $T_{ii}$ vs node degree $k_i$ for different values of the particle’s wandering time $t$ in scale-free networks ($\gamma =3$, $⟨k⟩=6$, $\alpha =1$). Increasing the simulation time $t$ improves agreement with the theoretical line given by Eq. (15).

Figure 4

Mean transit time $T_{ij}$ between two nodes $i$ and $j$ vs connectivity of the target node $k_j$ in classical random graphs $\left(⟨k⟩=5\right)$ and scale-free networks ($\gamma =3$, $⟨k⟩=6$).

Figure 5

Mean transit time $T_{ij}\left(x\right)$ for the cyclic search problem in classical random graphs with $⟨k⟩=5$. The solid lines have the slop predicted by Eq. (19), i.e., $T_{ij}\left(x\right)\propto k_j^{-1}$.