Small-World Networks
Learn about small-worlds networks and their applications.
Complex networks became famous after a curious experiment called six degrees of separation. In this experiment, researchers stated that you could get in touch with anyone in the world by just passing your message forward to six persons on average.
This experiment showed that, even with our world being so large, it’s highly connected. Therefore, it’s easy to access anyone we want. This gave origin to the term small-world.
Small-world network definition
A small-world network is a network where each node can be accessed with only a small number of steps, even if we have a lot of nodes with a low degree, which means that nodes don’t have a lot of neighbors. Because of that, we can say that a small-world network has a low diameter.
The diameter of a network is the maximum distance between the two farther-apart nodes in the network. In other words, it measures the maximum amount of steps we need to take to walk from one side of the network to the other.
To calculate the diameter of a network with NetworkX, we can use the nx.diameter() method.
nx.diameter(G)
In a more mathematical sense, we say a network is a small-world network if the typical distance
This is the same as saying that if we increase the number of nodes by 10000, the average distance will grow by only 4 steps.
Small-world metrics characteristics
The small-world network is a complex network model, so it can’t be represented by traditional random graph models such as the Erdős–Rényi model. This happens because the characteristics of the small-world networks don’t appear when the network is generated by a random model.
Two main metrics are used to characterize the small-world networks:
Average shortest path length
Clustering coefficient
In small-world networks, we expect the average shortest path length between any two nodes to be small. It’s because, by definition, in this network, all nodes should be somewhat closer to each other than in a random network. This is a direct assumption that comes from saying that the diameter is small. If the largest distance is small, then the smaller distance should be at least equal, or on average, smaller than that. Random graph models satisfy the small average shortest path length assumption.
Small-world networks are also known for having a high clustering coefficient. This means that in this kind of network, we have several groups that are densely connected together, more than what we would expect to see in a random graph.