From Jackson - Social and Economic Networks p. 87 (link: http://press.princeton.edu/chapters/s4_8767.pdf p.12 in pdf):

(...) (T)he distribution of degrees of a node found by choosing a link uniformly at random from a network that has degree distribution P and then picking either one of the end nodes with equal probability is:

$\tilde{P}(d) = \frac{P(d) d}{ E(d) } $,

where $P(d)$ is the probability of a node having degree $d$, and $E(d)$ is the expected degree in the network.

Q1: How is this expression derived?

Q2: Is this probability the same as the probability of having degree $d$ conditional on having at least one link (i.e., $P(d|d\geq1)$ )? If not, why?

Thanks in advance. For those who prefer graph lingo: link=edge, node=vertex.


The probability of picking a certain node is the probability of picking one of its adjacent edges times the probability of choosing its end: $$\frac{1}{2}\frac{d}{e},$$ where $d$ is its degree of the node and $e$ the number of links.

The probability of choosing any node of degree $d$ is the sum of these probabilities: $$n(d) \frac{d}{2e},$$ where $n(d)$ is the number of nodes of degree $d$.

Now observe that $P(d) = n(d)/N$ and that $E(d) = 2e/N$, where $N$ is the number of nodes.

With regards to Q2, consider as a counter example a network with three nodes and two links. The probability of having degree 2 is 1/3, but the probability of choosing the node with degree 2 by this process is 1/2.

  • $\begingroup$ Thank you for a clear answer! With regards to Q2, this then not the same as the probability of having degree d conditional on having at least one edge? I noticed that for the Poisson distribution, these are the same, but I suppose this is not true in general? $\endgroup$ – user3218615 Mar 26 '15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.