Mixing patterns

Mixing patterns are a characteristic of an entire network, referring to the extent for nodes to connect to other similar or different nodes. Mixing, therefore, can be classified broadly as assortative or disassortative. Assortative mixing is the tendency for nodes to connect to like nodes, while disassortative mixing captures the opposite case in which very different nodes are connected.

Obviously, the particular node characteristics involved in the process of creating a link between a pair will shape a network's mixing patterns. For instance, in a sexual relationship network, one is likely to find a preponderance of male-female links, while in a friendship network male-male and female-female networks might prevail. Examining different sets of node characteristics thus may reveal interesting communities or other structural properties of the network. In principle there are two kinds of methods used to exploit these properties. One is based on analytical calculations by using generating function techniques. The other is numerical, and is based on Monte Carlo simulations for the graph generation.[1]

In a study on mixing patterns in networks, M.E.J. Newman starts by classifying the node characteristics into two categories. While the number of real-world node characteristics is virtually unlimited, they tend to fall under two headings: discrete and scalar/topological. The following sections define the differences between the categories and provide examples of each. For each category, the models of assortatively mixed networks introduced by Newman are discussed in brief.

Discrete characteristics of a node are categorical, nominal, or enumerative, and often qualitative. For instance, race, gender, and sexual orientation are commonly examined discrete characteristics.

To measure the mixing of a network on discrete characteristics, Newman[1] defines a quantity ${\displaystyle e_{ij}}$ to be the fraction of edges in a network that connect nodes of type i to type j (see Fig. 1). On an undirected network this quantity is symmetric in its indices ${\displaystyle e_{ij}=e_{ji}}$, while on directed ones it may be asymmetric. It satisfies the sum rules

${\displaystyle \sum _{ij}{e_{ij}=1},\quad \sum _{j}{e_{ij}=a_{i}},\quad \sum _{i}{e_{ij}=b_{j}}}$,

where ${\displaystyle a_{i}}$ and ${\displaystyle b_{i}}$ are the fractions of each type of an edge's end that is attached to nodes of type ${\displaystyle i}$. On undirected graphs, where there is no physical distinction between the ends of a link, i.e. the ends of edges are all of the same type, ${\displaystyle a_{i}=b_{i}}$.

Then, an assortativity coefficient, a measure of the similarity's or dissimilarity's strength between two nodes on a set of discrete characteristics may be defined as:

${\displaystyle r={\frac {\sum _{i}{e_{ii}}-\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_{i}b_{i}}}}}$

with

${\displaystyle r_{min}=-{\frac {\sum _{i}{a_{i}b_{i}}}{1-\sum _{i}{a_{i}b_{i}}}}}$

This formula yields ${\displaystyle r=0}$ when there's no assortative mixing, since ${\displaystyle e_{ij}=a_{i}b_{j}}$ in that case, and ${\displaystyle r=1}$ when the network is perfectly assortative. If the network is perfectly disassortative, i.e. every link connects two nodes of different types, then ${\displaystyle r=r_{min}}$, which lies in general in the range ${\displaystyle -1\leq r<0}$. This range for ${\displaystyle r_{min}}$ implies that a perfectly disassortative network is normally closer to a randomly mixed network than a perfectly assortative one is. When there are several different types of nodes, then random mixing will most often pair unlike nodes, so that the network appears to be mostly disassortative. Therefore, it is appropriate that the value ${\displaystyle r=0}$ for a random network should be closer to that for the perfectly disassortative network than for the perfectly assortative one.

The method of generating functions is based on the idea of figuring out the proper generating function for the distributions of our interest every time, and extract data related to the networks structure by differentiating them. Assuming that the degree distribution ${\displaystyle p_{k}^{(i)}}$ for nodes of type ${\displaystyle i}$ and the value of the matrix ${\displaystyle e_{ij}}$ (and hence, the values of ${\displaystyle a_{i}}$ and ${\displaystyle b_{i}}$) are known, then we may consider the ensemble of all graphs with the specified ${\displaystyle p_{k}^{(i)}}$ and ${\displaystyle e_{ij}}$ to yield collective (macroscopic) network characteristics. In principle, the generating function for ${\displaystyle p_{k}^{(i)}}$ and its first moment are given by ${\displaystyle G_{0}^{(i)}(x_{1},...,x_{n})=\sum _{k}p_{k}^{(i)}x^{k}}$, and ${\displaystyle G_{1}^{(i)}={\frac {1}{z_{i}}}{\frac {dG_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}}$, where ${\displaystyle x_{i}={\frac {\sum _{j}e_{ij}x_{j}}{\sum _{j}e_{ij}}}}$ the node of type ${\displaystyle i}$ (${\displaystyle r_{i}}$ in the number) and ${\displaystyle z_{i}}$ the mean degree for nodes of this type. Now we focus on the distributions that we're interested for.

The distribution of the total number of nodes reachable by following an edge that arrives at a node of type ${\displaystyle i}$ has a generating function ${\displaystyle H_{1}^{(i)}(x)=xG_{1}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Similarly, the distribution of the number of nodes reachable from a randomly chosen node of type ${\displaystyle i}$ is generated by ${\displaystyle H_{0}^{(i)}(x)=xG_{0}^{(i)}[H_{1}^{(1)}(x),...,H_{1}^{(n)}(x)]}$. Now we are in position to yield some of the network's properties. The mean number ${\displaystyle s_{i}}$ of nodes reachable from a node of type ${\displaystyle i}$ is

${\displaystyle s_{i}={\frac {dH_{0}^{(i)}}{dx}}{\Bigg |}_{x=1}=1+G_{0}^{(i)'}(1){\frac {\sum _{j}e_{ij}H_{1}^{(i)'}(1)}{\sum _{j}e_{ij}}}}$

