# Deriving the probability of a node (vertex) on the end of a random chosen link (edge) having degree d.

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.

## 1 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.

• 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? – user3218615 Mar 26 '15 at 23:04