# Probability that two vertices are connected

Clauset, A., Newman, M.E.J., Moore, C., 2004. Finding community structure in very large networks. Phys. Rev. E 70, 066111. https://doi.org/10.1103/PhysRevE.70.066111

There is written that in an (what I think is undirected, but I might be wrong) network,

The probability of an edge existing between vertices $$v$$ and $$w$$ if connections are made at random but respecting vertex degrees is $$(k_v k_w)/2m$$

Where $$k_v$$ is the degree of node $$v$$, $$k_w$$ is the degree of node $$w$$, and $$m$$ is the number of edges in the graph (the sum of all the elements of the adjaciency matrix, divided by 2).

I don't understand where this formula comes from.

It looks to me that $$k_v k_m$$ is the number of possible ways in which the two nodes are connected, but then I don't understand why I have to divide by two times the number of edges in the network.

Can you enlighten me on the reasons behind this formula?

This is treated under Configuration model. Note that, there can be self-edges (i.e. it's not a loop-free graph) and there can also be multiple edges between two nodes. And, the formula above is a result of a series of assumptions and is not exactly correct.

Let's find the expected value of number of edges between vertices $$i$$ and $$j$$ and setup the mathematical model. We can think of vertices with half-edges (or stubs as wikipedia article mentions) attached to them. Each vertex, $$i$$, has $$k_i$$ half-edges attached. If an half-edge from vertex $$i$$ is connected another half-edge from vertex $$j$$, we have an edge between $$i$$ and $$j$$. If an half-edge from vertex $$i$$ is connected to another half-edge from the same vertex, we have a self-loop for vertex $$i$$.

Let $$X_{i}^l$$ be the binary random variable that represents the $$l$$-th half-edge of vertex $$i$$. It's $$1$$ if it's connected to vertex $$j$$ and $$0$$ otherwise. So, the expected value of $$X_{i}^l$$ is the probability of the half-edge $$l$$ of vertex $$i$$ connected to vertex $$j$$. There are $$2m-1$$ half-edges in total except this one and there are $$k_j$$ that are of interest. So, in a random setup, this probability is simply $$\mathbb E[X_i^l]=\frac{k_j}{2m-1}$$

The number of edges between the vertices $$i$$ and $$j$$ is just the sum of all $$X_i^l$$ for vertex $$i$$. So, the expected value of this is $$\mathbb E[\text{# edges between i and j}] = \mathbb E\left[\sum_{l=1}^{k_i} X_i^l\right]=\sum_{l=1}^{k_i} E[X_i^l]=\sum_{l=1}^{k_i} \frac{k_j}{2m-1}=\frac{k_ik_j}{2m-1}$$

This is not exactly the probability of vertices $$i$$ and $$j$$ being connected. It's the expected number of edges between these two and is expected to be close to the probability we want if the graph (and the number of edges) is large. In this case, it can also be approximated with $$2m-1\approx 2m$$ in the denominator. Because, if the graph is large, and say the degrees of the vertices is small compared to the overall number of edges, the overcounting by adding the probabilities of independent events (if this expected value is assumed to be the probability as per the original question) is getting smaller because for every half-edge there are so many other possibilities to connect to and the likelihood of selecting the same half-edge from vertex $$j$$ is small for two given half-edges of $$i$$.

### A Counter Example

Moreover, returning to the original question, one should not always expect to have $$k_ik_j\leq 2m$$ because the denominator is just a sum of the degrees and the numerator is the multiplication of some of them. Simply, in a graph with only two vertices, we can easily have $$k_1=4, k_2=4$$ and therefore $$2m=8$$, but the "probability" greater than $$1$$.

The actual probability in this case is $$1-\overbrace{3/7}^{\text{prob. of first stub of i connected to i}} \times \overbrace{1/5}^{\text{prob. of the remaining stub of i is connected to i}} = 32/35$$

But, the expected number of edges between the two vertices is $$k_ik_j/(2m-1) = 16 / 7$$, which is far greater.

### Reference

The treatment of this topic/subject is inside Section 13.2.1 of Newman's book, Networks: An Introduction.

Here is my thinking on this problem:

If you have $$m$$ randomly chosen edges in a graph, then you have $$2m$$ entries in the adjacency matrix. If we focus on the row of this matrix for vertex $$w$$, there is a $$\frac{k_w}{2m}$$ probability the non-diagonal entries will be 1. If there are $$k_v$$ entries in the column for vertex $$v$$, each of these has the same probability of being in the row for vertex $$w$$: $$P(v\&w) = k_v · \frac{k_w}{2m}$$

If I've overlooked a dependency or my counting protocol is under or over counting, I hope someone will let me know so this post can be adjusted accordingly.

• (+1) I think this is similar to the stub/half-edge analogy in the original explanation, but is an approximation to the expected value of the number of edges between the two vertices, not the exact probability. May 26, 2023 at 11:23