Skip to content

Kleinberg Network

Stephen Oliver edited this page Mar 30, 2017 · 1 revision

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.

See also

Clone this wiki locally
You can’t perform that action at this time.