Greedy Routing and the Algorithmic Small-World Phenomenom

Understand

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 decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings.
• Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks.