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

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

    • Since there are $k_i$ possible stubs for vertex $i$, the overall probability is:

  • 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$?

Mathematics Asked on November 12, 2021

1 Answers

One 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.

Answered by Wrzlprmft on November 12, 2021

Add your own answers!

Related Questions

Rule of inference. Is the argument valid?

2  Asked on February 5, 2021 by blue


Linear independence in $mathbb{Z}_2$ and $mathbb{R}$

1  Asked on February 4, 2021 by andrew-yuan


How to denote a FOR…LOOP in mathematics

1  Asked on February 3, 2021 by user3190686


Drawing numbers from an interval

1  Asked on February 3, 2021 by itsme


Projective bundle and blow up

0  Asked on February 3, 2021 by konoa


Ask a Question

Get help from others!

© 2021 All rights reserved.