6 - Navigation in random networks

Summary

In this chapter we shift our attention from the existence of certain structures in random networks, to the ability of finding such structures. More precisely, we consider the problem of navigating towards a destination, using only local knowledge of the network at each node. This question has practical relevance in a number of different settings, ranging from decentralised routing in communication networks, to information retrieval in large databases, file sharing in peer-to-peer networks, and the modelling of the interaction of people in society.

The basic consideration is that there is a fundamental difference between the existence of network paths, and their algorithmic discovery. It is quite possible, for example, that paths of a certain length exist, but that they are extremely difficult, or even impossible to find without global knowledge of the network topology. It turns out that the structure of the random network plays an important role here, as there are some classes of random graphs that facilitate the algorithmic discovery of paths, while for some other classes this becomes very difficult.

Highway discovery

To illustrate the general motivation for the topics treated in this chapter, let us start with some practical considerations. We turn back to the routing protocol described in Chapter 5 to achieve the optimal scaling of the information flow in a random network. Recall from Section 5.3 that the protocol is based on a multi-hop strategy along percolation paths that arise w.h.p. inside rectangles of size m × κ log m that partition the entire network area.