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.


1 Answer 1


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}$.

  • $\begingroup$ yes thank you. i had to try and derive the expression you had and i understand it now $\endgroup$
    – Kong
    May 14, 2018 at 20:10
  • 1
    $\begingroup$ It seems that your probability model is not the correct one, since it is possible that you sample a half-edge twice and bind it with itself. $\endgroup$
    – PSPACEhard
    Jul 9, 2018 at 6:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .