Transportation Geography and Network Science/Random graphs

Random Graph

A random graph is a graph generated by some random processes. The theory of random graph was founded by Erdős and Rényi in a series of papers in the 1950's.

In most of the random graph models, the number of vertices is fixed and edges among them are placed in some random ways. One of the simplest way to do this is to also fix the number of edges and place them uniformly and randomly among all possible pair of vertices. In other words, we generate a probability distribution of graphs with v vertices and e edges, and each of them have the same probability. This model is often referred to as G(v,e) where v denotes the number of vertices and e denotes the number of edges.

Although G(v,e) appears to be a simple model, it turns out that it is not easy to obtain some of the important properties we are interested in. Thus, another slightly different model has been proposed and most of the mathematical work has been conducted on this model called G(v,p) where v denote the number of vertices and p denote the probability of having an edge between each pair of vertices. In other words, the graph in G(v,p) model is constructed by scanning through each pair of the n vertices and place an edge between them with probability p.

Properties

The probability of having e edges in G(v,p) is

$p^{e}(1-p)^{{\binom {v}{2}}-e}$

For example, considering a random graph G(3,0.8), the probabilities that the graph have one, two or three edges are shown as follows:

Random graph G(3,0.8)

Probabilities of a graph with e edges

$P(e)={\binom {\binom {v}{2}}{e}}p^{e}(1-p)^{{\binom {v}{2}}-e}$

Number of random graphs(v vertices) have e edges:

$N(e)={\binom {\binom {v}{2}}{e}}$

For example, there are 15 different random graphs with 4 vertices and 2 edges:

random graphs with 4 vertices and 2 edges

Expected number of degrees

${\binom {v}{2}}p$

Expected degree value

$c=(v-1)p$

Degree distribution

$p_{k}={\binom {v-1}{k}}p^{k}(1-p)^{v-1-k}$

In large networks where mean degree is approximately constant (e.g. social network), the degree distribution becomes Poisson distributed

Clustering Coefficient

The clustering coefficient measures the transitivity of the network. It is defined as the probability that two network neighbors of a vertex are also neighbors of each other. Since in G(v,p), each pair of vertices is connected with probability p independent of everything else, the clustering coefficient C is

$C=p={\frac {c}{v-1}}$

Giant Component

One important characteristic studied in random graph is how the graph evolves when v becomes large. More specifically, if we know that most of the vertices in graph are connected as v goes to infinity, then it means there exists a component grows at a comparable rate as the graph. This component is called giant component. It can be shown that a giant component exists if and only if the mean degree value is greater than 1.