Assortative mixing

Let $N$ be a network with $n$ nodes, each of which has a “type” belonging to some set $T$ . We say that $N$ is “assortatively mixed” if nodes tend to have the same types as their neighbors. For example, if $N$ is a social network and $T$ is a set of interests, then assortative mixing could arise because friends tend to share interests.

How can we measure the extent of assortative mixing in $N$ ? Newman (2003) suggests the “assortativity coefficient” $r = \frac{\sum_{t \in T} x_{t t} - \sum_{t \in T} y_{t}^{2}}{1 - \sum_{t \in T} y_{t}^{2}},$ where $x_{s t}$ is the proportion of edges joining nodes of type $s$ to nodes of type $t$ , and where $y_{t} = \sum_{s \in T} x_{s t}$ is the proportion of edges incident with nodes of type $t$ . The coefficient $r$ varies between -1 and 1, and takes larger values when $N$ is more assortatively mixed. We say that $N$ is “positively sorted” if $r > 0$ and “negatively sorted” if $r < 0$ .

We can interpret $r$ by thinking about the “mixing matrix” $X = (x_{s t})$ . The numerator of $r$ equals the sum of diagonal entries of $X$ minus what that sum would be if the distributions of entries across rows and columns were independent. The denominator of $r$ is a normalizing constant ensuring $| r | \leq 1$ . Thus $r$ indexes the frequency of within-type edges in $N$ relative to the frequency we would expect in a random network with the same proportion of edges incident with each type.

As an example, suppose $N$ is a realization of the planted partition model with $n_{1}$ nodes of type 1, $n_{2} = n - n_{1}$ nodes of type 2, and some proportion $p_{s t} = {\begin{cases} p & if s = t \\ q & otherwise \end{cases}$ of edges joining nodes of type $s$ to nodes of type $t$ . Then $N$ has assortativity coefficient $r = \frac{p^{2} (n_{1} - 1) (n_{2} - 1) - q^{2} n_{1} n_{2}}{p^{2} (n_{1} - 1) (n_{2} - 1) + p q (n_{1} (n_{1} - 1) + n_{2} (n_{2} - 1)) + q^{2} n_{1} n_{2}},$ which equals -1 if $p = 0$ and $q > 0$ (i.e., there are no within-type edges), and equals 1 if $p > 0$ and $q = 0$ (i.e., there are no between-type edges). If $p = q$ then $r = - \frac{1}{n - 1},$ which converges to zero from below as $n$ becomes large. Intuitively, if $p = q$ then within-type and between-type edges occur at the same rate, but the network is slightly negatively sorted because there are slightly fewer potential within-type edges than potential between-type edges.

If $n_{1} = n_{2}$ then $r = \frac{p^{2} (n - 2) - q^{2} n}{p^{2} (n - 2) + q^{2} n},$ which converges to $(p^{2} - q^{2}) / (p^{2} + q^{2})$ as $n$ becomes large. The figure below demonstrates this case with $n_{1} = n_{2} = 25$ . The network on the left has edge frequencies $(p, q) = (0.15, 0.02)$ and assortativity coefficient $r = 0.75$ ; the network on the right has edge frequencies $(p, q) = (0.02, 0.15)$ and assortativity coefficient $r = - 0.79$ . Both networks are drawn so that adjacent nodes are closer together. Nodes in the positively sorted network tend to have neighbors with the same type, while nodes in the negatively sorted network tend to have neighbors with a different type.

The assortativity coefficient $r$ can be used when $T$ is a set of categorical types. In contrast, if $T$ is set of scalar quantities then we can measure the extent of assortative mixing via the Pearson correlation coefficient $ρ = \frac{Cov (t_{i}, t_{j})}{\sqrt{Var (t_{i}) Var (t_{j})}},$ where $t_{i} \in T$ and $t_{j} \in T$ are the “types” of nodes $i$ and $j$ , and where (co)variances are computed with respect to the frequency at which nodes of type $t_{i}$ and $t_{j}$ are adjacent in the network.¹ To see how this works, let $A = (a_{i j})$ be the $n \times n$ adjacency matrix for $N$ and let $W = (w_{i j})$ be the $n \times n$ “weighting matrix” with entries $w_{i j} = \frac{a_{i j}}{| | A | |},$ where $| | A | |$ denotes the sum of elements in $A$ . Then the vector $t = (t_{1}, t_{2}, \dots, t_{n})$ of node types has mean $E [t] = s^{T} t,$ where $s = (s_{1}, s_{2}, \dots, s_{n})$ is the vector of row sums $s_{i} = \sum_{j = 1}^{n} w_{i j} .$ Intuitively, $s$ describes the probability mass function for the (marginal) distribution of node types. Treating $t_{i}$ and $t_{j}$ as draws from this distribution, we have $\begin{aligned} Cov (t_{i}, t_{j}) & = E [t_{i} t_{j}] - E [t_{i}] E [t_{j}] \\ = \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} t_{i} t_{j} - (s^{T} t) (s^{T} t) \\ = t^{T} W t - (s^{T} t)^{2} \end{aligned}$ and similarly $\begin{aligned} Var (t_{i}) & = E [t_{i}^{2}] - E [t_{i}]^{2} \\ = \sum_{i = 1}^{n} s_{i} t_{i}^{2} - (s^{T} t)^{2} \\ = t^{T} S t - (s^{T} t)^{2}, \end{aligned}$ where $S$ is the $n \times n$ matrix with principal diagonal equal to $s$ and off-diagonal entries equal to zero. Then $ρ = \frac{t^{T} W t - (s^{T} t)^{2}}{t^{T} S t - (s^{T} t)^{2}} .$ For example, if the nodes in $N$ are arranged such that $a_{i j} = {\begin{cases} 1 & if t_{i} = t_{j} \\ 0 & otherwise \end{cases}$ then $\begin{aligned} t^{T} W t & = \sum_{i = 1}^{n} \sum_{j = 1}^{n} w_{i j} t_{i} t_{j} \\ = \sum_{i = 1}^{n} t_{i}^{2} \sum_{j = 1}^{n} w_{i j} \\ = \sum_{i = 1}^{n} t_{i}^{2} s_{i} \\ = t^{T} S t \end{aligned}$ and so $ρ = 1$ —that is, if all adjacent nodes have the same scalar type then the coefficient $ρ$ obtains its maximum value of unity.

One common use of the correlation coefficient $ρ$ is to measure assortativity with respect to nodes’ degrees (see, e.g., Newman, 2002). For example, the left-hand network in the figure above has $ρ = 0.03$ : although nodes are sorted strongly by color, they are approximately unsorted by degree because the planted partition model from which the network is generated has no mechanism for connecting high-degree nodes. Performing a degree-preserving randomization of the network changes its assortativity with respect to nodes’ degrees by changing the joint distribution of those degrees across node pairs:

Numerical experimentation suggests $r = ρ$ whenever $| T | = 2$ , which I prove here. ↩︎