opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp


Planet Lisp



Talking Points Memo

This Modern World

Working for Change

Other home


Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006


the Small-world phenomenon: an algorithmic perspective
Jon Kleinberg, 2000 , (Paper URL)
Thursday, November 3, 2005

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:

  • That short chains of acquaintances seem to connect us all and
  • That people are able to navigate along those chains!

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.

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006