Searching in small-world networks

Alessandro P.S. de Moura*, Adilson E. Motter, Celso Grebogi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We study the average time it takes to find a desired node in the Watts-Strogatz family of networks. We consider the case when the look-up time can be neglected and when it is important, where the look-up time is the time needed to choose one among all the neighboring nodes of a node at each step in the search. We show that in both cases, the search time is minimum in the small-world regime, when an appropriate distance between the nodes is defined. Through an analytical model, we show that the search time scales as [Formula presented] for small-world networks, where N is the number of nodes and D is the dimension of the underlying lattice. This model is shown to be in agreement with numerical simulations.

Original languageEnglish (US)
Number of pages1
JournalPhysical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
Volume68
Issue number3
DOIs
StatePublished - Jan 1 2003

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics
  • Condensed Matter Physics
  • Physics and Astronomy(all)

Fingerprint Dive into the research topics of 'Searching in small-world networks'. Together they form a unique fingerprint.

Cite this