Small World

The SmallWorld hypothesis, that no human on the planet is more than 6 acquaintances away from anyone else, has been a part of folklore for ages. StanleyMilgram? was the first person to test it formally. It's the same on this wiki - no WikiPage is more than 6 links away from any other. Other websites have to keep maps and indexes, but not Wiki.

According to TheTippingPoint, Dr. Milgram sent envelopes to randomly selected people in Omaha Nebraska. The goal of the experiment is to see how long (and how many jumps) it would take to get the package to a stockbroker in New England. Each person was asked to send the package on to someone who might be able to send it on. According to the results, most of the packages arrived on the stockbroker's desk in 5 to 6 jumps.

Small World networks occur commonly in nature, and are currently a hot research topic. See (for example) http://www.santafe.edu/sfi/publications/Bulletins/bulletinFall99/workInProgress/smallWorld.html

Quoting from there: Studying intermediate kinds of networks led to the discovery that when just a few long-range, random connections replace the local edges of a lattice-like network, the characteristic path length decreases dramatically; a "shortcut" occurs. And while the first random rewiring has a great impact on path length, the clustering changes very little. Even when the separation of elements in a network is very small the clustering can remain almost as high as possible. This result is what Watts and Strogatz call a "small-world network." The name derives from the fact that it exhibits the short global separations that are typified (anecdotally) by social interactions while maintaining the high degree of clustering exhibited in most social sex networks.

RealWorld anecdote:

My wife, who operates a VirtualAssistant? business from home, recently acquired a client in another state. In the course of servicing his business (which does lecturing and training in marketing topics) he recommended a recorded lecture. She listened to this lecture. One of the RealWorld examples used in the lecture involved two people (Duncan G. and Karen B.) who were mentioned in a book he had read - both of whom we know first hand, they've been friends of ours for years.

So this guy (Carson P.) reads a book by Victor H. that talks about Duncan & Karen, uses this material in a lecture, then recommends the lecture to a personal friend of Duncan & Karen. Carson and Victor and D&K all live in different states and are in different lines of work. We were able to introduce Carson to Duncan, a meeting he'd completely not anticipated.

Oh, and how do we know Duncan & Karen? My mother met Karen when they worked together in a volunteer capacity: my mom was a musician and Karen is a singer/performer/producer.

  So ... Carson <- Victor <- Wife <- Me <- Mom <- Karen & Duncan

You can collapse (Wife <- Me), but it still works out to 6 or less.

-- GarryHamilton

: "Carson and Victor and D&K all live in different states and are in different lines of work."

This exemplifies a features of a network that makes it a SmallWorld: links that cross boundaries (social, geographic, ethnic, age, etc). The metaphorically longer the link, the smaller the network becomes in the SmallWorld sense.

One of the books on SmallWorlds pointed out a practical consequence of this: you sometimes have a better chance of finding a job not through folks you know well, but through those you know slightly. The latter provide an entry in social worlds you might never discover otherwise.

An Example

: So how well do you need to know these acquaintances? Do they have to know you? Do you have to be on speaking terms? -- IvesAerts

Apparently you have to know them well enough to ask them to send a package. If you know someone who knows someone who knows GeorgeBush, would you use this link to get a package to TonyBlair? I don't think so... -- An AnonymousDonor who has seen the movie SixDegreesOfSeparation which features Will Smith in his only decent part ever.

Is that so? Please demonstrate - find MagicTheGatheringX (without the X) in 5 links or less from this WikiPage. My bet is that you can't - because that page is on a small WikiIsland?, with no (or only a few) connections to the main body of Wiki.

OK, IvesAerts, then CategoryHomePage, CategoryCategory, CategoryGame. Then click on the heading for a list of items. Of course, I've just dropped the number of links by publishing this.

Hm, thanks. Didn't think of the big category pages. I'm a newbie.

Discussion

"Let's see if we can get to every page in wiki."

Not to rain on the parade too early but... Ward has indicated on OrphanPages that there are a number of orphan pages in the database which are not linked to any others. Those pages are (effectively) infinitely separated. Care to modify the rules of the game somehow to exclude those pages?

Have you seen WikiList? There are no OrphanPages. Of course, if you count that, all pages are at most 2 hops away. If not, you can only deal with one subgraph at a time. And do you count reverse links?

See WikiMines if you'd like to write a program to study this question and need 200k of raw link data to get started.

Dr. Milgram only counted the packages that arrived. The correct conclusion to draw from his experiment is "Links cannot be established over more than 6 hops."

As an aside, most of his chains went through a few very well connected individuals. Society is more like a StarNetwork? than a MeshNetwork?.

--BenAveling

See SixDegreesOfKevinBacon, ErdosNumber, WardNumber, KiboNumber, SixDegreesOfExtremeProgramming, SixDegreesOfWikiWiki, SocialNetworks