Small-World Networks

A network is a set of nodes and edges. It is an abstraction for many real-world systems: social circles, gene circuits, neuronal networks, power grids, etc. Small-world networks are those network topologies which are as densely clustered as regular lattices, but the distance between any two nodes is as low as in random graphs. Most examples of real-life networks have been found to be small-world networks, and they have been studied for their interesting properties. The below interactive visualization allows you to interpolate between a regular lattice and a random graph, thereby showcasing the middle-ground of small-world networks.


Calculated Parameters:




Network Control:





In the above interactive visualization, the white color dots arranged along a circle represent the nodes of the network, whereas the straight and curved lines connecting them represent the edges. Red color edges have more propensity to get rewired than blue colored ones. Before rewiring, all nodes are uniformly connected to their nearest nodes, thereby constituting a regular lattice. As the rewire propensity increases, the regular lattice transforms into a random graph.


Explanation

Clustering coefficient represents the tight-knit nature of a node's neighbourhood, averaged across all nodes. To be more precise, if a node \(n\) has \(k_n\) neighbours, then these \(k_n\) neigbours can have a maximum of \(k_n (k_n - 1) / 2\) connections between them (if they're fully connected). The extent to which this maximum connectedness is achieved across all nodes is called the clustering coefficient.
Characteristic length is the length of the shortest path between two nodes, averaged across all possible pairs of nodes.

A regular lattice with, say 30 nodes and 4 edges per node, is characterized by a high clustering coefficient and high characteristic length. As soon as some edges get rewired, this introduces shortcuts in the network which brings down the characteristic length, while having not much effect on the clustering coefficient. This is the realm of small-world networks, and its effects are more prevalent in bigger graphs with sparser connections. As the rewiring propensity is increased, the regular network unravels, giving rise to a random graph which has both: low clustering coefficient and low characteristic length.

Small-world networks have many special properties: contagions (disease or rumours) spread faster, consensus is correctly established, strategies find it difficult to establish, information is delivered faster, oscillators find it easier to establish synchrony, etc. These properties definitely play a role in the the real-world networks that are structured as small-world networks, and may play a role behind fascinating properties observed in them.


Note:
  1. This interactive visualization is inspired by the research paper titled "Collective dynamics of small-world networks" by Duncan Watts & Steven Strogatz, published in Nature in 1998 (link)
  2. Clustering coefficient is straightforward to compute, whereas characteristic length computation requires Djikstra's algorithm to run, so this website may lag on lower-end devices when simulated with large networks.
  3. Related: Porous percolation

Developed by ChanRT | Fork me at GitHub