Biased random walks on Kleinberg’s spatial networks

• This paper studies random walk with a bias in spatial network.
• This paper finds that the best optimal transport is related with the bias.
• This paper finds a highly efficient structure for navigation.

We investigate the problem of the particle or message that travels as a biased random walk toward a target node in Kleinberg’s spatial network which is built from a dd-dimensional (d=2d=2) regular lattice improved by adding long-range shortcuts with probability P(rij)∼rij−α, where rijrij is the lattice distance between sites ii and jj, and αα is a variable exponent. Bias is represented as a probability pp of the packet to travel at every hop toward the node which has the smallest Manhattan distance to the target node. We study the mean first passage time (MFPT) for different exponent αα and the scaling of the MFPT with the size of the network LL. We find that there exists a threshold probability pth≈0.5pth≈0.5, for p≥pthp≥pth the optimal transportation condition is obtained with an optimal transport exponent αop=dαop=d, while for 0pthp>pth, and increases with LL less than a power law and get close to logarithmical law for 0