Assortativity

{{Short description|Tendency for similar nodes to be connected}} {{Network Science}} '''Assortativity''', or assortative mixing, is a preference for a network's nodes to attach to others that are similar in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree.<ref name=pre>{{cite journal | last=Newman | first=M. E. J. | title=Mixing patterns in networks | journal=Physical Review E | volume=67 | issue=2 | date=27 February 2003 | issn=1063-651X | doi=10.1103/physreve.67.026126 | article-number=026126| pmid=12636767 | arxiv=cond-mat/0209450 | bibcode=2003PhRvE..67b6126N | s2cid=15186389 }}</ref> The addition of this characteristic to network models more closely approximates the behaviors of many real world networks.

Correlations between nodes of similar degree are often found in the mixing patterns of many observable networks. For instance, in social networks, nodes tend to be connected with other nodes with similar degree values. This tendency is referred to as assortative mixing, or ''assortativity''. On the other hand, technological and biological networks typically show disassortative mixing, or ''disassortativity'', as high degree nodes tend to attach to low degree nodes.<ref name=amn>{{cite journal | last=Newman | first=M. E. J. | title=Assortative Mixing in Networks | journal=Physical Review Letters | volume=89 | issue=20 | date=28 October 2002 | issn=0031-9007 | doi=10.1103/physrevlett.89.208701 | article-number=208701 | pmid=12443515| arxiv=cond-mat/0205405 | bibcode=2002PhRvL..89t8701N | s2cid=1574486 }}</ref>

==Measurement==

