The first theoretical navigation model was proposed by Kleinberg[1]}, [2]}. He introduced an \(n \times n \)  lattice to model social networks. In addition to the links between nearest neighbors, each node \(u\)  is connected to a random node \(v\)  with a probability proportional to \(d(u,v)^{-r}\) , where \(d(u,v)\)  denotes the lattice distance between \(u\)  and \(v\) .
Kleinberg has proved that the optimal navigation can be obtained when the power-law exponent \(r\)  equals to \(d\) , where \(d\)  is the dimensionality
of the lattice, and the time complexity of navigation in that case is at most \(O(\log ^2 n)\) . Since then, much attention has been dedicated to Kleinberg's navigation model[3]}, [4]}, [5]}. Roberson et al. studied the navigation problem in fractal networks, where they proved that \(r=d\)  was also the optimal power-law exponent in the fractal case[6]}. Carmi, Cartozo and their cooperators have provided exact solutions respectively for the asymptotic behavior of Kleinberg's navigation model[7]}, [8]}. More recently, the navigation probolem with a total cost restriction has also been discussed, where the cost denotes the length of the long-range connections[9]}, [10]}.
