0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lulu Nov 22 '17 at 11:59
  • $\begingroup$ Yeah should be, it’s an example given to us and yes I think it’s indtended to be an approximation. $\endgroup$ – iqopi Nov 22 '17 at 12:06
  • $\begingroup$ 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? $\endgroup$ – lulu Nov 22 '17 at 12:09
  • $\begingroup$ 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. $\endgroup$ – iqopi Nov 22 '17 at 12:12
  • $\begingroup$ 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. $\endgroup$ – lulu Nov 22 '17 at 12:18
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.