What is Random Graph?

Random Graph, denoted by Gn,p, consists of n vertices and each possible edge between two vertices is present with independent probability p. Often one wishes to express properties of Gn,p not in terms of p but in terms of the average degree z of a vertex. The average number of edges on the graph as a whole is 1/2*n(n-1)p, and the average number of ends of edges is twice this, since each edge has two ends. So the average degree of a vertex is

where the last approximate equality is good for large n.  

Random Graph Vs Real-world Network

Clustering

Real-world networks show strong clustering or network transitivity, whereas Random graph model does not. A network is said to show clustering if the probability of two vertices being connected by an edge is higher when the vertices in question have a common neighbor. Watts and Strogatz measured this clustering by defining a clustering coefficient C, which is the average probability that two neighbors of a given vertex are also neighbors of one another. In many real-world networks the clustering coefficient is found to have a high value, anywhere from a few percent to 50 percent or even more. In the random graph on the other hand, the probabilities of vertex pairs being connected by edges are by definition independent, so that there is no greater probability of two vertices being connected if they have a mutual neighbor than if they do not. This means that the clustering coefficient for a random graph is simply C = p, or equivalently C ~ z/n.

Degree Distribution

The probability pk that a vertex in a random graph has degree exactly k is given by the binomial distribution

In the limit where n >> kz, this becomes

which is the well-known Poisson distribution. Both binomial and Poisson distributions are strongly peaked about the mean z, and have a large-k tail that decays rapidly as 1/k!. We can compare these predictions to the degree distributions of real networks by constructing histograms of the degrees of vertices in the real networks.

As the figure shows, in most cases the degree distribution of the real network is power-law degree distributions which is very different from the Poisson distribution.

Small World Effect

Random graphs having non-Poisson degree distributions can be generated by specifying a degree sequence, i.e., a specified set {ki} of the degrees of the vertices i = 1...n. Typically this set will be chosen in such a way that the fraction of vertices having degree k will tend to the desired degree distribution pk as n becomes large. Once one has one's degree sequence, the method for generating the graph is as follows: one gives each vertex i a number {ki} of “stubs",ends of edges emerging from the vertex, and then one chooses pairs of these stubs uniformly at random and joins them together to make complete edges. When all stubs have been used up, the resulting graph is a random graph with the desired degree sequence.

The mean number of neighbors of a randomly chosen vertex A in a graph with degree distribution pk is  

 

The probability distribution of the degree of the vertex to which an edge leads is proportional to kpk

and the number of edges emerging from the vertex other than the one we arrived along is one less than the total degree of the vertex and its correctly normalized distribution is therefore 

or, equivalently,

The average degree of such a vertex is then

......... (1)

This is the average number of vertices two steps away from our vertex A via a particular one of its neighbors. Multiplying this by the mean degree of A, which is just z = <k>, we thus find that the mean number of second neighbors of a vertex is

 ...............(2)

We can extend this calculation to further neighbours also. The average number of edges leading from each second neighbour, other than the one we arrived along, is also given by (1), and indeed this is true at any distance m away from vertex A. Thus the average number of neighbours at distance m is

where z1 = z = <k> and z2 is given by Eq. (2). Iterating this equation we then determine that

...............(3)

Depending on whether z2 is greater than z1 or not, this expression will either diverge or converge exponentially as m becomes large, so that the average total number of neighbors of vertex A at all distances is finite if z2 < z1 or infinite if z2 > z1 (in the limit of infinite n).

Thus the graph shows a phase transition similar to that of the random graph precisely at the point where 

z2 = z1.

Making use of Eq. (2) and rearranging, we find that this condition is also equivalent to

or, as it is more commonly written,

..........(4)

The quantity of interest in many networks is the typical distance through the network between pairs of vertices. If we are “below" the phase transition of Eq. (4), in the regime where there is no giant component, then most pairs of vertices will not be connected to one another at all, so vertex-vertex distance has little meaning. On the other hand, "above" the transition, where there is a giant component, all vertices in this giant component are connected by some path to all others. Eq. (3) tells us the average number of vertices a distance m away from a given vertex A in the giant component. When the total number of vertices within distance m is equal to the size n of the whole graph, m is equal to the so-called “radius" r of the network around vertex A. Indeed, since z2/z1>>1 well above the transition, the number of vertices at distance m grows quickly with m in this regime, which means that most of the vertices in the network will be far from A, around distance r, and r is thus also approximately equal to the average vertex-vertex distance l. Well above the transition therefore, l is given approximately by, or,

...............(5)

For the special case of the random graph, for which z1 = z and z2 = z^2

as noted above, this expression reduces to the well-known standard formula for this

case: 

The important point to notice about Eq. (5) is that the vertex-vertex distance increases logarithmically with the graph size n, i.e., it grows rather slowly. Even for very large networks we expect the typical distance through the network from one vertex to another to be quite small. In social networks this effect is known as the small-world effect, and was famously observed by the experimental psychologist Stanley Milgram in the letter-passing experiments he conducted in the 1960s (Milgram, 1967; Travers and Milgram, 1969; Kleinfeld, 2000).

References-
[1] M.E.J Newman, Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, U.S.A.
      "Random graphs as models of networks"