Assortativity

The assortativity coefficient is the Pearson correlation coefficient of degree between pairs of linked nodes.[2] Positive values of r indicate a correlation between nodes of similar degree, while negative values indicate relationships between nodes of different degree. In general, r lies between −1 and 1. When r = 1, the network is said to have perfect assortative mixing patterns, when r = 0 the network is non-assortative, while at r = −1 the network is completely disassortative.

The assortativity coefficient is given by ${\displaystyle r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}}$. The term ${\displaystyle q_{k}}$ is the distribution of the remaining degree. This captures the number of edges leaving the node, other than the one that connects the pair. The distribution of this term is derived from the degree distribution ${\displaystyle p_{k}}$ as ${\displaystyle q_{k}={\frac {(k+1)p_{k+1}}{\sum _{j\geq 1}jp_{j}}}}$. Finally, ${\displaystyle e_{jk}}$ refers to the joint probability distribution of the remaining degrees of the two vertices. This quantity is symmetric on an undirected graph, and follows the sum rules ${\displaystyle \sum _{jk}{e_{jk}}=1\,}$ and ${\displaystyle \sum _{j}{e_{jk}}=q_{k}\,}$.

In a Directed graph, in-assortativity (${\displaystyle r({\text{in}},{\text{in}})}$) and out-assortativity (${\displaystyle r({\text{out}},{\text{out}})}$) measure the tendencies of nodes to connect with other nodes that have similar in and out degrees as themselves, respectively.[4] Extending this further, four types of assortativity can be considered (see[5]). Adopting the notation of that article, it is possible to define four metrics ${\displaystyle r({\text{in}},{\text{in}})}$, ${\displaystyle r({\text{in}},{\text{out}})}$, ${\displaystyle r({\text{out}},{\text{in}})}$, and ${\displaystyle r({\text{out}},{\text{out}})}$. Let ${\displaystyle (\alpha ,\beta )}$, be one of the in/out word pairs (e.g. ${\displaystyle (\alpha ,\beta )=({\text{out}},{\text{in}})}$). Let ${\displaystyle E}$ be the number of edges in the network. Suppose we label the edges of the network ${\displaystyle 1,\ldots ,E}$. Given edge ${\displaystyle i}$, let ${\displaystyle j_{i}^{\alpha }}$ be the ${\displaystyle \alpha }$-degree of the source (i.e. tail) node vertex of the edge, and ${\displaystyle k_{i}^{\beta }}$ be the ${\displaystyle \beta }$-degree of the target (i.e. head) node of edge ${\displaystyle i}$. We indicate average values with bars, so that ${\displaystyle {\bar {j^{\alpha }}}}$, and ${\displaystyle {\bar {k^{\beta }}}}$ are the average ${\displaystyle \alpha }$-degree of sources, and ${\displaystyle \beta }$-degree of targets, respectively; averages being taken over the edges of the network. Finally, we have

${\displaystyle r(\alpha ,\beta )={\frac {\sum _{i}(j_{i}^{\alpha }-{\bar {j^{\alpha }}})(k_{i}^{\beta }-{\bar {k^{\beta }}})}{{\sqrt {\sum _{i}(j_{i}^{\alpha }-{\bar {j^{\alpha }}})^{2}}}{\sqrt {\sum _{i}(k_{i}^{\beta }-{\bar {k^{\beta }}})^{2}}}}}.}$

Fig. 2: k_nn distribution for two real-world networks. The top network (a) is disassortative, since the slope is negative. On the other hand, (b) is assortative, since the slope is positive.[6]

Another means of capturing the degree correlation is by examining the properties of ${\displaystyle \langle k_{nn}\rangle }$, or the average degree of neighbors of a node with degree k.[7] This term is formally defined as: ${\displaystyle \langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)}}$, where ${\displaystyle P(k'|k)}$ is the conditional probability that an edge of node with degree k points to a node with degree k'. If this function is increasing, the network is assortative, since it shows that nodes of high degree connect, on average, to nodes of high degree. Alternatively, if the function is decreasing, the network is disassortative, since nodes of high degree tend to connect to nodes of lower degree. The function can be plotted on a graph (see Fig. 2) to depict the overall assortativity trend for a network.

In assortative networks, there could be nodes that are disassortative and vice versa. A local assortative measure[8] is required to identify such anomalies within networks. Local assortativity is defined as the contribution that each node makes to the network assortativity. Local assortativity in undirected networks is defined as,

${\displaystyle \rho ={\frac {j\ \left(j+1\right)\left({\overline {k}}-\ {\mu }_{q}\right)}{2M{\sigma }_{q}^{2}}}}$

Where ${\displaystyle j}$ is the excess degree of a particular node and ${\displaystyle {\overline {k}}}$ is the average excess degree of its neighbors and M is the number of links in the network.

Respectively, local assortativity for directed networks[4] is a node's contribution to the directed assortativity of a network. A node's contribution to the assortativity of a directed network ${\displaystyle r_{d}}$ is defined as, ${\displaystyle {\rho }_{d}=\ {\frac {{j_{out}}^{2}\left({\overline {k}}_{in}-\ {\mu }_{q}^{in}\right)+\ {j_{in}}^{2}\left({\overline {k}}_{out}-\ {\mu }_{q}^{out}\right)}{2\ M{\sigma }_{q}^{in}{\sigma }_{q}^{out}}}}$

Where ${\displaystyle j_{out}}$ is the out-degree of the node under consideration and ${\displaystyle j_{in}}$ is the in-degree, ${\displaystyle {\overline {k}}_{in}}$ is the average in-degree of its neighbors (to which node ${\displaystyle v}$} has an edge) and ${\displaystyle {\overline {k}}_{out}}$ is the average out-degree of its neighbors (from which node ${\displaystyle v}$ has an edge).${\displaystyle {\sigma }_{q}^{in}\ \neq 0}$,${\displaystyle \ {\ \sigma }_{q}^{out}\ \neq 0}$.

By including the scaling terms ${\displaystyle {\sigma }_{q}^{in}}$ and ${\displaystyle {\ \sigma }_{q}^{out}}$ , we ensure that the equation for local assortativity for a directed network satisfies the condition ${\displaystyle r_{d}=\ \sum _{i=1}^{N}{{\rho }_{d}}}$.

Further, based on whether the in-degree or out-degree distribution is considered, it is possible to define local in-assortativity and local out-assortativity as the respective local assortativity measures in a directed network.[4]