Random Network Phase Change

My network code is evolving.  Today, I was able to look at the phase change phenomenon in a randomly linked network.

To build a random network choose two nodes at random and connect them together.  As one continues to add links to the system, some nodes by chance end up with more links than others.  The number of nodes directly linked (the nearest neighbors) to a chosen node is called the “degree”.  The distribution of degree for a 1,000 node system is shown for various numbers of total links in the system in my post from a couple of days ago.

As more links are added to the system, more and more nodes are connected together.  Some nodes get connected to nodes that already have links, making larger groups of nodes linked together.  As one adds links to the system, new groups of 2 form as well as groups becoming linked together to form larger groups.

In the system simulated here, I have 1,000 nodes.  If I add 500 random links to the system, this would be enough to link every node once.  But because links are added randomly, some nodes are highly linked, and others aren’t linked at all.  One might expect the groups to get bigger gradually until there are so many links in the system, that nearly all the nodes are in one big group.

Instead, something else interesting happens as we add enough links in the system to theoretically connect every node (500 in my simulation).

If we look at the groups that form, the system goes through an abrupt transition from the unlinked phase to the linked phase when the (links in system)/(nodes in system) ~ ½.  See Figure 1 below.  The largest group rapidly grows from containing a tiny fraction of the nodes to containing nearly all of them.  This is the phase transition in random networks depicted in Watts’ book Six Degrees on pg 45 (hardback edition).  The value Average Links/Node = 0.5 is known as the critical point.  This was explained in 1959 by Erdos and Renyi (without the benefit of a straight-forward simulation like the one here).

Figure 1. Phase Transition Diagram 

What is the distribution of group size at Average Links/Node = 0.5? Figure 2 shows a histogram the group sizes for one simulation run.

Figure 2. Distribution of group sizes at the Critical Point. The largest groups are too
far off to the right to show on the histogram.  The largest group in the system
at the critical point has 118 nodes, or about 12% of the nodes.