hide
Free keywords:
cs.SI,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Networking and Internet Architecture, cs.NI,
Abstract:
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.
