'

*Erdős and Rényi acknowledged for the first time that real graphs, from social networks to phone lines, are not nice and regular. They are hopelessly complicated. Humbled by their complexity, the two assumed that these networks are random*' (Barabási,Linked (2002)).
A random network is one in
which the edges are distributed randomly. Such networks are

*easily traversed*; this means that the path length or*distance*(i.e. the number of edges) between any two nodes is typically quite small. For random networks, as also for regular networks, the number of edges per node has an approximately Gaussian distribution, with a mean value that is a measure of the*scale*of the network.
Historically, complex graphs
with no easily discernible design principles were modelled by Erdős and Rényi (ER) in the 1950s as random graphs. In this simplest
possible model (

*the ER model*) of a complex graph, if there are*N*nodes, and if every pair of nodes is connected with a probability*p*, then there are ~*pN*(*N*-1)/2 edges, distributed randomly. The ER model amounted to equating complexity with randomness and was therefore, naturally, superseded by more sophisticated models of complex networks. But it still provides a very useful*benchmark*for understanding the degree of complexity of real-life networks.
The
degrees of different nodes in a graph or network are different. One can define
a

*degree-distribution function**P*(*k*) which gives the probability that any particular node has a degree*k*, i.e. it is connected to*k*other nodes. Suppose <*k*> is the average degree of a network. Most of the nodes in a random network have nearly the same degree, which is close to <*k*>. The degrees of the various nodes in a random graph or network follow a Poisson distribution, with a peak at*P*(<*k*>).
The
degree distribution

*P*(*k*) in most of the real-life networks deviates significantly from the Poisson distribution. In fact, it generally follows a*power law*(see below).
The
notion of

*clustering coefficient*has a particularly simple meaning for a random network. Consider a particular node in a random network. The clustering coefficient*C*of a node_{i}*i*is a number which is a measure of how many other nodes are connected to it. For a random network, this number is nothing but the average degree <*k*> of the network, which is also the probability*p*that any two nodes of the network are connected. All nodes in a random network have the same clustering coefficient:*C*=

_{random}*p*= <

*k*>/

*N.*

*Evolution*of a graph or network as more and more nodes or edges get added (or even subtracted) is of direct relevance to the study of evolution in complex systems. Historically, such investigations in graph theory were first carried out for random graphs. One starts with a set of

*N*nodes, and introduces random edges in it successively. As the number of edges grows, the connection probability

*p*for any pair of nodes increases. Eventually one obtains a fully connected graph, i.e.

*p*→ 1, and the number of edges is the maximum possible, namely

*N*(

*N*-1)/2.

One aim of such studies is to
see what happens when

*N*→ ∞. Another is to investigate how new properties emerge as the value of*p*increases gradually. An important result obtained by Erdős and Rényi was that*many properties of random graphs appear quite suddenly*. Usually there is a*critical or threshold connection probability**p*(_{c}*N*) such that if*p*(*N*) grows slower than*p*(_{c}*N*) as*N*→ ∞, then almost every random graph with connection probability*p*(*N*) does not have the property which would have otherwise appeared in the graph if*p*(*N*) were greater than*p*(_{c}*N*).__Percolation transitions in random networks__

'

*Random network theory tells us that as the average number of links per node increases beyond the critical one, the number of nodes left out of the giant cluster decreases exponentially*' (Barabási,*Linked*).
'

*Recognizing that passing a critical threshold is the prerequisite for the spread of fads and viruses was probably the most important conceptual advance in understanding spreading and diffusion*' (Barabási,*Linked*).
For a random network there
exists a critical connection probability

*p*below which only isolated clusters exist, but above which a_{c}*giant cluster*emerges which spans a large portion of the network, or the entire network. We then speak of a percolation transition.
Significant
analogies or correspondences exist between percolation transitions in networks
and the regular thermodynamic phase transitions in materials. In
particular, the notion of continuous (or second-order) and discontinuous (or
first-order) phase transitions in materials has its parallel in network theory.
The critical connection probability

*p*in a random network can be interpreted as the equivalent of the critical point in a thermodynamic phase transition. Suppose, in the spirit of the ER model, we start with a set of_{c}*N*isolated vertices and introduce edges randomly, one by one. At any stage in the evolution of this random network, we can identify components or connected subgraphs in the network. The larger the size of a component, the greater is the chance that it would merge with another component as more and more edges are added, rather like the gravitational attraction between objects.
Suppose

*rN*edges have been introduced randomly at some stage. Let*C*denote the size of a component. For*r*< 1/2 the largest value of*C*is quite small, as it scales as log*N*. But, for*r*> 1/2, something very different happens.*C*scales as (4*r*-2)*N*when*r*is slightly greater than ½. That is,*C*scales linearly with*N*, starting with the value 0 for*r*= 1/2. This is very similar to how the order parameter of a continuous phase transition varies as a function of the control parameter, say temperature: It is zero above the critical temperature*T*, and rises continuously as the temperature is lowered gradually from_{c}*T*. Thus the percolation transition in a random network marks a distinct change in the evolution of the connection topology._{c}
Can we have a percolation
transition in a random network that is the equivalent of a

*discontinuous*or first-order phase transition? The answer according to Achlioptas, D’Souza and Spencer (2009) is ‘Yes’, provided we change the rule for the evolution of the network. Several such rules are conceivable, and even small changes may be effective. In one such rule, we begin by choosing*two*edges randomly, and then discard one of them according to some criterion. Of course, if the edge to be discarded is selected randomly from the pair of edges, we get nothing new. However, if a non-random selection rule is operative for deciding the edge to be discarded, a discontinuous or first-order percolation transition can become possible.
Small changes in edge-formation
rules can sometimes alter drastically the nature of percolation transitions in
complex networks. When an edge is introduced, it connects two vertices, each of
which has a certain component size. One example of a selection rule for
obtaining first-order percolation transition behaviour is that, from the pair
of edges chosen randomly, we keep the one which minimizes the product of the
sizes of the two components which will get merged by this choice, and discard
the other candidate edge. Alternatively, instead of minimizing the product of
the two component sizes, we could choose to minimize their sum. In either case,
what would have been a continuous percolation transition becomes a
discontinuous, sudden, or

*explosive*percolation transition (cf. Achlioptas, D’Souza and Spencer 2009).