Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Greedy Routing and the Algorithmic Small-World Phenomenom


Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Lengler,  Johannes
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 1006KB

Supplementary Material (public)
There is no public supplementary material available

Bringmann, K., Keusch, R., Lengler, J., Maus, Y., & Molla, A. (2016). Greedy Routing and the Algorithmic Small-World Phenomenom. Retrieved from http://arxiv.org/abs/1612.05539.

Cite as: https://hdl.handle.net/11858/00-001M-0000-002C-5309-E
The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings that limit the applicability to real-world networks. In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study greedy routing in a more realistic random graph model (geometric inhomogeneous random graphs), which overcomes the previous shortcomings. Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks. In this model, we show that greedy routing succeeds with constant probability, and in case of success almost surely finds a path that is an almost shortest path. Our results are robust to changes in the model parameters and the routing objective. Moreover, since constant success probability is too low for technical applications, we study natural local patching methods augmenting greedy routing by backtracking and we show that such methods can ensure success probability 1 in a number of steps that is close to the shortest path length. These results also address the question of Krioukov et al. whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical answer, assuming our random graph model.