The solution to the “six degrees” problem

Many people have heard of the famous “six degrees” experiment, in which psychologist Stanley Milgram asked individuals in Boston and Omaha, Neb., were asked to deliver a letter to a target stranger in Boston, using only a chain of acquaintances: You’d pass the letter to someone who might be closer to the target, and they’d pass it on, and so on. Milgram discovered that on average, it took roughly six links to get the letters to their destination.

A cool finding, indeed. But got network scientists wondering: Is there an algorithm that could scan a network and automatically deduce the fastest possible route for a message? If you had, like, 4,000 nodes all loosely and chaotically joined, could one algorithm grok the speediest way to get from any point A to any other point B?

It sounds pretty abstract, but this science has a lot of practical applications. Wifi “mesh” networks, for example — which I wrote about last month — could work much more quickly and efficiently if the mesh “knew” the fastest route for a message to travel. And it might be possible to stop computer viruses and worms in their tracks if one could automatically intuit the fastest route between computers online. So for years, scientists have developed various solutions that map out networks, with varying degrees of success.

Now two researchers at the University of Amherst have published what appears to be the best algorithm yet — and it’s based on human psychology. As they note, our connections in society aren’t random; we tend to know people based on shared charcteristics: Dentists know other dentists, Upper East Siders in Manhattan know other Upper East Siders, sixth graders know sixth graders. And then they point out the observation that Malcolm Gladwell made famous in The Tipping Point: That certain rare people seem to have a lot more connections than other people — “superconnectors”, as Gladwell calls them. So, as a press release on the research notes …

This “degree disparity” leads to some individuals acting as hubs.

Taking these factors into account simultaneously results in a searching algorithm that gets messages to the target by passing it to gregarious individuals who are most like the target.

They called their new algorithm “expected-value navigation”, or EVN. When they tested it against several pre-existing, popular algorithms, it worked better — producing shorter, more efficient pathways. (It’s the top one in the chart above, which is taken from their PDF paper on the subject.)

Here’s the interesting thing, though. Ever since Gladwell’s book, people have assumed that “superconnectors” are crucial to the transmission of messages and information through society. As Gladwell argued, if it weren’t for those ultrapopular, massively gregarious people, memes wouldn’t spread as quickly through mass culture; indeed, hunting down and targetting the ultracool, early-adopting superconnectors of the teen-and-youth world has been the holy grail of marketers for years now. And this study would seem to affirm that superconnectors are the glue that holds social networks together.

But other research suggests they really aren’t so crucial. Duncan Watts, another famous network researcher, has spent years replicating the “six degrees” study by using email — which allows him to carefully study the role of each node in message propagation. His conclusion? Superconnectors may well exist — but they don’t matter. Messages travel through society in a surprisingly democratic fashion, relying most often on “weak” and “intermediate” nodes instead of superconnected ones.

Curious, eh?

(Thanks to for this one!)

blog comments powered by Disqus

Search This Site


I'm Clive Thompson, the author of Smarter Than You Think: How Technology is Changing Our Minds for the Better (Penguin Press). You can order the book now at Amazon, Barnes and Noble, Powells, Indiebound, or through your local bookstore! I'm also a contributing writer for the New York Times Magazine and a columnist for Wired magazine. Email is here or ping me via the antiquated form of AOL IM (pomeranian99).

More of Me


Recent Comments

Collision Detection: A Blog by Clive Thompson