Evolution of a random network

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.

${\displaystyle {0<\left\langle k\right\rangle <1}}$, ${\displaystyle {\left(p<{\frac {1}{n}}\right)}}$

For ${\displaystyle {\left\langle k\right\rangle =0}}$ the network consists of ${\displaystyle {N}}$ isolated nodes. Increasing ${\displaystyle {\left\langle k\right\rangle }}$ means adding ${\displaystyle {N\left\langle k\right\rangle =pN(N-1)/2}}$ links to the network. Yet, given that ${\displaystyle {\left\langle k\right\rangle <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, ${\displaystyle {\frac {N_{G}}{N}}}$, remains zero. The reason is that for ${\displaystyle {\left\langle k\right\rangle <1}}$ the largest cluster is a tree with size ${\displaystyle {N_{G}\sim lnN}}$, hence its size increases much slower than the size of the network. Therefore, ${\displaystyle {N_{G}/N=lnN/N\rightarrow 0}}$ in the ${\displaystyle {N\rightarrow \infty }}$ 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.[1]

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 ${\displaystyle {\left\langle k\right\rangle <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 another 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.

${\displaystyle {0<\left\langle k\right\rangle =1}}$, ${\displaystyle {\left(p={\frac {1}{n}}\right)}}$.

The critical point separates the regime where there is not yet a giant component ( ${\displaystyle {0<\left\langle k\right\rangle <1}}$ ) from the regime where there is one ( ${\displaystyle {\left\langle k\right\rangle >1}}$ ). At this point, the relative size of the largest component is still zero. Indeed, the size of the largest component is ${\displaystyle {N_{G}\sim N^{\tfrac {2}{3}}}}$. Consequently, ${\displaystyle {N_{G}}}$ grows much slower than the network's size, so its relative size decreases as ${\displaystyle {{\frac {N_{G}}{N}}\sim N^{-{\tfrac {1}{3}}}}}$ in the ${\displaystyle {N\rightarrow \infty }}$ limit. Note, however, that in absolute terms there is a significant jump in the size of the largest component at ${\displaystyle {\left\langle k\right\rangle =1}}$. For example, for a random network with ${\displaystyle {N=7\ast 109}}$ nodes, comparable to the globe's social network, for ${\displaystyle {0<\left\langle k\right\rangle <1}}$ the largest cluster is of the order of ${\displaystyle {N_{G}\simeq lnN=ln(7\ast 109)\simeq 22.7}}$. In contrast at ${\displaystyle {\left\langle k\right\rangle =1}}$ we expect ${\displaystyle {N_{G}\simeq N^{\tfrac {2}{3}}=(7\ast 109){\tfrac {2}{3}}\sim 3\ast 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.[1]

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 this regime. The size of the giant component is described as follows ${\displaystyle {N_{G}=(p-p_{c})N}.}$

${\displaystyle {\left\langle k\right\rangle >1}}$, ${\displaystyle {\left(p>{\frac {1}{n}}\right)}}$.

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:

${\displaystyle {N_{G}/N\sim \left\langle k\right\rangle -1}}$

or

${\displaystyle {N_{G}\sim (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 ${\displaystyle {\left\langle k\right\rangle =1}}$. For large ${\displaystyle {\left\langle k\right\rangle }}$ the dependence between ${\displaystyle {N_{G}}}$ and ${\displaystyle {\left\langle k\right\rangle }}$ 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.[1]

As connections are added to a network, there comes a point when ${\displaystyle \langle k\rangle =lnN}$, and the giant component absorbs all nodes, so there are no isolated nodes or unconnected components.

${\displaystyle {\left\langle k\right\rangle >\ln N}}$, ${\displaystyle {\left(p>{\frac {\ln N}{N}}\right)}}$.

For sufficiently large p the giant component absorbs all nodes and components, hence ${\displaystyle {N_{G}\simeq N}}$. In the absence of isolated nodes the network becomes connected. The average degree at which this happens depends on ${\displaystyle {N}}$ as ${\displaystyle {\left({\frac {\ln N}{N}}\right)\rightarrow 0}}$. Note that when we enter the connected regime the network is still relatively sparse, as ${\displaystyle {\left({\frac {\ln N}{N}}\right)\rightarrow 0}}$ for large N. The network turns into a complete graph only at ${\displaystyle {\left\langle k\right\rangle =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 ${\displaystyle \langle k\rangle }$ collapse into a giant component through a phase.[1]

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.

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.[1]

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,[4] gels,[5] and other material development such as cellulose with tunable properties.[6]

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

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,[9] or prediction of node properties.[10]