Greedy routing and the algorithmic small-world phenomenon
METADATA ONLY
Loading...
Author / Producer
Date
2022-05
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
The algorithmic small-world phenomenon, empirically established by Milgram in the 60 s [1], was theoretically explained by Kleinberg in 2000 [2]. 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, we study decentralized greedy routing in a random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings. We prove that greedy routing succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length Θ(loglogn), with stretch 1+o(1). Moreover, natural local patching methods ensure success probability 1, while maintaining the same stretch. These results also address the question whether there are efficient local routing protocols for the internet graph. Despite promising experimental studies the question remained unsolved theoretically. We give for the first time a rigorous, affirmative answer for a thoroughly validated model of the internet graph. © 2021 Elsevier Inc.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
125
Pages / Article No.
59 - 105
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Small-world phenomenon; Greedy routing; Real-world networks; Routing protocols; Internet routing; Random graph models
Organisational unit
03672 - Steger, Angelika / Steger, Angelika