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