Small World Routing - The Kleinberg Model

The Kleinberg Model

The Kleinberg model of a network is effective at demonstrating the effectiveness of greedy small world routing. The model uses an n x n grid of nodes to represent a network, where each node is connected with an undirected edge to its neighbors. To give it the “small world” effect, a number of long range edges are added to the network that tend to favor nodes closer in distance rather than farther. When adding edges, the probability of connecting some random vertex to another random vertex w is proportional to, where is the clustering coefficient.