Random graph process

502 Views Asked by At

Let $G=(V,E)$ be a graph and $p\in(0,1]$. We consider the following random graph process denoted $(G_n)_{n\geq 1} = (V,E_t)_{t\geq1}$. At each stage $t\geq 1$, every edge in $E$, independently of the others, belongs to $E_t$ with probability $p$, and does not belong to $E_t$ with probability $1-p$.

I would like to know if there is a name and a literature for such graph processes.

More generally, is there a literature on random graph processes?

1

There are 1 best solutions below

2
On

I'm not sure how the graph is evolving with time from your description to be honest, however the concept of random graph process has been introduced for the first time by Erdős and Rényi in their classical paper "On the evolution of Random graphs", http://snap.stanford.edu/class/cs224w-readings/erdos60random.pdf.

Just to give you a summary on the way it works, you start with an empty graph on n vertices, so at time $t=0$ you start with the graph $E_n$. Then at time $t=1$ you add randomly one of the ${n \choose 2}$ possibly edges, all being equally likely (i.e. each having probability $\frac{1}{{n \choose 2}}$), and you get a graph $G_1$ with one edge. At time $t=2$ you add randomly another edge from the remaining ${n \choose 2}-1$ edges, again each equally likely (i.e. each having probability $\frac{1}{{n \choose 2}-1}$), and so on until at time $t={n \choose 2}$ you finally have the complete graph on your $n$ vertices $K_n$.

The total number of different "graph processes" you can have starting from $E_n$ to reach $K_n$ is ${n \choose 2}!$