-
Notifications
You must be signed in to change notification settings - Fork 2
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.