A Kleinberg network is a general model for a small world network.

A Kleinberg network is built from a lattice connected graph in d dimensions, that is, nodes are laid out on a d-dimensional Cartesian grid, with each node connected to all neighbors within lattice distance p.

An additional q long-range connections are added, such that the probability of a connection from u to v is proportional to distance(u,v)^(-1 * a), where a is a fixed constant.

Kleinberg shows that such networks are routable in O(log(n)^2) time if a = d.

• Jon Kleinberg's page

• Navigation in a Small World, J. Kleinberg

• The small-world phenomenon: An algorithmic perspective, J. Kleinberg