Why are the probability and mean number of edges between two nodes in a network equal for large networks?

Question

Slide 18 in this lecture goes:

What is the probability of an edge between nodes $i$ and $j$?

There are $k_i$ stubs at node $i$ and $k_j$ at $j$

The probability that one of the $k_i$ stubs of node $i$ connects with one of the stubs of node $j$ is
$frac{k_j}{(2m-1)}$

Since there are $k_i$ possible stubs for vertex $i$, the overall probability is:
$$P_{ij}=frac{k_ik_j}{(2m-1)}congfrac{k_ik_j}{(2m)}$$

The above formula is the expected number of edges between nodes $i$ and $j$, but in the limit of large $m$, the probability and mean values become equal (why??)

Why do the probability and the mean values become equal in the limit of large $m$?

Wrzlprmft · Answer

The derivation of the equation ($P_{ij}=frac{k_ik_j}{(2m-1)}congfrac{k_ik_j}{(2m)}$) simply adds the probability of edges and thus computes the mean number of edges between the two nodes.
It ignores the event that there are two or more edges between nodes $i$ and $j$. The exact answer would be:
$$ P_{ij} = 1- left( 1- frac{k_j}{2m-1} right)^{k_j}. $$
However, for large $m$ and more precisely small $frac{k_j}{m}$, this distinction is miniscule as the probability that there are more than one edge between two nodes becomes very small.

Why are the probability and mean number of edges between two nodes in a network equal for large networks?

What is the probability of an edge between nodes $i$ and $j$?

One Answer

Add your own answers!

Ask a Question