11 Probability Generating Functions
Open the live notebook in Google Colab here.
In this lecture we’ll introduce a powerful tool for calculating network properties: probability generating functions.
Properties of probability generating functions
We note that the degree distribution and the probability generating function give two different mathematical representations of the same idea. The probability generating function is a power series representation of the degree distribution of \(K\). This is quite useful because the probability generating function is always a polynomial, and there is a lot of rich theory we can leverage.
Exercise: Suppose we have a network where we observe the following data.
| Node Degree | Percentage of Nodes with Given Degree |
|---|---|
| 0 | 12% |
| 1 | 20% |
| 2 | 58% |
| 3 | 10% |
What is the probability generating function \(g(z)\) associated with the degree distribution for this network?
Exercise: Suppose \(K\) is Poisson distributed with mean degree \(c\). What is the probability generating function for \(K\)?
Recall that the probability mass function a Poisson distribution with mean \(c\) is given by \(\frac{c^k e^{-c}}{k!}.\)
Exercise: What is the probability generating function for the exponential distribution of the form \[ p_k = (1-a)a^k, \quad 0<a<1 \,. \]
The examples above give a sense of how to calculate probability generating functions from known degree distributions. As the next theorem shows, we can also find the degree distribution from the probability generating function. We’ll prove this theorem in class.
Normalization and moments
The moments of a probability distribution are quantities that give us important information about the shape of the distribution. The \(m\)th moment of a probability distribution \(p_k\) is
\[ \langle k^m \rangle = \sum_{k=0}^\infty k^m p_k \,. \]
We recognize that moments have already shown up in several of our calculations thus far. For example, the zeroth moment of a degree distribution is always 1 since \(\sum_{k=0}^\infty p_k = 1\). The first moment \(\langle k \rangle\) is the expected value. The second moment showed up in our previous lecture when discussing the friendship paradox.
We can now see that generating functions give us a nice way to calculate moments. Using the definition of the probability generating function, we see that the zeroth moment is given by \[ g(1) = \sum_{k=0}^\infty p_k = 1 \,. \] If we take the derivative of the probability generating function with respect to \(z\) we obtain \[ g'(z) = \sum_{k=0}^\infty kp_kz^{k-1} \,. \] If we evaluate at \(z=1\), we get the first moment of \(p_k\): \[ g'(1) = \sum_{k=0}^\infty kp_k = \langle k \rangle\,. \]
Unfortunately, we can see that \(g''(1)\) will not exactly give us the second moment. A small modification, however, will do the trick.
\[\begin{align*} z \frac{d}{dz} \left(z \frac{dg}{dz}\right) &= z \frac{d}{dz} \left( \sum_{k=0}^\infty kp_kz^{k} \right) \\ &= z \sum_{k=0}^\infty k^2p_kz^{k-1} \\ &= \sum_{k=0}^\infty k^2p_kz^{k} \,. \end{align*}\]
Evaluating this quantity at \(z=1\) will give the second moment of the distribution: \[ \left( z \frac{d}{dz} \right)^2 g(z) \bigg \vert_{z=1} = \langle k^2 \rangle \,. \]
This strategy generalizes to higher-order moments as well.
Products of generating functions
In this section, we will show the following very useful property of generating functions.
Proof. Since \(K_i\) are i.i.d, the probability of drawing a particular set of values \(\mathcal{K} = \{k_1, k_2, \dots, k_m\}\) is \[ (p_{k_1}^{(1)})(p_{k_2}^{(2)}) \dots (p_{k_m}^{(m)}) = \prod_{i=1}^m p_{k_i}^{(i)} \,. \]
Next, we will calculate the probability \(\pi_s\) that the values add to a specific total \(s\). We do this by summing the product over all sets \(\mathcal{K}\) that add to \(s\).
\[ \pi_s = \sum_{k_1=0}^ \infty \dots \sum_{k_m=0}^ \infty \delta_{s, \sum_i k_i} \prod_{i=1}^m p_{k_i}^{(i)}\,. \] where \(\delta_{s, \sum_i k_i}\) is the Kronecker delta.
Now that we have this probability, we can write down a probability generating function for the distribution \(\pi_s\):
\[\begin{align*} h(z) &= \sum_{s=0}^\infty \pi_s z^s \\ &= \sum_{s=0}^\infty z^s \left[ \sum_{k_1=0}^\infty \dots \sum_{k_m=0}^\infty \delta_{s, \sum_i k_i} \prod_{i=1}^m p_{k_i}^{(i)} \right] \,. \end{align*}\]
Since \(s= \sum_i k_i\) for each case, we can rewrite the above as \[\begin{align*} h(z) &= \sum_{k_1=0}^\infty \dots \sum_{k_m=0}^\infty z^{\sum_i k_i}\prod_{i=1}^m p_{k_i}^{(i)} \\ &= \prod_{i=1}^m \sum_{k_i = 0}^\infty p_{k_i}^{(i)} z^{k_i} \,. \end{align*}\]
But, simplifying the notation on the indices, we see that \(\sum_{k_i = 0}^\infty p_{k_i}^{(i)} z^{k_i} = \sum_{k = 0}^\infty p_{k}^{(i)} z^{k} = g_i(z).\)
Thus, \[ h(z) = \prod_{i=1}^m g_i(z) \, \] as required.
This theorem has a very useful corollary in the case where all the random variables are drawn from the same distribution.
This corollary is useful when summing the degrees of \(m\) randomly chosen nodes from degree distribution \(p_k\).
Applications in configuration Models
Generating functions for excess degree distribution
Suppose we have a random graph \(G\) generated by a configuration model with degree distribution \(p_k\). That is, we know if we select a node \(u\) from \(G\) uniformly at random, it will have degree \(k\) with probability \(p_k,\) and the associated generating function is \(g_K(z)\).
We showed previously that the excess degree distribution is \(q_k = \frac{(k+1)p_{k+1}}{c},\) where \(c = \mathbb{E}(K)\) is the expected degree of the network. Here, we use the notation \(J\) for the random variable for excess degree of node \(u\), which means that \(J+1\) describes degree of a node reached by following an edge in \(G\). From here, we can write down the generating function \(g_J\) for the excess degree: \[\begin{align} g_J(z) &= \sum_{k=0}^\infty q_k z^k \\ &= \sum_{k=0}^\infty \frac{(k+1)p_{k+1}}{c} z^k \\ &= \frac{1}{c}\sum_{k=0}^\infty (k+1)p_{k+1}z^k \end{align}\]
If we compare the last line to the formula for \(g'(z)\) above, we see that this looks like the derivative of the generating function associated with \(p_k\) … cool! \[ g_J(z) = \frac{1}{c} g'_K(z) \,. \] We can make one final note: since \(c = \mathbb{E}(K) = g'_K(1)\), we can also write the denominator in terms of generating functions for \(K\): \[ g_J(z) = \frac{g'_K(z)}{g_K'(1)} \,. \]
Thus, we have a relationship between generating functions for the degree distribution and the excess degree distribution.
Number of second neighbors of a node
Now, suppose we have a configuration model with degree distribution \(p_k\) under the assumption that the network is locally tree-like. We know how to count the number of neighbors (that’s given by the degree). Let’s count the number of neighbors of neighbors — also called second neighbors — of a node.
What is the probability that a node has exactly \(k\) second neighbors in our configuration model? It depends on how many neighbors you have! If you have \(m\) neighbors, then this probability is \[ \mathbb{P}(m \text{ neighbors})\mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors}) \,. \]
Summing over all possible values of \(m\) gives us our expression: \[ \mathbb{P}(k \text{ second neighbors}) = \sum_{m=0}^\infty \mathbb{P}(m \text{ neighbors})\mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors}) \]
This calculation could be very hard! Let’s see how generating functions can help us perform this calculation. We will define the generating function for \(\mathbb{P}(k \text{ second neighbors})\) to be \(g_2(z).\) Then
\[\begin{align} g_2(z) &= \sum_{k=0}^\infty \mathbb{P}(k \text{ second neighbors}) z^k \\ &= \sum_{k=0}^\infty \sum_{m=0}^\infty p_m \mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors}) z^k \\ & = \sum_{m=0}^\infty p_m \sum_{k=0}^\infty \mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors}) z^k \,. \end{align}\]
However, notice that the quantity \(\mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors})\) is related to the excess degree: we are interested in the sum of the excess degrees of \(m\) neighbors. Using the multiplicative property we proved above, we know that this sum has the generating function \((g_J(z))^m\).
\[ \sum_{k=0}^\infty \mathbb{P}(k \text{ second neighbors} \vert m \text{ neighbors}) z^k = \prod_{i=1}^m\sum_{k=0}^\infty q_kz^k = (g_J(z))^m\,. \]
Substituting this expression into our calculation for \(g_2(z)\) yields \[ g_2(z) = \sum_{m=0}^\infty p_m (g_J(z))^m = g_K(g_J(z)) \,. \]
That is, the generating function for the distribution of second neighbors can be calculated from the generating functions of the degree and excess degree distribution!
We can now find the expected number of second neighbors by calculating \(g_2'(1)\). By the chain rule, \(g_2'(z) = g_K'(g_J(z))g_J'(z).\)
\[ g_2'(1) = g_K'(g_J(1))g_J'(1). \]
However, we know that \(g_J(1) = 1\), because it is the zeroth moment of the distribution. Thus, \[ \mathbb{E}(\text{second neighbors}) = g_K'(1)g_J'(1) = (\text{mean degree})(\text{mean excess degree})\,. \]
Referring to our previous calculations for these quantities, we have \[ \mathbb{E}(\text{second neighbors}) = \langle k \rangle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle} = \langle k^2 \rangle - \langle k \rangle \,. \]
References
© Heather Zinn Brooks and Phil Chodrow, 2024