These animations shows the evolution of the decentralized
navigation algorithm (red) on a square 2-dimensional grid with
shortcuts, as described in Jon Kleinberg's paper "The Small-World
Phenomenon: An Algorithmic Perspective". In parallel, the green
path shows the shortest path that a centralized algorithm would
choose.
Scale-free shortcuts.
The shortcut exponent is set to 2 in this example, the unique value
for which efficient decentralized navigation is possible in this
model. This holds essentially because the navigation algorithm can
find useful shortcuts at every scale quite efficiently. The
centralized algorithm is performing slightly better because it "sees"
all the shortcuts in the network, not just those of visited nodes.
Shortcuts too local.
The shortcut exponent is set to 4 in this example, which means
that shortcuts tend to be very local w.r.t. the grid. The
decentralized routing algorithm can only make slow progress.
Shortcuts too global.
The shortcut exponent is set to 0 in this example, which means
that each shortcut goes to a node sampled uniformly at random from the set
of all nodes. The decentralized routing algorithm makes fast progress
first, but slows down when it approaches the destination, because no
"local shortcuts" can be found. Even though a short path exists, it cannot
be discovered by the local navigation algorithm.