title: Searching in small-world networks.
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 N(1/D(D+1)) 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.
authors.affiliation: Instituto de Fisica, Universidade de São Paulo, Caixa Postal 66318, 05315-970 São Paulo, São Paulo, Brazil. amoura@if.usp.br
authors.forename: Alessandro P S
authors.initials: AP
authors.lastname: de Moura
authors.forename: Adilson E
authors.initials: AE
authors.lastname: Motter
authors.forename: Celso
authors.initials: C
authors.lastname: Grebogi