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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.