Furthermore, if ${\displaystyle u_{i}}$ is the probability for a node of type ${\displaystyle i}$ (reached by following a randomly chosen link in the graph) not to belong to the giant cluster, then the overall fraction ${\displaystyle S}$ of nodes that compose this cluster is given by

${\displaystyle S=1-\sum _{i}{\frac {a_{i}}{z_{i}}}G_{0}^{(i)}(u_{1},...,u_{n})}$

The numerical simulations based on Monte Carlo techniques seem to agree with the analytical results yielded by the formulas described above.

Scalar characteristics of a node are those that are quantitative. They may be continuous or discrete ordinal variables like counts. Age is perhaps the simplest example, though intelligence and raw income are other obvious possibilities. Some topological features of the network may also be used for examining mixing by scalar properties. Specifically, the degree of a node is often a highly important feature in the mixing patterns of networks.[2] Topological scalar features are very useful, because unlike other measures, they are always available. They are sometimes used as a proxy for real-world "sociability".[1]

For measuring the assortativity of scalar variables, similar to the discrete case (see above) an assortativity coefficient can be defined. One can measure it using the standard Pearson Correlation, as Newman demonstrates.[1] In Fig. 2, for instance, a calculation of the Pearson Correlation Coefficient yields r = 0.574. This indicates a fairly strong association between the age of husbands and wives at the time of marriage.

An alternative coefficient can be computed for measuring the mixing by the degree of the nodes. Newman [1] derives the expression, which is found to be

${\displaystyle r={\frac {\sum _{jk}jk(e_{jk}-q_{j}q_{k})}{\sigma _{q}^{2}}}}$ for an undirected network. In this formula, if ${\displaystyle p_{k}}$ refers to the graph's degree distribution (i.e., the probability that a node has degree k) then ${\displaystyle q_{k}={\frac {(k+1)p_{k+1}}{z}}}$. This refers to the excess degree of a node, or the number of other edges aside from the currently examined one. The z refers to the average degree in the network, and ${\displaystyle \sigma _{q}}$ is the standard deviation of the distribution ${\displaystyle q_{k}}$. For a directed network the equivalent expression is ${\displaystyle r={\frac {\sum _{jk}jk(e_{jk}-q_{j}^{in}q_{k}^{out})}{\sigma _{in}\sigma _{out}}}}$.

This correlation is positive when nodes are assortative by degree, and negative when the network is disassortative. Thus, the measure captures an overall sense of the mixing patterns of a network. For a more in-depth analysis of this topic, see the article on assortativity.

The method of generating functions is still applicable for this case too, but the functions to be calculated are rarely calculable in closed form. Thus, numerical simulations seem to be the only way to yield results of some interest. The technique used is once again the Monte Carlo one. For the case of networks with a power-law degree-distribution ${\displaystyle p_{k}\sim k^{-\tau }}$, ${\displaystyle q_{k}}$ has a divergent mean, unless ${\displaystyle \tau >3}$, which rarely happens so.[3] Instead, the exponentially truncted power-law distribution ${\displaystyle p_{k}={\frac {k^{-\tau }\mathrm {e} ^{-k/\kappa }}{\mathrm {Li} _{\tau }(\mathrm {e} ^{-1/\kappa })}}\ \mathrm {for} \ k\geq 1}$ yields a distribution for the excess degree of the type ${\displaystyle q_{k}\sim (k+1)^{1-\tau }\mathrm {e} ^{-(k+1)/\kappa }}$. The results for this case are summarized below.

1) The position of the phase transition at which a giant cluster appears moves to higher values of ${\displaystyle \kappa }$ as the value of ${\displaystyle r}$ decreases. That is, the more assortative a network is, the lower the edge density threshold for the giant cluster's appearance will be.

2) The size of the giant cluster in the limit of large ${\displaystyle \kappa }$ is smaller for the assortatively mixed graph, than for the neutral and disassortative ones.

3) Assortative mixing in the network affects the network's robustness under node removal. For assortative networks, it is required to remove about ten times more than usual (usual means a neutral network) high-degree nodes to destroy the giant cluster, while the opposite is true for disassortative networks, i.e. they are more susceptible than neutral ones under removal of the high-degree nodes.

The fascinating result on the dependence of the network's robustness to its node mixing may be explained as follows. According to their definition, high-degree nodes in assortative networks tend to form a core group among them. Such a core group provides robustness to the network by concentrating all the obvious target nodes together in one portion of the graph. Removing these high-degree nodes is still one of the most effective ways to destroy network connectivity, but it is less effective (compared to neutral networks) because by removing them all from the same portion of the graph we fail to attack other portions. If these other portions are themselves percolating, then a giant cluster will persist even as the highest degree nodes vanish. On the other hand, the disassortatively mixed network is particularly susceptible to removal of high-degree nodes because these nodes are strewn far apart across the network, so that attacking them is like attacking all parts of the network at once.

A common application of mixing patterns is the study of disease transmission. For instance, many studies have used mixing to study the spread of HIV/AIDS and other contagious diseases.[4][5][6] These articles find a strong connection between Mixing patterns and the rate of disease spread. The findings can also be used to model real-world network growth, as in,[7] or find communities within networks.