Given a a large random network with a degree squence ${d_i} = {d_1, d_2, d_3,…,d_N}$ with $N>>1$ ($d_i$ is the degree of node $i$). The number of links of this network therefore is $L = \frac{1}{2}\sum_{i = 1}^N d_i$.
Show: The probability $p_{ij}$ that 2 nodes $i$, $j$ are connected is
$$
p_{ij} = \frac{d_i d_j}{2L}.
$$
I think with the right argumentation, this example should be rather easy, but even though i have tried to come up with one for quiet some time, i am still left with nothing. Can someone help me please?
Best Answer
The version of the statement that's exactly true is the following:
Here, we pick a random multigraph according to the configuration model. That is, initially there are $n$ isolated vertices and the $i^{\text{th}}$ vertices has $d_i$ half-edges out of it. We pick a uniformly random perfect matching between the half-edges, and connect matched half-edges together into an edge.
Then there are $d_id_j$ different ways to choose a half-edge out of vertex $i$ and a half-edge out of vertex $j$. The probability that they are joined together in the matching is $\frac1{2L-1}$: there are $2L$ half-edges total, so a half-edge has $2L-1$ others to be joined to, which are chosen uniformly.
Presumably, we want the approximation to hold with high probability as $n \to \infty$, and in the random graph rather than the random multigraph. (You have to be careful about what "$n \to \infty$" means here and what that does to the degree sequence, but we can generally work that out.)
Then, we need to show two things:
The first statement should hold provided that $\frac{d_i d_j}{2L} \to 0$ as $n \to \infty$. But if we further have $d_i d_j \ll L^{1/2}$, then it has an easy proof; the probability that there are two or more edges is asymptotically at most $\frac{(d_i d_j)^2}{(2L)^2}$, there are always at most $d_i d_j$ edges (actually, at most $\max\{d_i, d_j\}$), so the multi-edge case contributes at most $\frac{(d_i d_j)^3}{(2L)^2} \ll \frac{d_i d_j}{2L}$ to the expectation.
(If $d_id_j$ is larger than that, we can probably do a Poisson approximation.)
The second statement should always hold if $\Delta = \max\{d_1, d_2, \dots, d_n\}$ is sufficiently small: say, if $\Delta \le n^{1/6}$. In that case, the probabiity that the multigraph is simple is asymptotically $e^{-\gamma(\gamma+1)}$, where $$\gamma = \frac{\sum_i d_i (d_i - 1)}{2 \sum_i d_i},$$ and this does not significantly change if we condition on one edge being present (essentially, reducing both $d_i$ and $d_j$ by $1$).