Evolution of a random network

Conditions for emergence of a giant component

Condition for the emergence of the giant component was predicted by Erdős and Renyi in their paper:

⟨ k ⟩ = 1 , where ⟨ k ⟩ is the average degree of a random network.

Thus, one link is sufficient for its emergence of the giant component. If expressing the condition in terms of p , one obtain:
P c = 1 N − 1 ≈ 1 N (1)
Whew N is the number of nodes, P c is the probability of clustering. Therefore, the larger a network, the smaller p is sufficient for the giant component.

Regimes of evolution of a random network

Three topological regimes with its unique characteristics can be distinguished in network science: subcritical, supercritical and connected regimes.

Subcritical Regime

The subcritical phase is characterised by small isolated clusters, as the number of links is much less than the number of nodes. A giant component can be designated any time to be the largest isolated small component, but the difference in cluster sizes is effectively negligible in this phase.

0 < ⟨ k ⟩ < 1 , ( p < 1 n )

For ⟨ k ⟩ = 0 the network consists of N isolated nodes. Increasing ⟨ k ⟩ means adding N ⟨ k ⟩ = p N ( N − 1 ) / 2 links to the network. Yet, given that ⟨ k ⟩ < 1 , there is only a small number of links in this regime, hence mainly tiny clusters could be observed. At any moment the largest cluster can be designated to be the giant component. Yet in this regime the relative size of the largest cluster, N G N , remains zero. The reason is that for ⟨ k ⟩ < 1 the largest cluster is a tree with size N G ∼ l n N , hence its size increases much slower than the size of the network. Therefore, N G / N = l n N / N → 0 in the N → ∞ limit. In summary, in the subcritical regime the network consists of numerous tiny components, whose size follows the exponential distribution. Hence, these components have comparable sizes, lacking a clear winner that we could designate as a giant.

Critical Point

As we keep connecting nodes, the pairs joining together will form small trees, and if we keep connecting nodes, a distinguishable giant component emerges at critical point <k> = 1.

This means that at the moment that each component has on average 1 link, a giant component emerges. This point corresponds to probability p = 1/ (N-1), as the probability of having a link between two nodes is the ratio of the one case when that one link connect the two randomly chosen nodes, divided by all the other possibilities how that one connection can connect one of the nodes to an other node, which is N-1, as a node can connect to all other nodes but itself (excluding the possibility of a self loop in this model).

This also has the implication, that the larger a network is, the smaller p it needs to have a giant component emerging.

0 < ⟨ k ⟩ = 1 , ( p = 1 n ) .

The critical point separates the regime where there is not yet a giant component ( 0 < ⟨ k ⟩ < 1 ) from the regime where there is one ( ⟨ k ⟩ > 1 ). At this point, the relative size of the largest component is still zero. Indeed, the size of the largest component is N G ∼ N 2 3 . Consequently, N G grows much slower than the network's size, so its relative size decreases as N G N ∼ N − 1 3 in the N → ∞ limit. Note, however, that in absolute terms there is a significant jump in the size of the largest component at ⟨ k ⟩ = 1 . For example, for a random network with N = 7 ∗ 109 nodes, comparable to the globe's social network, for ⟨ k ⟩ = 1 the largest cluster is of the order of N G ≃ l n N = l n ( 7 ∗ 109 ) ≃ 22.7 . In contrast at ⟨ k ⟩ = 1 we expect N G ≃ N 2 3 = ( 7 ∗ 109 ) 2 3 ∼ 3 ∗ 106 , a jump of about five orders of magnitude. Yet, both in the subcritical regime and at the critical point the largest component contains only a vanishing fraction of the total number of nodes in the network. In summary, at the critical point most nodes are located in numerous small components, whose size distribution follows. The power law form indicates that components of rather different sizes coexist. These numerous small components are mainly trees, while the giant component may contain loops. Note that many properties of the network at the critical point resemble the properties of a physical system undergoing a phase.

Supercritical Regime

Once the giant component had emerged upon passing the critical point, as we add more connections, the network will consist of a growing giant component, and less and less smaller isolated clusters and nodes. Most real networks belong to ths regime. The size of the giant component is described as follows Ng = (p – pc) N.

0 < ⟨ k ⟩ > 1 , ( p > 1 n ) .

This regime has the most relevance to real systems, as for the first time we have a giant component that looks like a network. In the vicinity of the critical point the size of the giant component varies as:
N G / N ∼ ⟨ k ⟩ − 1
or
N G ∼ ( p − p c ) N (2)
where pc is given by (1). In other words, the giant component contains a finite fraction of the nodes. The further we move from the critical point, a larger fraction of nodes will belong to it. Note that (2) is valid only in the vicinity of 0 < ⟨ k ⟩ = 1 . For large 0 < ⟨ k ⟩ the dependence between N G and 0 < ⟨ k ⟩ is nonlinear. In summary in the supercritical regime numerous isolated components coexist with the giant component, their size distribution following exponential distribution. These small components are trees, while the giant component contains Loops and cycles. The supercritical regime lasts until all nodes are absorbed by the giant.

Connected Regime

As connections are being added to a network there comes a point when <k> = lnN, and the giant component absorbs all nodes making the network fully connected, having a complete graph.

0 < ⟨ k ⟩ > l n N , ( p > l n N N ) .

For sufficiently large p the giant component absorbs all nodes and components, hence N G ≃ N . In the absence of isolated nodes the network becomes connected. The average degree at which this happens depends on N as ( l n N N ) → 0 . Note that when we enter the connected regime the network is still relatively sparse, as ( l n N N ) → 0 for large N. The network turns into a complete graph only at ⟨ k ⟩ = N − 1 . In summary, the random network model predicts that the emergence of a network is not a smooth, gradual process: The isolated nodes and tiny components observed for small <k> collapse into a giant component through a phase.

Water-ice transition

Phase transitions take place in matter, as it can be considered as a network of particles. When water is frozen, upon reaching 0 degree (the critical point) the crystalline structure of ice emerges according to the phase transitions of random networks: As cooling continues, each water molecule binds strongly to four others, forming the ice lattice, which is the emerging network.

Magnetic phase transition

Similarly, magnetic phase transition in ferromagnetic materials also follow the pattern of network evolution: Above a certain temperature, spins of individual atoms can point in two different directions. However, upon cooling the material down, upon reaching a certain critical temperature, spins start to point in the same direction, creating the magnetic field. The emergence of magnetic properties in the structure of the material resemble to the evolution of a random network.

Physics and chemistry

As we could see in the above examples, network theory applies to the structure of materials, therefore it is also applied in research related to materials and their properties in physics and chemistry.

Particularly important areas are polymers, gels, and other material development such as cellulose with tunable properties.

Biology and medicine

Phase transitions are used in research related to the functioning of proteins or emergence of diabetes on the cell-level. Neuroscience also extensively makes use of the model of the evolution of networks as phase-transition occur in neuron-networks.

Network science, statistics and machine learning

Phase transition of a network is naturally a building block of more advanced models within its own discipline too. It comes back in research examining clustering and percolation in networks, or prediction of node properties.