Small World Networks
"Any network can be a small-world network as long as it has some way of embodying order yet retains some small amount of disorder".
-- Duncan Watts

Good News !!

You are viewing a draft of the book entitled "Patterns – The Art, Soul, and Science of Beholding Nature". The final version of this book has now being published as an Amazon Kindle eBook.

There are some significant changes in the eBook that are not in this draft. You may purchase the eBook here

Some of the ideas in the eBook are contained in posts at my Patterns In Nature Blog. You are encouraged to visit this blog site. If you press the "Like" button shown below, your Facebook page will provide you with short notifications and summaries of new blog posts as they become available.

A small-world network is a network graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of links. A small world network, where nodes represent people and edges connect people who are acquainted in some way, captures the "small world" phenomenon of strangers being linked by a small number of acquaintances.

Widely diverse patterns have strikingly similar small-world connectivity architecture. Some examples are electrical power grids, nervous systems, social networks, the Internet, ecosystems, and epidemics.

One such small-world topology is often called the Watts-Strogatz (WS) model. Here, only a few random links are needed to generate a short average path length which results in high connectivity between remote nodes and clusters. In the graph shown to the left, nodes #5 and #9 are connected via a randomly generated link that produces a connection between two remote clusters. Short overall path lengths and high clustering are the characteristic signatures of small world networks. These characteristics result in a graph that is somewhere between the extremes of ordered (regular) and disordered (random).

Watts and Strogatz ran a series of computer simulations where they started with a regular network. With each step in the simulation, an existing link was randomly chosen and rewired between one node and another. The network's connectivity was assessed at each step. Surprisingly, connectivity increased dramatically with only a small amount of randomization. Thereafter, any further increase in connectivity was minimal. Early on in the simulation, the network became a  "small world" and did not get significantly smaller. Watts and Strogatz showed that randomly rewiring only a few links in such a network dramatically reduced the number of links required to reach distant nodes. This dramatically increased connectivity within the network. What is particularly interesting is that they found that the transition to a small world is effectively undetectable at a local level. They pointed out that "nothing about your immediate neighborhood would tell you that the world had become small".

The Watts-Strogatz model offers a possible explanation for phenomena such as epidemics. An epidemic is an "encounter network". It could easily be contained if the infected individuals remained in their cluster and did not make contact with the rest of the world. But a random connection (such as an infected individual flying from one country to another) could drastically widen the encounter network and cause the disease to spread to other clusters.

You are invited to explore more detail by looking at regular networks, random networks, and scale-free networks.

Useful References


Table Of Contents