Blind and myopic ants in heterogeneous networks

The diffusion processes on complex networks may be described by different Laplacian matrices due to heterogeneous connectivity. Here we investigate the random walks of blind ants and myopic ants on heterogeneous networks: While a myopic ant hops to a neighbor node every step, a blind ant may stay or hop with probabilities that depend on node connectivity. By analyzing the trajectories of blind ants, we show that the asymptotic behaviors of both random walks are related by rescaling time and probability with node connectivity. Using this result, we show how the small eigenvalues of the Laplacian matrices generating the two random walks are related. As an application, we show how the return-to-origin probability of a myopic ant can be used to compute the scaling behaviors of the Edwards-Wilkinson model, a representative model of load balancing on networks.

Figure 1

Comparison of the occupation probability $p_{ji}\left(t\right)$ of myopic ants (lines) and the predicted one ${\tilde{p}}_{ji}\left(t\right)=\frac{k_j}{\langle k\rangle }{Q}_{ji}\left(\frac{t}{\langle k\rangle }\right)$ (points) from that of blind ants $Q_{ji}\left(t\right)$ and Eq. (10) in scale-free networks. (a) The RTO probability $p_{ii}\left(t\right)$ of myopic ants and its prediction ${\tilde{p}}_{ii}\left(t\right)$ made from $Q_{ji}\left(t\right)$ of blind ants in a BA network with $m=1(\langle k\rangle =2)$ and $N=3000$. The spectral dimension is $d_s=4/3$. The node $i$ is the one selected randomly and has degree $k_i=137$. (b) The RTO probabilities $p_{ii}\left(t\right)$ and ${\tilde{p}}_{ii}\left(t\right)$ in the same BA networks as in (a) for a different node $i$ with $k_i=1$. (c) The occupation probability $p_{ij}\left(t\right)$ and the predicted one ${\tilde{p}}_{ij}\left(t\right)$ in the same BA network with two selected nodes $i$ and $j$ having degrees $k_i=137$ and $k_j=1$, respectively. (d) $p_{ii}\left(t\right)$ and ${\tilde{p}}_{ii}\left(t\right)$ in the same BA networks with two selected nodes having degrees $k_i=1$ and $k_j=13$, respectively. (e) The RTO probabilities $p_{ii}\left(t\right)$ and ${\tilde{p}}_{ii}\left(t\right)$ in a $(2,2)$ flower network in the seventh generation with $N=10924$ and $\langle k\rangle =3$. The spectral dimension is $d_s=2$ and the selected node $i$ has degree $k_i=16$. (f) The occupation probabilities $p_{ij}\left(t\right)$ and ${\tilde{p}}_{ij}\left(t\right)$ in the same $(2,2)$ flower network as in (e) for two selected nodes having degrees $k_i=16$ and $k_j=128$.

Figure 2

Plots of the relative deviation ${\eta }_{ji}\left(t\right)=\frac{{\tilde{p}}_{ji}\left(t\right)-p_{ji}\left(t\right)}{p_{ji}\left(t\right)}$ for each pair of selected nodes $i$ and $j$, (a) $i=j$ with $k_i=137$, (b) $i=j$ with $k_i=1$, (c) $k_i=137$ and $k_j=1$, and (d) $k_i=1$ and $k_j=13$ in the BA network and (e) $i=j$ with $k_i=16$ and (f) $k_i=1$ and $k_j=128$ in the $(2,2)$ flower networks as considered in Fig. 1. The lines are guide for the eye, which have slope $-1$.

Figure 3

The relative deviation $\frac{{\mu }_r-{\lambda }_r/\langle k\rangle }{{\mu }_r}$ of the eigenvalues ${\mu }_r$ and ${\lambda }_r$ of two Laplacian matrices $L$ and $\tilde{L}$ in Eq. (12). The eigenvalues are obtained numerically for the model networks having different spectral dimensions $d_s$ and the degree exponent $\gamma$: the $(2,2)$ flower networks in the seventh generation $\left(N=10924,\langle k\rangle =3,d_s=2,\gamma =3\right)$, the BA networks with $m=1$ ($N=16000,\langle k\rangle =2,d_s=4/3,\gamma =3$) and $m=2 \left(N=16000,\langle k\rangle =4,d_s\to \infty ,\gamma =3\right)$, and the Sierpinski gasket in the eighth generation ($N=9843,\langle k\rangle =4,d_s=2log3/log5,\gamma \to \infty$). The dashed line has slope 1.

Figure 4

(a, b) The load fluctuations ${\omega }_i{\left(\infty \right)}^2$ on the BA networks with $m=1$ and $m=2$ as a function of degree $k_i$. As shown in Eq. (20), it follows the power law with the predicted exponents 0 and $-1$, respectively. The cross and open circle symbols indicate the exact results using the Laplacian $L$ and the corresponding result using Eq. (10), respectively. Their relative deviation are shown in (c) for the BA network with $m=1$ and (d) with $m=2$. Even though the relative deviation seems to increase with $k_i$, it remains quite small in the entire range of $k_i$.