Probability of an edge in a random graph

Question

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.

If I am correct, when the graph is built with the configuration model, this probability is: $$ 1 - \left(1 - \frac{d_v}{2m-1}\right)^{d_u} $$ where $m$ denotes the total number of edges ($m = \frac{1}{2}\sum_{v\in V} d_v$).

Indeed, the wanted probability is one minus the probability that the link does not exist. This probability is the one that each of the $d_u$ stubs of $u$ are not paired with $v$. For each of these stubs, the probability that it is not linked to $v$ is one minus the probability that it is linked to $v$. And this is the probability to choose one of the $d_v$ stubs of $v$ among the $2\cdot m-1$ possible stubs. Right?

When the degrees are not too large, this value is close to $1-\frac{d_u d_v}{2m}$.

BUT the configuration model produces multigraphs, and so this is the probability that $u$ and $v$ are linked in a multigraph.

I guess the approximation holds for simple graphs too, because if the degrees are not too large the configuration model produces simple graphs.

But what about the exact probability?

Answer 1

As Jukka writes, exact solutions are unattainable (or uselessly complicated) except for very low degrees and special cases. An example of such a special case is regular graphs of degree $d$, where the probability of an edge is exactly $d/(n-1)$.

The asymptotic probability of an edge as $n\to\infty$ with the degree sequence being a function of $n$ has been solved for a variety of different cases. This is distributed over quite a few papers; I'll mention some.

B. D. McKay, Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combinatoria, 19A (1985) 15-26; for the case $d_{max}^4=o(E)$, $E$ being the number of edges.

B. D. McKay, Subgraphs of dense random graphs with specified degrees. Combinatorics, Probability and Computing, 20 (2011) 413-433; for degree approximately linear in $n$ and limited variation of degree.

M. Isaev and B. D. McKay, Complex martingales and asymptotic enumeration. Random Structures and Algorithms, 52 (2018) 617-661; for degree approximately linear in $n$ allowing much greater variation of degree.

A. Liebenau and N. C. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph; this covers the large gap between the first and second papers for when the degrees don't vary too much.

Some other cases like power-law degree sequences have also been done at least partly. The case of intermediate degree, large variation, is not done except in principle (there is a formula with multidimensional moments and big determinants).

Answer 2

Some observations, that are too long for a comment.

Obs 1. The proposed formula for the configuration model cannot be right, because it is not symmetric with respect to $d_u$ and $d_v$.

Obs 2. One has to be careful when specifying the "random" graph: what is the intended distribution? If uniform, uniform among what? I don't believe the configuration model generates multigraphs uniformly at random. If we specify three vertices $V=\{1,2,3\}$ and degree sequence $(2,2,2)$, it seems that the configuration model produces

1. with probability $1/15$ the graph with 3 loops
2. with probability $8/15$ the triangle
3. with probability $6/15$ some graph where one vertex has a loop, and the other two vertices have two edges between them. (There are $3$ such multigraphs, so each has probability $2/15$.) This is not uniform over the $5$ labelled multigraphs [that have the specified number of vertices and degree sequence], nor over the $3$ possible unlabeled multigraphs.

Obs 3. Continuing the case $n=3$ and degree sequence $(2,2,2)$. Take any two vertices, say, 1 and 2. They have degrees $2$ and $2$. The probability that an edge exists between 1 and 2 is:

• $10/15 = 2/3$ in the configuration model ($8/15$ from the triangle, plus $2/15$ from the graph that has one loop at vertex 3).
• $2/5$ if we choose uniformly at random from the $5$ possible multigraphs.
• but the proposed formula, if I understand it right, says $1-(1-2/5)^2 = 16/25$.

For the question on simple graphs, chosen uniformly from the graphs that have the required degree sequence, I believe exact formulas may be quite difficult, except in very small cases that can be solved exhaustively.

Answer 3

I think that the problem raised by Jukka Kohonen comes from the fact that there are several forms of labelling. In this paper by Fosdick et al. the authors make an interesting distinction between stub-labeled multigraphs and vertex-labeled multigraphs.

Usually people imply vertex-labeled multigraphs, as is the case of Jukka when asserting "I don't believe the configuration model generates multigraphs uniformly at random.". The configuration model produces uniformly at random stub-labeled (loopy) multigraphs, as discussed in the section 3 of the reference above (where I think it is described as Bollobas stub-matching method). In the example of the (2,2,2) sequence, the 15 graphs mentioned are different stub-labeled multigraphs.

Note also that a vertex-labeled graph is isomorphic to $ \prod _i d_i ! $ stub-labeled graphs, which may be useful to go from one enumeration to the other.

In anyway, I agree that the probability proposed in the original question is not correct in the context of the configuration model.