## Small-world networks

The Watts-Strogatz model of the small-world network have a large clustering coefficient and paths from node a to b that are on average short.

This means the typical number of steps between two randomly chosen nodes grows proportionally to the logarithm of the number of nodes in the network. The simplicity of this approach makes it a nice starting point for decentralized search.

"It is possible to prove that in the model of a d-dimensional lattice with uniformly random shortcuts, no decentralized algorithm can find short paths [...]. Exploring further, though, we find that a subtle variant of the Watts-Strogatz network will in fact support efficient search: Rather than adding the long-range shortcuts uniformly at random, we add links between nodes of this network with a probability that decays like the dth power of their distance (in d dimensions)." Jon Kleinberg — The Small-World Phenomenon and Decentralized Search

Pelechrinis explores the uniformity of distribution in Kleinberg's model. But geography doesn't correlate with the location of data, so Kleinberg's model seems complete as it is.