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 class of 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.

Original languageEnglish (US)
Article number190
JournalNew Journal of Physics
StatePublished - Jun 28 2007

All Science Journal Classification (ASJC) codes

  • General Physics and Astronomy

Cite this