Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I am new to graphs and am reading about modularity for my course work. One thing I don't understand is how and why the expected number of edges between $v$ and $w$ is $\dfrac{k_vk_w}{2m}$
Does anyone have a more intuitive / pictorial explanation because I have been searching on the internet for a few hours and still do not understand it at all.
The idea is that $k_v$, the degree of $v$ stands for the number of "half-edges" starting at $v$. Then, to make a full edge, you need to bind two half-edges in the graph. If you did it by picking half-edges uniformly, you would find that the probability of a randomly-picked edge being between $v$ and $w$ is $\frac{k_vk_w}{4m^2}+\frac{k_wk_v}{4m^2}=\frac{k_vk_w}{2m^2}$ because the probability of picking an half-edge of node $v$ is $\frac{k_v}{2m}$. Then, if $(X_i)_{i\leq m}$ is the $i$-th picked edge, and $S=\sum_{i=1}^m \mathbb{1}_{\{X_i=(v,w)\}}$ counts the number of edges between $v$ and $w$, then $\mathbb{E}(S)=m\times \frac{k_vk_w}{2m^2} =\frac{k_vk_w}{2m}$.
