Kleinberg navigation on anisotropic lattices

Abstract

We study the Kleinberg problem of navigation in Small World networks when the underlying lattice is stretched along a preferred direction. Extensive simulations confirm that maximally efficient navigation is attained when the length $r$ of long-range links is taken from the distribution $P(\mathbf{r})\sim r^{-\alpha }$, when the exponent $\alpha$ is equal to 2, the dimension of the underlying lattice, regardless of the amount of anisotropy, but only in the limit of infinite lattice size, $L\to \infty$. For finite size lattices we find an optimal $\alpha (L)$ that depends strongly on $L$. The convergence to $\alpha =2$ as $L\to \infty$ shows interesting power-law dependence on the anisotropy strength.

6 pages, 4 figures, data included with source