Multiple Random Walks to Uncover Short Paths in Power Law Networks
Developing simple distributed algorithms to allow nodes to perform topology discovery and message routing using incomplete topological information is a problem of great interest in network science. Consider the following routing problem in the context of a large power law network G. A small number of nodes want to exchange messages over short paths on G. These nodes do not have access to the topology of G but are allowed to crawl the network subject to a budget constraint. Only crawlers whose paths cross are allowed to exchange topological information. In this paper, the authors study the use of Random Walks (RWs) to crawl G.