opening it up with Common Lisp
Book review: Darwinia
Summer reading: Spin
the Omnivoire's Delimma
the Golem's Eye
the Small-world phenomenon: an algorithmic perspective
This paper has been on my reading list for the last several years and I finally got to it yesterday. When Kleinberg wrote it, everyone and their cousin had been gabbing on about the "Small World" phenomenon and "six degrees of separation". But it was Kleinberg who had the genius to realize that Milgrim's original experiment provided two insights:
Kleinberg then goes on to generalize the Watts-Strogatz ring model to grids of arbitrary dimension. This provides a more realistic notion of space (and therefore distance). In Kleinberg's model, each vertex is linked to all of its local neighbors (those within a distance of q) and then has q additional links added to more distant vertexes. The kicker is that the probability that a vertex u has a link added to a vertex v will be inversely proportional (to some power r) to the distant between u and v. Different values of r provide different distributions. For example, if r is 0, we'll get the uniform distribution (which is essentially the Watts-Strogatz model). Furthermore, the larger r becomes, the more centralized the links will be.
Kleinberg then goes on to show that navigation is only possible when r is equal to the dimension of the underlying grid. E.g., in a 2-dimensional world, navigation is only possible (in general) when r is 2. What's more, the navigation strategy is simple: at each step, choose the neighbor that is closest to the target. It's a gorgeous little paper: a beautiful result beautifully presented.
Copyright -- Gary Warren King, 2004 - 2006