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.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Wow, that's way not how probability works! If you flip five coins, you haven't run out of sides the coin can land on, it will still either go head or tail up. Your question would be answered, not by learning about random graphs, but about probability theory. The answer is that given $n$ vertices, for every pair $v$ and $u$, we flip a coin. If head's up, we add the edge otherwise, we don't. That's your 50% chance of the edge appearing or not. Remarkably, if you have countably many edges, this graph is unique and referred to as the random graph. $\endgroup$– Pål GDDec 29, 2012 at 2:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$.
answered Dec 28, 2012 at 15:50
-
-
$\begingroup$ It means that each edge exists with probability $p$. $\endgroup$– GeorgeDec 28, 2012 at 16:59
$\begingroup$
$\endgroup$
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)$.
