Proving Assortativity r from Symmetric Binomial Distribution
Consider the symmetric binomial form given by the equation:
$$e_{jk} = N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j$$
where $p+q=1$, $\alpha > 0$, and $N = \frac{1}{2}(1-e^{-1/\alpha})$ is a normalizing constant. Here, $e_{jk}$ represents the joint probability distribution of the remaining degrees of the two vertices at either end of a randomly chosen edge.
Let's define the following terms:
$e_{jk}$: Joint probability distribution of the remaining degrees of the two vertices at either end of a randomly chosen edge.
$e_j$: The marginal probability distribution of the remaining degree of one vertex at the end of a randomly chosen edge, given by summing $e_{jk}$ over all possible values of $k$.
$p_k$: Binomial probability distribution of the degrees of vertices in the graph, representing the distribution of degrees for a vertex at one end of an edge.
$q_k$: Distribution of the remaining degrees reached by following a randomly chosen edge to a vertex with degree $k$.
$q_j$: Distribution of the remaining degrees reached by following a randomly chosen edge from a vertex with degree $j$, given by summing $e_{jk}$ over all possible values of $k$.
This distribution is chosen for analytic tractability, although its behavior is also quite natural: the distribution of the sum $j+k$ of the degrees at the ends of an edge falls off as a simple exponential, while that sum is distributed between the two ends binomially, with the parameter $p$ controlling the assortative mixing.
$$q_k = \frac{(k+1)p_{k+1}}{\sum_j jp_j}$$ $$e_j = \sum_{k} e_{jk}$$ $$\sum_{jk} e_{jk} = 1$$ $$\sum_{j} e_{jk} = q_k$$ $$q_k = \sum_{j} e_{jk}$$
$r$ is defined as:
$$r = \frac{1}{2\sigma_q^2}\sum_{jk} jke_{jk} - q_j q_k$$
where $\sigma_q^2 = \sum_k k^2 q_k - (\sum_k k q_k)^2$ is the variance of the distribution $q_k$.
Prove that:
$$r = \frac{8pq - 1}{2e^{1/\alpha} - 1} - (2p - q)^2$$
To prove the expression for $r$, we need to calculate each component:
Calculate $\sigma_q^2$: \begin{align*} $\sigma_q^2 &= \sum_k k^2 q_k - \left(\sum_k k q_k\right)^2 \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\sum_k k \frac{(k+1)p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k(k+1)p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \sum_k \frac{k^3 p_{k+1}}{\sum_j jp_j} - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \frac{\sum_k k^3 p_{k+1}}{\sum_j jp_j} - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \frac{\sum_k k^3 p_{k+1}}{\sum_j jp_j} - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \frac{\sum_k k^3 p_{k+1}}{\sum_j jp_j} - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \frac{\sum_k k^3 p_{k+1}}{\sum_j jp_j} - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \end{align*}
Calculate $r$: \begin{align*} r &= \frac{1}{2\sigma_q^2}\sum_{jk} jke_{jk} - q_j q_k \\ &= \frac{1}{2\sigma_q^2}\left(\sum_{jk} jke_{jk} - \sum_{jk} jk e_{jk}\right) \\ &= \frac{1}{2\sigma_q^2}\left(\sum_{jk} jk (e_{jk} - e_{jk})\right) \\ &= \frac{1}{2\sigma_q^2}\left(\sum_{jk} jk \left(N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j - N \binom{j+k}{k} p^k q^j - \binom{j+k}{j} p^j q^k\right)\right) \\ &= \frac{1}{2\sigma_q^2}\left(\sum_{jk} jk (N \binom{j+k}{j} p^j q^k - N \binom{j+k}{k} p^k q^j)\right) \\ &= \frac{1}{2\sigma_q^2}\left(N \sum_{jk} jk (\binom{j+k}{j} p^j q^k - \binom{j+k}{k} p^k q^j)\right) \end{align*}
Further simplification is required to match the provided expression for $r$. Let me continue with that simplification.
Continuing from where we left off:
\begin{align*} r &= \frac{1}{2\sigma_q^2}\left(N \sum_{jk} jk (\binom{j+k}{j} p^j q^k - \binom{j+k}{k} p^k q^j)\right) \\ &= \frac{N}{2\sigma_q^2}\left(\sum_{jk} jk \left(\binom{j+k}{j} p^j q^k - \binom{j+k}{k} p^k q^j\right)\right) \end{align*}
We can express $jk$ as a single summation index $n = j + k$:
\begin{align*} r &= \frac{N}{2\sigma_q^2}\left(\sum_{n=0}^{\infty} \sum_{j=0}^{n} jk \left(\binom{n}{j} p^j q^k - \binom{n}{k} p^k q^j\right)\right) \end{align*}
Since $\binom{n}{j} = \binom{n}{n-j}$, we can rewrite the above expression as:
\begin{align*} r &= \frac{N}{2\sigma_q^2}\left(\sum_{n=0}^{\infty} \sum_{j=0}^{n} \left(jk \binom{n}{j} p^j q^k - jk \binom{n}{n-j} p^k q^j\right)\right) \end{align*}
Then, we can rewrite the $jk$ term using the derivative of a product:
\begin{align*} r &= \frac{N}{2\sigma_q^2}\left(\sum_{n=0}^{\infty} \sum_{j=0}^{n} \left(j\frac{\partial}{\partial p}(p^j) q^k - k\frac{\partial}{\partial q}(q^k) p^j\right) \binom{n}{j} \right) \end{align*}
Now, let's focus on simplifying the summation.
We'll first simplify the expression inside the summation:
\begin{align*} j\frac{\partial}{\partial p}(p^j) &= j \cdot jp^{j-1} = jp^j \\ k\frac{\partial}{\partial q}(q^k) &= k \cdot kq^{k-1} = kq^k \end{align*}
Substituting these into the expression for $r$:
\begin{align*} r &= \frac{N}{2\sigma_q^2}\left(\sum_{n=0}^{\infty} \sum_{j=0}^{n} \left(jp^j q^k - kq^k p^j\right) \binom{n}{j} \right) \\ &= \frac{N}{2\sigma_q^2}\left(\sum_{n=0}^{\infty} \sum_{j=0}^{n} \left(jp^j q^k - kq^k p^j\right) \binom{n}{j} \right) \end{align*}
Now, we need to evaluate the double sum. Let's split it into two parts:
\begin{align*} \text{First part: } & \sum_{n=0}^{\infty} \sum_{j=0}^{n} jp^j q^k \binom{n}{j} \\ \text{Second part: } & \sum_{n=0}^{\infty} \sum_{j=0}^{n} kq^k p^j \binom{n}{j} \end{align*}
We'll evaluate each part separately. Let's start with the first part.
To evaluate the first part:
\begin{align*} \sum_{n=0}^{\infty} \sum_{j=0}^{n} jp^j q^k \binom{n}{j} &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} jp^j q^k \frac{n!}{j!(n-j)!} \\ &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{(j-1)!(n-j)!} p^j q^k \end{align*}
We can rewrite this sum using the binomial expansion:
\begin{align*} \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{(j-1)!(n-j)!} p^j q^k &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{j!(n-j)!} p^j q^k + \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{j!(n-j-1)!} p^j q^k \\ &= \sum_{n=0}^{\infty} (p+q)^n q^k + \sum_{n=0}^{\infty} (p+q)^{n+1} p q^k \\ &= \sum_{n=0}^{\infty} (p+q)^n q^k + pq \sum_{n=0}^{\infty} (p+q)^{n+1} q^k \\ &= \frac{q^k}{1-(p+q)} + pq \frac{q^k}{1-(p+q)} \\ &= \frac{q^k}{1-p} + pq \frac{q^k}{1-p} \\ &= \frac{q^k + pq^k}{1-p} \end{align*}
Now, let's evaluate the second part.
To evaluate the second part:
\begin{align*} \sum_{n=0}^{\infty} \sum_{j=0}^{n} kq^k p^j \binom{n}{j} &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} kq^k p^j \frac{n!}{j!(n-j)!} \\ &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{(j-1)!(n-j)!} q^k p^j \end{align*}
Similar to the first part, we can rewrite this sum using the binomial expansion:
\begin{align*} \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{(j-1)!(n-j)!} q^k p^j &= \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{j!(n-j)!} q^k p^j + \sum_{n=0}^{\infty} \sum_{j=0}^{n} \frac{n!}{j!(n-j-1)!} q^k p^j \\ &= \sum_{n=0}^{\infty} (p+q)^n q^k + \sum_{n=0}^{\infty} (p+q)^{n+1} q^k \\ &= \frac{q^k}{1-(p+q)} + \frac{q^k}{1-(p+q)} \\ &= \frac{q^k}{1-p} \end{align*}
Now, we can rewrite $r$ using these results:
\begin{align*} r &= \frac{N}{2\sigma_q^2}\left(\left(\frac{q^k + pq^k}{1-p}\right) - \left(\frac{q^k}{1-p}\right)\right) \\ &= \frac{N}{2\sigma_q^2}\left(pq^k\right) \\ &= \frac{N}{2\sigma_q^2}pq^k \end{align*}
Now, let's substitute $\sigma_q^2$ back into the expression for $r$ and simplify.
Substituting $\sigma_q^2$ into the expression for $r$:
\begin{align*} r &= \frac{N}{2\sigma_q^2}pq^k \\ &= \frac{N}{2}\frac{pq^k}{\sum_k k^2 q_k - \left(\sum_k k q_k\right)^2} \\ &= \frac{N}{2}\frac{pq^k}{\sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\sum_k k \frac{(k+1)p_{k+1}}{\sum_j jp_j}\right)^2} \\ &= \frac{N}{2}\frac{pq^k}{\sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2} \\ &= \frac{N}{2}\frac{pq^k}{\sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2} \\ &= \frac{N}{2}\frac{pq^k}{\sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2} \end{align*}
Now, we need to simplify the denominator and then further simplify the expression for $r$. Let's continue with that.
To simplify the denominator, let's first focus on the terms involving $p_{k+1}$:
\begin{align*} \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) \\ \end{align*}
We can see that there's a common factor of $p_{k+1}$ in each term. Let's factor that out:
\begin{align*} \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) &= \frac{1}{\sum_j jp_j} \sum_k k^2 (k+1)p_{k+1} \\ &= \frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} \end{align*}
Now, let's deal with the terms involving $p_k$:
\begin{align*} \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 &= \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \end{align*}
Now, let's substitute these expressions back into the denominator and simplify $r$.
Substituting the expressions for the terms involving $p_{k+1}$ and $p_k$ back into the denominator:
\begin{align*} \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 &= \frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \left(\frac{\sum_k k^2 p_k}{\sum_j jp_j}\right)^2 \\ &= \frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \left(\frac{\left(\sum_k k p_k\right)^2}{\left(\sum_j jp_j\right)^2}\right) \end{align*}
Now, let's substitute this expression back into $r$ and simplify:
\begin{align*} r &= \frac{N}{2}\frac{pq^k}{\frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \left(\frac{\left(\sum_k k p_k\right)^2}{\left(\sum_j jp_j\right)^2}\right)} \\ &= \frac{N}{2}\frac{pq^k}{\frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \frac{\left(\sum_k k p_k\right)^2}{\left(\sum_j jp_j\right)^2}} \end{align*}
We need to further simplify this expression to match the provided expression for $r$. Let's continue simplifying.
To simplify further, let's denote:
$$\mu_q = \sum_k kp_k$$
Then, rewrite the expression for $r$:
\begin{align*} r &= \frac{Npq^k}{2\left(\frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \frac{\mu_q^2}{\left(\sum_j jp_j\right)^2}\right)} \\ &= \frac{Npq^k}{2\left(\frac{1}{\mu_q} \sum_k k^3 \frac{(k+1)p_{k+1}}{\sum_j jp_j} - \frac{\mu_q^2}{\mu_q^2}\right)} \\ &= \frac{Npq^k}{2\left(\frac{1}{\mu_q} \sum_k k^3 \frac{(k+1)p_{k+1}}{\sum_j jp_j} - 1\right)} \end{align*}
Now, let's rewrite the numerator and denominator in terms of $q_k$:
\begin{align*} pq^k &= p\frac{(k+1)p_{k+1}}{\sum_j jp_j} \\ &= \frac{(k+1)p_{k+1}}{\sum_j jp_j} \\ &= q_k \end{align*}
Thus, the numerator $pq^k$ simplifies to $q_k$. For the denominator, we have:
\begin{align*} \frac{1}{\mu_q} \sum_k k^3 \frac{(k+1)p_{k+1}}{\sum_j jp_j} &= \frac{1}{\mu_q} \sum_k k^3 q_k \\ &= \frac{\sum_k k^3 q_k}{\mu_q} \end{align*}
Now, substituting these back into the expression for $r$:
\begin{align*} r &= \frac{N}{2}\frac{q_k}{\frac{\sum_k k^3 q_k}{\mu_q} - 1} \\ &= \frac{Nq_k\mu_q}{2\left(\sum_k k^3 q_k - \mu_q\right)} \end{align*}
We can recognize the numerator as the first moment of $q_k$, and the denominator as the third central moment of $q_k$. Let's denote these as $\mu_1$ and $\mu_3$, respectively:
$$\mu_1 = \mu_q, \quad \mu_3 = \sum_k k^3 q_k - \mu_q$$
Then, we have:
$$r = \frac{N\mu_1}{2\mu_3}$$
Let's recall the expressions for $\mu_1$ and $\mu_3$:
$$\mu_1 = \sum_k kp_k = \sum_k kq_k$$ $$\mu_3 = \sum_k k^3 q_k - \mu_q$$
Now, let's simplify $r$ using these expressions.
Recalling the expressions for $\mu_1$ and $\mu_3$:
$$\mu_1 = \sum_k kq_k$$ $$\mu_3 = \sum_k k^3 q_k - \mu_q$$
We can express $\mu_q$ in terms of $\mu_1$:
$$\mu_q = \mu_1$$
Substituting these into the expression for $r$:
\begin{align*} r &= \frac{N\mu_1}{2(\mu_3)} \\ &= \frac{N\mu_q}{2\left(\sum_k k^3 q_k - \mu_q\right)} \\ &= \frac{N\mu_q}{2\left(\sum_k k^3 q_k - \mu_1\right)} \end{align*}
Now, let's recall the definition of assortativity coefficient $r$:
$$r = \frac{1}{2\sigma_q^2}\sum_{jk} jke_{jk} - q_j q_k$$
And the expression for $N$:
$$N = \frac{1}{2}(1-e^{-1/\alpha})$$
We need to show that $r$ can be expressed as:
$$r = \frac{8pq - 1}{2e^{1/\alpha} - 1} - (2p - q)^2$$
We'll start by calculating the terms in the expression for $r$.
Let's calculate the terms in the expression for $r$:
\begin{align*} \sigma_q^2 &= \sum_k k^2 q_k - \left(\sum_k k q_k\right)^2 \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\sum_k k \frac{(k+1)p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \sum_k k^2 \left(\frac{(k+1)p_{k+1}}{\sum_j jp_j}\right) - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \end{align*}
\begin{align*} q_j &= \sum_k e_{jk} \\ &= \sum_k \left(N \binom{j+k}{j} p^j q^k + \binom{j+k}{k} p^k q^j\right) \\ &= N \sum_k \binom{j+k}{j} p^j q^k + \sum_k \binom{j+k}{k} p^k q^j \end{align*}
We'll need to simplify these expressions further and then compute $r$. Let's continue.
To simplify the expressions further, let's first calculate $\sigma_q^2$:
\begin{align*} \sigma_q^2 &= \frac{1}{\sum_j jp_j} \sum_k k^3 p_{k+1} - \left(\frac{\sum_k k^2 p_{k+1}}{\sum_j jp_j}\right)^2 \\ &= \frac{1}{\mu_1} \left(\sum_k k^3 p_{k+1} - \frac{\left(\sum_k k^2 p_{k+1}\right)^2}{\mu_1^2}\right) \end{align*}
Now, let's calculate $q_j$:
\begin{align*} q_j &= N \sum_k \binom{j+k}{j} p^j q^k + \sum_k \binom{j+k}{k} p^k q^j \\ &= N \sum_k \frac{(j+k)!}{j!k!} p^j q^k + \sum_k \frac{(j+k)!}{j!k!} p^k q^j \\ &= N \sum_k \frac{(j+k)!}{j!k!} p^j q^k + \sum_k \frac{(j+k)!}{j!k!} p^k q^j \end{align*}
We need to further simplify these expressions to compute $r$. Let's continue with that.
To further simplify the expressions, let's denote:
$$ \text{First term in } q_j = Q_1 $$ $$ \text{Second term in } q_j = Q_2 $$
We'll start by calculating $Q_1$:
\begin{align*} Q_1 &= N \sum_k \frac{(j+k)!}{j!k!} p^j q^k \\ &= N \sum_k \frac{(j+k)(j+k-1)\dots(j+1)}{k!} p^j q^k \\ &= N \sum_k \frac{(j+k)!}{k!j!} p^j q^k \\ &= N \sum_k \binom{j+k}{k} p^j q^k \end{align*}
And now, let's compute $Q_2$:
\begin{align*} Q_2 &= \sum_k \frac{(j+k)!}{j!k!} p^k q^j \\ &= \sum_k \frac{(j+k)(j+k-1)\dots(k+1)}{j!} p^k q^j \\ &= \sum_k \frac{(j+k)!}{j!k!} p^k q^j \\ &= \sum_k \binom{j+k}{j} p^k q^j \end{align*}
Now, let's substitute these back into the expression for $q_j$ and further simplify.
Substituting the expressions for $Q_1$ and $Q_2$ back into the expression for $q_j$:
$$q_j = N Q_1 + Q_2$$
We have:
$$q_j = N \sum_k \binom{j+k}{k} p^j q^k + \sum_k \binom{j+k}{j} p^k q^j$$
This can be simplified as:
$$q_j = N \sum_k \binom{j+k}{k} p^j q^k + \sum_k \binom{j+k}{j} p^k q^j$$ $$q_j = N \sum_k \binom{j+k}{j} p^j q^k + \sum_k \binom{j+k}{j} p^k q^j$$ $$q_j = \sum_k \binom{j+k}{j} (Np^j q^k + p^k q^j)$$
Now, let's express $N$ using the given formula:
$$N = \frac{1}{2}(1-e^{-1/\alpha})$$
We'll substitute this expression for $N$ back into $q_j$. Let's continue with that.
Substituting the expression for $N$ into $q_j$:
$$q_j = \sum_k \binom{j+k}{j} \left(\frac{1}{2}(1-e^{-1/\alpha})p^j q^k + p^k q^j\right)$$
This can be further simplified:
$$q_j = \frac{1}{2} \sum_k \binom{j+k}{j} (1-e^{-1/\alpha})p^j q^k + \sum_k \binom{j+k}{j} p^k q^j$$