Exact Solution for Optimal Navigation with Total Cost Restriction

Abstract

Recently, Li \textit{et al.} have concentrated on Kleinberg's navigation model with a certain total length constraint $Λ= cN$, where $N$ is the number of total nodes and $c$ is a constant. Their simulation results for the 1- and 2-dimensional cases indicate that the optimal choice for adding extra long-range connections between any two sites seems to be $α=d+1$, where $d$ is the dimension of the lattice and $α$ is the power-law exponent. In this paper, we prove analytically that for the 1-dimensional large networks, the optimal power-law exponent is $α=2$ Further, we study the impact of the network size and provide exact solutions for time cost as a function of the power-law exponent $α$. We also show that our analytical results are in excellent agreement with simulations.

4 pages, 4 figures