What is the probability that two nodes are connected in a random graph?

Question

I have just started with the theory of random graphs. I have come across the following expression of the probability that two nodes $i$ and $j$ are connected where $k_i$ and $k_j$ are the respective node degrees and $m$ is the number of edges in the graph, according to Erdos and Renyi:

$$p_{ij}=\frac{k_ik_j}{2m-1}$$

According to my understanding, the probability should be the number of possible connections between $i$ and $j$ divided by the total number of possible connections in the graph. In that sense the numerator of the formula is obvious. Can any of you explain me the denominator or the formula as a whole?

I was consulting this lecture slides when I came across the formula in the 17th slide. The professor gave an explanation of the formula in this lecture at around 1:10:00 timestamp. However, I did not understand the concept clearly.

EDIT

I have tried to explain the expression in the following way with the help of this.

A stub of node $i$ can be connected to $2m-1$ other stubs. The probability of a stub of node $i$ being connected to one of $k_j$ stubs is: $$\frac{k_j}{2m-1}$$ The probability that $k_i$ stubs being connected to one of $k_j$ stubs is:

$$ \frac{\overbrace{k_j+\ldots+k_j}^{k_i-times}}{2m-1} = \frac{k_ik_j}{2m-1} $$

Answer 1

Some reflections. Just from my understanding here the degrees of the nodes are fixed and connected means "adjacent".

From the video let's call $S_i$ the stubs of $i$ and $S_j$ the stubs of $j$.

Now I guess one should make the approximation:

$P(i, j \ \text{connected}) \sim \sum_{s\in S_i}P(i, j \ \text{connected via stub } s)$

I think this is an approximation because the events are not disjoints. Two nodes may be connected via multiple stubs therefore the probabilities do not simply add. Now we consider that:

$P(i, j \ \text{connected via stub } s)=\frac{k_j}{\text{Total number of stubs -1}}$

( where $-1$ is there because we cannot connect a stub to itself ). Of course $\text{"Total number of stubs $-1$"}=2m-1$.

Putting everything together, and replacing $\sum_{s\in S_i} \rightarrow k_i$, we get at least the formula you proposed.

Answer 2

To add some more details to the existing answer: the formula $\frac{k_i k_j}{2m - 1}$ given describes the expected number of edges between vertex $i$ and vertex $j$: for each half-stub of vertex $i$, the probability of being connected to vertex $j$ is $\frac{k_j}{2m-1}$, and by linearity of expectation (i.e. summing over the half-stubs of vertex $i$), we obtain $\frac{k_i k_j}{2m-1}$.

Thus, this in fact is an upper bound for the probability that $i$ and $j$ are connected, since $p_{ij} = \mathbb{P}(i \sim j) = \mathbb{P}(\mathrm{Edges}(i, j) \geq 1) \leq \mathbb{E}[\mathrm{Edges}(i, j)] = \frac{k_i k_j}{2m - 1}$ by Markov's inequality.

Now in practice, this formula is probably true asymptotically, i.e. $p_{ij} = (1 + o(1)) \frac{k_i k_j}{2m - 1}$ (where we must make sense of what $n \to \infty$ means for the degree sequence). This is discussed more precisely in this answer.