Exact Solution for Optimal Navigation with Total Cost Restriction

Recently, Li $\mathit{\text{et}}\mathit{\text{al.}}$ have concentrated on Kleinberg’s navigation model with a certain total length constraint $\mathrm{\Lambda }=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 $\alpha =d+1$, where $d$ is the dimension of the lattice and $\alpha$ is the power-law exponent. In this paper, we prove analytically that for the 1-dimensional large networks, the optimal power-law exponent is $\alpha =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 $\alpha$. We also show that our analytical results are in excellent agreement with simulations.