I am trying to calculate the remaining degree distribution of an undirected graph.

Let $q_{j,k}$ be defined as the joint probability distribution of the remaining degrees of the two nodes at either end of a randomly chosen edge. Let $G=(V,E)$ be a graph with three nodes $V=(v_1,v_2,v_3)$, and two edges $E=(e_1,e_2)$ where $e_1=(v_1,v_2)$ and $e_2=(v_2,v_3)$.

In this paper it says that the remaining degree distribution is symmetric in its indices ($q_{j,k} = q_{k,j}$) for an undirected graph. Graph $G$ has two edges both connecting a node with remaining degrees 0 and 1. So according to that paper, the probabilities of finding such an edge would be $q_{0,1} = q_{1,0} = 1/2$. But this would surely imply that there is an equal chance of finding a directed edge connecting nodes with remaining degrees 0 and 1, and another directed in the opposite direction. Shouldn't either $q_{1,0} = 1$ or $q_{0,1} = 1$?

Can anyone explain why this isn't the case?

Its important to me because I'm calculating the Mutual Information of this distribution and you get a very different result depending on if the distribution is symmetric in its indices or erm triangular(?).

  • 1
    $\begingroup$ Can you explain how your $2\times 2$ matrices are supposed to be interpreted as distributions? Googling "remaining degree distribution" suggests that you're looking for a probability distribution, but how does your notation describe that? $\endgroup$ – Henning Makholm Jan 11 at 2:59
  • $\begingroup$ I have edited the question to make things more explicit. Does it make sense now? $\endgroup$ – Jonathan Jan 11 at 9:11
  • $\begingroup$ @HenningMakholm I have edited the question to make it even simpler and I reference a paper which should give some context. I hope it makes sense. $\endgroup$ – Jonathan Jan 12 at 13:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.