de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Greedy Routing and the Algorithmic Small-World Phenomenom

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44182

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44908

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1612.05539.pdf
(Preprint), 1006KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-002C-5309-E
Zusammenfassung
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.