Small World Networks

Essential knowledge:

• Networks are said to have a Small World property if any two nodes are connected by a short number of hops, typically less than six. This means it is possible to cross the network very quickly.

• In real life this has lots of interesting effects. For example, it means that any two people are often connected by a common acquaintance.

You may be interested that:

One of the earliest mentions of the small world phenomenon was by a Hungarian writer Frigyes Karinthy, who wrote a book of short stories entitled ‘Everything is Different’.

One of these stories was ‘Chains’, in which one of the story characters believed that any two individuals are separated by five acquaintance chains at most. This piece of literature got the attention of many mathematicians, sociologists and scientist in the following decades.

In 1967, Stanley Milgram, who is a social psychologist, wanted to know how many steps does it need for any two individuals in the United States to reach each other. For this reasons he conducted an experiment asking people in Omaha in Nebraska to send a letter to a stockbroker in Boston; but they were asked not to send it directly, instead they were asked to pass it to anyone who they knew on a first-name basis, thus creating an acquaintance chain.

Many expected the chains to include hundreds of people, but surprisingly the average chain length for the successful 64 attempts was 6.5 only, hence, the expression ‘Six Degrees of Separation’ was used to refer to this phenomenon. It was this outcome that established the concept of small worlds.

In 2003, Dodds, Muhamad and Watts conducted the same experiment again, but this time utilizing the power of the World Wide Web through emails. There were 18 targets from 13 different countries. The result of that experiment confirms Milgram’s results. Moreover, in a most recent research conducted on Facebook by Backstrom et al, it was reported that an average chain length of 4 separates any two individuals on Facebook.

Those experiments demonstrate the small world effect, in which large social networks are tightly connected in their nature. As a result, there are actually many unpredicted links among different individuals whom we would expect to be far from each other.

Have you experienced this small world phenomenon in your own social networks?

If you’re really curious:

Small world is a network feature that can be identified using the following key properties:

1. The existence of short paths between most of their nodes (low diameter).

2. It tends to have cliques with high clustering co-efficient (you will be introduced to ‘clustering co-efficients’ in step 1.14).

3. The degree of nodes in the network has a power law distribution, leading to a few dominant hubs with very high degree.

Although, in such networks, most nodes are not connected directly to each other, there are a significantly small number of hops between any two nodes.

It seems strange for such networks to have short paths and to be highly clustered, as clustering might lead to locality. Watts and Strogatz demonstrated a small world model that can generate a network that has short paths and is highly clustered. This model starts with a regular network with high clustering co-efficient, and then it adds a number of random connections that will result in minimising the path lengths.

Optional further readings

1. Travers, J and S. Milgram, S (1969) ‘An Experimental Study of the Small World Problem’, Sociometry, vol. 32, no. 4, pp. 425-443

2. Watts, DJ and Strogatz, SH (1998) ‘Collective dynamics of `small-world’ networks’, Nature, vol. 393, no. 6684, pp. 440–442, Jun

3. Dodds, PS, Muhamad, R and Watts, DJ (2003) ‘An Experimental Study of Search in Global Social Networks’, Science, vol. 301, no. 5634, pp. 827–829, Aug

4. Backstrom, L, Boldi, P, Rosa, M, Ugander, J and Vigna, S (2012) ‘Four degrees of separation’, in Proceedings of the 3rd Annual ACM Web Science Conference, New York, NY, USA, 2012, pp. 33–42