Ever hear of Six Degrees of Separation? It’s about Small World networks. Stanley Milgram ran the Small World experiment to find out if two randomly selected individuals knew each other. Usually, most knew each other through just a few intermediaries.

Any individual in a social network is just a few “hops” to any other individual.

Take a simple graph of 50 nodes or individuals. Each is connected to the node next to it. (I’ll use NetLogo to illustrate)
small-worlds-1.jpg

Take two random nodes on this graph. Say you want to pass a message from Node A to Node X. A has to pass the message through a series of nodes to reach X. So the message passes from A to B to L to M to Y to X. The maximum distance is the distance between nodes on the opposite sides of the circle.

Here, average path link is 6.5.

What if there were alternate connections between nodes. Node A can take a “shortcut” through the middle. So if A has to pass that message to X again, he can take a shortcut by passing the message straight to Z and then to X – bypassing B, L, and M.

So add a random connection between one random node and another random node. This one reduces the average path link to 5.523 (the number will vary within a range).

If you add three random connections, it looks like this.
small-worlds-2.jpg

This reduces the average path link to 4.426
That’s only with three extra connections.

Giving each of the 50 nodes an added connection reduces average path to roughly 2.8.

We can startegically position extra connections to make networks more efficient. Flows of information or resources can reach their destinations with fewer stops in between. The is has benefits ranging from city traffic to new methods to find kidney transplants.

Advertisements