[[Image:Scale-free networks for different degrees of assortativity.jpg|thumb|180px|right|'''Fig. 1:''' Scale-free networks for different degrees of assortativity: (a) A = 0 (uncorrelated network), (b) ''A'' = 0.26, (c) ''A'' = 0.43, where ''A'' indicates ''r'' (the ''assortativity coefficient'', as defined in this sub-section).<ref name=un>{{cite journal|first1=R.|last1=Xulvi-Brunet|first2=I.M.|last2=Sokolov|title=Changing correlations in networks: assortativity and dissortativity|journal=Acta Physica Polonica B|volume=36|issue=5|page=1431|year=2005|bibcode=2005AcPPB..36.1431X|url=https://www.actaphys.uj.edu.pl/fulltext?series=Reg&vol=36&page=1431|access-date=2019-08-15|archive-date=2021-05-09|archive-url=https://web.archive.org/web/20210509155602/https://www.actaphys.uj.edu.pl/fulltext?series=Reg&vol=36&page=1431|url-status=live}}</ref>]]

Assortativity is often operationalized as a correlation between two nodes. However, there are several ways to capture such a correlation. The two most prominent measures are the ''assortativity coefficient'' and the ''neighbor connectivity''. These measures are outlined in more detail below.

===Assortativity coefficient===

The ''assortativity coefficient'' is the Pearson correlation coefficient of degree between pairs of linked nodes.<ref name=amn /> Positive values of <math>r</math> indicate a correlation between nodes of similar degree, while negative values indicate relationships between nodes of different degree. In general, <math>r</math> lies between <math>-1</math> and <math>1</math>. When <math>r = 1</math>, the network is said to have perfect assortative mixing patterns, when <math>r = 0</math> the network is non-assortative, while at <math>r = -1</math> the network is completely disassortative.

For undirected networks, the assortativity coefficient can be written as

:<math>r = \frac{\sum_{j,k} jk\,\bigl(e_{jk} - q_j q_k \bigr)}{\sigma_q^2}</math>.

In this expression, the indices <math>j</math> and <math>k</math> denote possible values of the ''remaining degree'', which is defined as the degree of a node minus one (i.e., the number of edges leaving a node other than the edge currently under consideration).

The quantity <math>q_k</math> is the probability that a randomly chosen end of an edge is attached to a node with remaining degree <math>k</math>. Because nodes with higher degree contribute proportionally more edge ends, <math>q_k</math> is derived from the degree distribution <math>p_k</math> as

:<math>q_k = \frac{(k+1)p_{k+1}}{\sum_{j} j\,p_j}</math>.

The term <math>e_{jk}</math> is the joint probability distribution of the remaining degrees at the two ends of a randomly chosen edge. It is obtained by examining all edges in the network, counting how often the pair <math>(j,k)</math> of remaining degrees occurs, and normalizing these counts so that

:<math>\sum_{j,k} e_{jk} = 1</math>.

By construction, the marginals of <math>e_{jk}</math> reproduce the distribution <math>q_k</math>

:<math>\sum_j e_{jk} = q_k</math>.

With these definitions, the expression above is exactly the Pearson correlation coefficient of the remaining degrees at the endpoints of edges.

In a directed graph, in-assortativity (<math>r( \text{in}, \text{in})</math>) and out-assortativity (<math>r( \text{out}, \text{out})</math>) measure the tendencies of nodes to connect with other nodes that have similar in and out degrees as themselves, respectively.<ref name=ino>{{cite journal|last1= Piraveenan |first1= M. |last2= Prokopenko |first2= M. |last3= Zomaya |first3= A.Y. |title= Assortative mixing in directed biological networks |journal= IEEE/ACM Transactions on Computational Biology and Bioinformatics |year= 2008 |volume= 9|issue= 1 | pages= 66–78 |doi= 10.1109/TCBB.2010.80 |pmid= 20733240 |s2cid= 2806529 }}</ref> Extending this further, four types of assortativity can be considered (see <ref>{{cite journal|last=Foster|first=Jacob |author2=David V. Foster |author3=Peter Grassberger |author4=Maya Paczuski |title=Edge direction and the structure of networks|journal=Proceedings of the National Academy of Sciences|date=June 2010|volume=107|issue=24|pages=10815–20|doi=10.1073/pnas.0912671107|doi-access=free|pmid=20505119 |pmc=2890716 |arxiv=0908.4288|bibcode=2010PNAS..10710815F}}</ref>). Adopting the notation of that article, it is possible to define four metrics <math>r( \text{in}, \text{in})</math>, <math>r( \text{in}, \text{out})</math>, <math>r( \text{out}, \text{in})</math>, and <math>r( \text{out}, \text{out})</math>. Let <math>(\alpha,\beta)</math>, be one of the ''in''/''out'' word pairs (e.g. <math>(\alpha,\beta)=(\text{out},\text{in})</math>). Let <math>E</math> be the number of edges in the network. Suppose we label the edges of the network <math>1,\ldots,E</math>. Given edge <math>i</math>, let <math>j^{\alpha}_i</math> be the <math>\alpha</math>-degree of the source (i.e. ''tail'') node vertex of the edge, and <math>k^{\beta}_i</math> be the <math>\beta</math>-degree of the target (i.e. ''head'') node of edge <math>i</math>. We indicate average values with bars, so that <math>\bar{j^\alpha}</math>, and <math> \bar{k^\beta}</math> are the average <math>\alpha</math>-degree of sources, and <math>\beta</math>-degree of targets, respectively; averages being taken over the edges of the network. Finally, we have

<math> r(\alpha,\beta)=\frac{\sum_i (j^\alpha_i-\bar{j^\alpha})(k^\beta_i-\bar{k^\beta})}{ \sqrt{\sum_i (j^\alpha_i-\bar{j^\alpha})^2} \sqrt{\sum_i (k^\beta_i-\bar{k^\beta})^2} }. </math>

===Neighbor connectivity===

Another means of capturing the degree correlation is by examining the properties of <math>\langle k_{nn} \rangle</math>, or the average degree of neighbors of a node with degree ''k''.<ref name=dcp>{{cite journal | last1=Pastor-Satorras | first1=Romualdo | last2=Vázquez | first2=Alexei | last3=Vespignani | first3=Alessandro | title=Dynamical and Correlation Properties of the Internet | journal=Physical Review Letters | volume=87 | issue=25 | year=2001 | issn=0031-9007 | doi=10.1103/physrevlett.87.258701 | article-number=258701|arxiv=cond-mat/0105161 | pmid=11736611 | bibcode=2001PhRvL..87y8701P| s2cid=6232586 }}</ref> This term is formally defined as: <math>\langle k_{nn} \rangle = \sum_{k'}{k'P(k'|k)}</math>, where <math>P(k'|k)</math> 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.

===Local assortativity===

In assortative networks, there could be nodes that are disassortative and vice versa. A local assortative measure<ref name=la>{{cite journal |last1= Piraveenan |first1= M. |last2= Prokopenko |first2= M. |last3= Zomaya |first3= A.Y. |title= Local assortativeness in scale-free networks |journal= EPL (Europhysics Letters) |year= 2008 |volume= 84 |issue= 2 |article-number= 28002 |doi= 10.1209/0295-5075/84/28002 |bibcode= 2008EL.....8428002P |s2cid= 250843016 |url= http://epljournal.edpsciences.org/10.1209/0295-5075/89/49901/pdf |access-date= 2022-03-01 |archive-date= 2023-02-04 |archive-url= https://web.archive.org/web/20230204155959/https://iopscience.iop.org/article/10.1209/0295-5075/89/49901/pdf |url-status= live |url-access= subscription }}</ref> 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,

<math> \rho = \frac{j\ \left(j+1\right)\left(\overline{k}-\ {\mu }_q\right)}{2M{\sigma }^2_q} </math>

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

Respectively, local assortativity for directed networks<ref name="ino"/> is a node's contribution to the directed assortativity of a network. A node's contribution to the assortativity of a directed network <math>r_d</math> is defined as, <math> {\rho }_d=\ \frac{{j_{out}}^2\left({\overline{k}}_{in}-\ {\mu }^{in}_q\right)+\ {j_{in}}^2\left({\overline{k}}_{out}-\ {\mu }^{out}_q\right)}{2\ M{\sigma }^{in}_q{\sigma }^{out}_q} </math>

Where <math>j_{out}</math> is the out-degree of the node under consideration and <math>j_{in}</math> is the in-degree, <math>{\overline{k}}_{in}</math> is the average in-degree of its neighbors (to which node <math>v</math>} has an edge) and <math>{\overline{k}}_{out}</math> is the average out-degree of its neighbors (from which node <math>v</math> has an edge).<math>{\sigma }^{in}_q\ \ne 0</math>,<math>\ {\ \sigma }^{out}_q\ \ne 0</math>.

By including the scaling terms <math>{\sigma }^{in}_q</math> and <math>{\ \sigma }^{out}_q</math> , we ensure that the equation for local assortativity for a directed network satisfies the condition <math>r_d=\ \sum^N_{i=1}{{\rho }_d}</math>.

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.<ref name="ino"/>

==Assortative mixing patterns of real networks==

The assortative patterns of a variety of real world networks have been examined. While models of social networks tend to exhibit assortative mixing, models of technological and biological networks appear to be disassortative. It has been suggested that this is because most networks have a tendency to evolve, unless otherwise constrained, towards their maximum entropy state—which is usually disassortative.<ref>{{cite journal | last1=Johnson | first1=Samuel | last2=Torres | first2=Joaquín J. | last3=Marro | first3=J. | last4=Muñoz | first4=Miguel A. | title=Entropic Origin of Disassortativity in Complex Networks | journal=Physical Review Letters | volume=104 | issue=10 | date=11 March 2010 | issn=0031-9007 | doi=10.1103/physrevlett.104.108702 | article-number=108702 | pmid=20366458| arxiv=1002.3286 | bibcode=2010PhRvL.104j8702J | s2cid=32880913 }}</ref>

The table also has the value of r calculated analytically for two models of networks:

# the random graph of Erdős and Rényi # BA Model (Barabási-Albert model)

In the ER model, since edges are placed at random without regard to vertex degree, it follows that r = 0 in the limit of large graph size. The scale-free BA model also holds this property. For the BA model in the special case of m=1 (where each incoming node attaches to only one of the existing nodes with a degree-proportional probability), a more precise result is known: as <math>N</math> (the number of vertices) tends to infinity, r approaches 0 at the same rate as <math>(\log^2 N)/N</math>.<ref name=amn />

==Application==

The properties of assortativity are useful in the field of epidemiology, since they can help understand the spread of disease or cures. For instance, the removal of a portion of a network's vertices may correspond to curing, vaccinating, or quarantining individuals or cells. Since social networks demonstrate assortative mixing, diseases targeting high degree individuals are likely to spread to other high degree nodes. Alternatively, within the cellular network—which, as a biological network is likely dissortative—vaccination strategies that specifically target the high degree vertices may quickly destroy the epidemic network.

==Structural disassortativity== {{Main|structural cut-off}} The basic structure of a network can cause these measures to show disassortativity, which is not representative of any underlying assortative or disassortative mixing. Special caution must be taken to avoid this structural disassortativity.

==References==

Category:Networks Category:Network theory