Path finding strategies in scale-free networks

We numerically investigate the scale-free network model by Barab{\'a}si and Albert [Science {\bf 286}, 509 (1999)] through the use of various path finding strategies. In real networks, the global network information is not accessible to each vertex, and the actual path connecting two vertices can sometimes be much longer than the shortest one. A generalized diameter depending on the actual path finding strategy is introduced, and a simple strategy, which utilizes only the local information on the connectivity, is suggested and shown to yield the small-world behavior: the diameter $D$ of the network increases logarithmically with the network size $N$, the same as found with the global strategy. If paths are sought at random, $D \sim N^{0.5}$ is found.