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.
Best Answer
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.