Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
3  
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. –  Pål GD Dec 29 '12 at 2:53

3 Answers 3

up vote 9 down vote accepted

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.

share|improve this answer

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$.

share|improve this answer
    
Can you please further elaborate it... –  Zara Dec 28 '12 at 15:56
    
It means that each edge exists with probability $p$. –  George Dec 28 '12 at 16:59

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)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.