# Probability that 2 nodes are connected in a random, large network

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?

• Is this true? If, say, $d_i=N-1$ then $p_{ij}=1$ for all choices of $j\neq i$, but that doesn't seem to be consistent with your formula. Am I misunderstanding? Or was your formula intended to be an approximation of some sort? – lulu Nov 22 '17 at 11:59
• Yeah should be, it’s an example given to us and yes I think it’s indtended to be an approximation. – iqopi Nov 22 '17 at 12:06
• Well, do you agree that my example is a counterexample to the result? Granted, in a large random graph it is improbable that a node has valence $N-1$ but...well, then your quantifiers are confusing. Do you fix a degree sequence and then look at a random graph with that sequence? And, if so, what sort of approximation is intended? – lulu Nov 22 '17 at 12:09
• I think the result of your counterexample is $(N-1)/N \approx 1$ for $N>>1$, so i think this is in the range of the approximation. I don't really know what kind of approximation it should be, since it isn't given in the example. I think anything remotely correct would be enought for this example. – iqopi Nov 22 '17 at 12:12
• Well...that calculation doesn't look right. $2L$ should be about $\frac {N^2}2$, surely. In any case, I think I don't understand the question. Perhaps I am missing something. I suggest you edit your post to, at least, indicate that you are looking for an approximate answer and, if possible, to say what sort of approximation you seek. – lulu Nov 22 '17 at 12:18

## 1 Answer

The version of the statement that's exactly true is the following:

In a random multigraph with degree sequence $(d_1, d_2, \dots, d_n)$, the expected number of edges between vertices $i$ and $j$ is $$\frac{d_i d_j}{2L-1}.$$

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:

1. The expected number of edges between $i$ and $j$ is asymptotically equal to the probability that there is an edge (in the configuration model).
2. Having an edge between $i$ and $j$ does not significantly impact the probability that the multigraph is simple.

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$).