Exact solution for optimal navigation with total cost restriction
Department of Systems Science, School of Management, Beijing Normal University - Beijing 100875, PRC
Accepted: 21 November 2010
Recently, Li 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 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.
PACS: 89.75.Hc – Networks and genealogical trees / 89.75.Fb – Structures and organization in complex systems
© EPLA, 2010