Kaushal Kurapati\’s blog

Thoughts on Search, Technology and Management

Structure of Graphs and Networks – part 2

Posted by kaushalkurapati on May 28, 2007

We looked at Random network model in Part 1  of this series.

 Six degrees of Separation

In 1967 Stanley Milgram, a Harvard professor, ran an interesting experiment. He chose two people in Boston as the targets. He sent letters to randomly chosen people in the midwest (Omaha, Wichita). He asked these people to send letters to these targets if they knew them directly; if not, they should send letters to their personal acquaintances, who they thought may know these targets directly. Apparently 42 of the 160 letters he sent made it back to the targets! (26%). The median number of intermediaries required to reach the target was 5.5. Rounding it up to 6 gives the famous “any two people are separated by six degrees of separation“.

This model of the world says that we live in a small world. So any two nodes in a large human network can, on average, be reached via 6 links. This does not imply reaching a node 6 links away is easy…because at each node you would have to know which out-bound link to pursue to get to your target and without that knowledge, the search quickly becomes exponential and impossible to navigate to the target.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: