'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