Saturday, 2 November 2013

104. Random Networks

'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 Ci of a node 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:

Crandom = 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 pc(N) such that if p(N) grows slower than pc(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 pc(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 pc below which only isolated clusters exist, but above which a 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 pc 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 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 logN. But, for r > 1/2, something very different happens. C scales as (4r-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 Tc, and rises continuously as the temperature is lowered gradually from Tc. Thus the percolation transition in a random network marks a distinct change in the evolution of the connection topology.

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).

No comments:

Post a Comment