Navigating in Small World Networks

Piere Fraigniaud and George Giakkoupis from the University of Paris at Diderot have a really nice paper in this upcoming PODC. Their paper titled "The Effect of Power-Law Degrees on the Navigability of Small Worlds" builds on the classic paper by Jon Kleinberg on navigating small world networks.

Jon Kleinberg's classic paper concerns navigation in a grid network where each node, in addition to its local edges, has one additional long range edge. What Kleinberg showed is that provided that, for each node, this long range link covers a distance d with probability proportional to d^2, then a greedy routing algorithm will ensure that any node can reach any other node in the network within no more than about log^2 n hops where n is the number of nodes in the network[1]. Moreover, the exponent in this probability is pretty important, even a slight deviation from an exponent of 2 results in networks that can not be efficiently navigated by greedy algorithms. In this way, Kleinberg was thus one of the first people to describe a type of network that might mimic the social network that allowed quick routing in Stanley Milgram's famous six degrees of separation experiments.

So what about this new paper by Piere and George? Well for many years the exponent of 2 in log^2 has bothered people. Piere and George show that it is possible to get rid of it with power laws. In particular, they show that if instead of each node having exactly 1 long distance link, the number of long distance links per node follows a certain powerlaw distribution, then greedy routing works in about log n hops. A powerlaw distribution means that the number of nodes with a number of long distance links x is proportional to x^k for some fixed constant k. This is a so called heavy tail distribution which occurs in many natural complex systems. Surprisingly, Piere and George show that the type of powerlaw distribution for which greedy routing works is when k is in the range between 2 and 3, which is very similar to the exponent one observes for degree distributions in many naturally occuring social networks.

As far as I know this is one of the first papers that suggests a nice functional property of powerlaw distributions. In particular, it shows that powerlaw distributions are more powerful than other distributions in achieving a specific mathematical goal. Are there other algorithmic or mathematical problems that powerlaw distributions are "good" for. It looks like a very nice paper.

[1] I'm using the term about to meet O(log^2 n) or roughly a function that grows like C log^2 n for some fixed constant C.

Bulwer-Lytton Fiction Contest Winner 2009

"She walked into my office on legs as long as one of those long-legged birds that you see in Florida - the pink ones, not the white ones - except that she was standing on both of them, not just one of them, like those birds, the pink ones, and she wasn't wearing pink, but I knew right away that she was trouble, which those birds usually aren't."

Raymond Chandler channels an ornithologist?