Small world routing

Greedy routing

Nearly every solution to the problem of routing in small world involves the application of greedy routing. This sort of routing depends on a relative reference point by which any node in the path can choose the next node it believes is closest to the destination. That is, there must be something to be greedy about. For example, this could be geographic location, IP address, etc. In the case of Milgram's original small-world experiment, participants knew the location and occupation of the final recipient and could therefore forward messages based on those parameters.

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 v to another random vertex w is proportional to 1 / d ( v , w ) q , where q is the clustering coefficient.

Greedy routing in the Kleinberg model

It is easy to see that a greedy algorithm, without using the long range edges, can navigate from random vertices v->w on the grid in O ( n ) time. By following the guaranteed connections to our neighbors, we can move one unit at a time in the direction of our destination. This is also the case when the clustering component q large and the “long range” edges end up staying very close; we simply do not take advantage of the weaker ties in this model. When q = 0 , the long range edges are uniformly connected at random which means the long range edges are “too random” to be used efficiently for decentralized search. Kleinberg has shown that the optimal clustering coefficient for this model is q = 2 , or an inverse square distribution.

To reason why this is the case, if a circle of radius r is drawn around the initial node it will have nodal density n / ( p i ∗ r 2 ) where n is the number of nodes in the circular area. As this circle gets expanded further out, the number of nodes in the given area increases proportional to r 2 as the probability of having a random link with any node remains proportional 1 / r 2 , meaning the probability of the original node having a weak tie with any node a given distance away is effectively independent of distance. Therefore, it is concluded that with q = 2 , long-range edges are evenly distributed over all distances, which is effective for letting us funnel to our final destination.