Greedy routing in small-world networks with power-law degrees

Pierre Fraigniaud 1, 2 George Giakkoupis 3
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg's grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter α ≥ 0 and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent α for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when 2 < α < 3 the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of O(log^(α−1) n · log log n) steps, for any source–target pair. This is asymptotically smaller than the O(log^2 n) steps needed in Kleinberg's original model with the same average degree, and approaches O(log n) as α approaches 2. Further, we show that when 0 ≤ α < 2 or α ≥ 3 the expected number of steps is O(log^2 n), while for α = 2 it is O(log^(4/3) n). We complement these results with lower bounds that match the upper bounds within at most a log log n factor.
Type de document :
Article dans une revue
Distributed Computing, Springer Verlag, 2014, 27 (4), pp.231 - 253. 〈10.1007/s00446-014-0210-y〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger
Contributeur : George Giakkoupis <>
Soumis le : vendredi 19 décembre 2014 - 00:32:10
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:31:05


Fichiers produits par l'(les) auteur(s)



Pierre Fraigniaud, George Giakkoupis. Greedy routing in small-world networks with power-law degrees. Distributed Computing, Springer Verlag, 2014, 27 (4), pp.231 - 253. 〈10.1007/s00446-014-0210-y〉. 〈hal-01097141〉



Consultations de la notice


Téléchargements de fichiers