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