Optimal Navigation in Complex Networks

Recent literature has presented evidence that the study of navigation in complex networks is useful to understand their dynamics and topology. Two main approaches are usually considered: navigation of random walkers and navigation of directed walkers. Unlike these approaches ours supposes that a traveler walks optimally in order to minimize the cost of the walking. If this happens, two extreme regimes arise-one dominated by directed walkers and the other by random walkers. We try to characterize the critical point of the transition from one regime to the other in function of the connectivity and the size of the network. Furthermore, we show that this approach can be used to generalize several concepts presented in the literature concerning random navigation and direct navigation. Finally, we defend that investigating the extreme regimes dominated by random walkers and directed walkers is not sufficient to correctly assess the characteristics of navigation in complex networks.