Abstract. We study the decentralized search problem in a family of parameterized spatial network models that are heterogeneous in node degree. We investigate several algorithms and illustrate that some of these algorithms exploit the heterogeneity in the network to find short paths by using only local information. In addition, we demonstrate that the spatial network model belongs to a classof searchable networks for a wide range of parameter space. Further, we test these algorithms on the US airline network which belongs to this class of networks and demonstrate that searchability is a generic property of the US airline network. These results provide insights on designing the structure of distributed networks that need effective decentralized search algorithms.

Received 12 March 2007
Published 28 June 2007