1
$\begingroup$

We have two Erdos-Renyi random graphs, $G_1$ and $G_2$, generated with probability $p_1$ and $p_2$, respectively. If we take the union $G_1$ $\bigcup$ $G_2$, we obtain another Erdos-Renyi graph, $G_3$.

I know that the probability of having a link in $G_3$ is: $$p_1 + p_2 - p_1p_2$$ but I cannot understand why.

$\endgroup$
  • $\begingroup$ $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ $\endgroup$ – saulspatz Oct 12 '18 at 14:35
0
$\begingroup$

Approach 1: $G_3$ contains edge $vw$ if either $G_1$ or $G_2$ contains it. We add the probabilities of each of those cases, then subtract the overlap, getting \begin{align} \Pr[vw \in E(G_3)] &= \Pr[vw \in E(G_1)] + \Pr[vw \in E(G_2)] - \Pr[vw \in E(G_1) \cap E(G_2)] \\ &= p_1 + p_2 - p_1p_2. \end{align} It's crucial that $G_1$ and $G_2$ are independent, so we can just multiply $p_1$ and $p_2$ to find the probability that an edge is in both graphs.

Approach 2: $G_3$ contains an edge $vw$ unless neither $G_1$ nor $G_2$ contains it. So the probability that $G_3$ does not have the edge is $$ \Pr[vw \notin E(G_3)] = \Pr[vw \notin E(G_1)] \cdot \Pr[vw \notin E(G_2)] = (1-p_1)(1-p_2) $$ and therefore the probability $G_3$ does have the edge is $$ \Pr[vw \in E(G_3)] = 1 - (1-p_1)(1-p_2) = p_1 + p_2 - p_1 p_2. $$

$\endgroup$
0
$\begingroup$

An Erdos-Renyi graph is defined by a set of nodes N, and a probability p. The links between nodes are derived as follows; Choose a pair of nodes {n(1), n(2)} without replacment. Link these if a random draw from the interval [0,1] is less than or equal to p.

If G3 = G1 union G2 apply this algorithm to G1 disjoint union G2 then the Expectation of the total number of links satisfies your hypothesis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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