Random graph model

Question

When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean?

For example if probability is 0.5, does that mean that we can just add two edges in a graph because 0.5+0.5=1.

Answer 1

Suppose you wish to compute the random graph $G(n,p)$ that is the graph with $n$ vertices where each edge is added with probability $p.$

Suppose you have a coin that gives tails with probability $p$ and heads with probability $1-p.$

Then what you do you take $\{1,...,n\}$ to be the vertex set of your graph and for each pair $(i,j) \in { \{1,\ldots,n\} \choose 2}$ you flip your coin. If it comes tails you add the edge $(i,j)$ to your graph otherwise you don't.

Answer 2

In the random $G(n,p)$ model, each of the $\binom{n}{2}$ edges is added to the graph with probability $p$ independently. That means that if you consider any two edges, then both are in the graph with probability $p^2$, not $2p$.

Answer 3

In addition to what is said, which is correct, you can build a random graph $G(n,p)$ for $0 \leq p \leq 1$ as follows:

Assume you have a set of vertices $V$ and empty edges $E$. For each $v$ in $V$: For each $u$ in $V$ (where $u > v$ with respect to some total order among the nodes of $V$): generate a uniform random number $r$ where $r \in [0,1]$. If ($r \leq p$) then include the edge $(v,u)$ and $(u,v)$ to $E$.

This generates a random graph $G = (V,E)$ denoted $G(n,p)$ where $|V| = n$. This however is a directed graph. If you want to make it a directed graph, which as that case does not follow the definition, then add only the graph $(v,u)$.