Assortativity

Last updated March 16, 2024

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.^[1] 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.^[2]

Measurement

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.^[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 $r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}$ . The term $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 $p_{k}$ as $q_{k}={\frac {(k+1)p_{k+1}}{\sum _{j\geq 1}jp_{j}}}$ . Finally, $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 $\sum _{jk}{e_{jk}}=1\,$ and $\sum _{j}{e_{jk}}=q_{k}\,$ .

In a Directed graph, in-assortativity ( $r({\text{in}},{\text{in}})$ ) and out-assortativity ( $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 $r({\text{in}},{\text{in}})$ , $r({\text{in}},{\text{out}})$ , $r({\text{out}},{\text{in}})$ , and $r({\text{out}},{\text{out}})$ . Let $(\alpha ,\beta )$ , be one of the in/out word pairs (e.g. $(\alpha ,\beta )=({\text{out}},{\text{in}})$ ). Let $E$ be the number of edges in the network. Suppose we label the edges of the network $1,\ldots ,E$ . Given edge $i$ , let $j_{i}^{\alpha }$ be the $\alpha$ -degree of the source (i.e. tail) node vertex of the edge, and $k_{i}^{\beta }$ be the $\beta$ -degree of the target (i.e. head) node of edge $i$ . We indicate average values with bars, so that ${\bar {j^{\alpha }}}$ , and ${\bar {k^{\beta }}}$ are the average $\alpha$ -degree of sources, and $\beta$ -degree of targets, respectively; averages being taken over the edges of the network. Finally, we have

$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}}}}}.$

Neighbor connectivity

Another means of capturing the degree correlation is by examining the properties of $\langle k_{nn}\rangle$ , or the average degree of neighbors of a node with degree k.^[6] This term is formally defined as: $\langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)}$ , where $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.

Local assortativity

In assortative networks, there could be nodes that are disassortative and vice versa. A local assortative measure^[7] 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,

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

Where $j$ is the excess degree of a particular node and ${\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 $r_{d}$ is defined as, ${\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 $j_{out}$ is the out-degree of the node under consideration and $j_{in}$ is the in-degree, ${\overline {k}}_{in}$ is the average in-degree of its neighbors (to which node $v$ } has an edge) and ${\overline {k}}_{out}$ is the average out-degree of its neighbors (from which node $v$ has an edge). ${\sigma }_{q}^{in}\ \neq 0$ , $\ {\ \sigma }_{q}^{out}\ \neq 0$ .

By including the scaling terms ${\sigma }_{q}^{in}$ and ${\ \sigma }_{q}^{out}$ , we ensure that the equation for local assortativity for a directed network satisfies the condition $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]

Assortative mixing patterns of real networks

The assortative patterns of a variety of real world networks have been examined. For instance, Fig. 3 lists values of r for a variety of networks. Note that the social networks (the first five entries) have apparent assortative mixing. On the other hand, the technological and biological networks (the middle six entries) all 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.^[8]

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 $N$ (the number of vertices) tends to infinity, r approaches 0 at the same rate as $(\log ^{2}N)/N$ .^[2]

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

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.

Related Research Articles

In mathematical physics and mathematics, the Pauli matrices are a set of three $2 \times 2$ complex matrices that are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

In transcendental number theory, the Lindemann–Weierstrass theorem is a result that is very useful in establishing the transcendence of numbers. It states the following:

In abstract algebra and number theory, Kummer theory provides a description of certain types of field extensions involving the adjunction of nth roots of elements of the base field. The theory was originally developed by Ernst Eduard Kummer around the 1840s in his pioneering work on Fermat's Last Theorem. The main statements do not depend on the nature of the field – apart from its characteristic, which should not divide the integer n – and therefore belong to abstract algebra. The theory of cyclic extensions of the field K when the characteristic of K does divide n is called Artin–Schreier theory.

In econometrics, the autoregressive conditional heteroskedasticity (ARCH) model is a statistical model for time series data that describes the variance of the current error term or innovation as a function of the actual sizes of the previous time periods' error terms; often the variance is related to the squares of the previous innovations. The ARCH model is appropriate when the error variance in a time series follows an autoregressive (AR) model; if an autoregressive moving average (ARMA) model is assumed for the error variance, the model is a generalized autoregressive conditional heteroskedasticity (GARCH) model.

In mathematics, a sesquilinear form is a generalization of a bilinear form that, in turn, is a generalization of the concept of the dot product of Euclidean space. A bilinear form is linear in each of its arguments, but a sesquilinear form allows one of the arguments to be "twisted" in a semilinear manner, thus the name; which originates from the Latin numerical prefix sesqui- meaning "one and a half". The basic concept of the dot product – producing a scalar from a pair of vectors – can be generalized by allowing a broader range of scalar values and, perhaps simultaneously, by widening the definition of a vector.

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

In mathematics, we can define norms for the elements of a vector space. When the vector space in question consists of matrices, these are called matrix norms.

In general relativity, the Gibbons–Hawking–York boundary term is a term that needs to be added to the Einstein–Hilbert action when the underlying spacetime manifold has a boundary.

In statistics, simple linear regression (SLR) is a linear regression model with a single explanatory variable. That is, it concerns two-dimensional sample points with one independent variable and one dependent variable and finds a linear function that, as accurately as possible, predicts the dependent variable values as a function of the independent variable. The adjective simple refers to the fact that the outcome variable is related to a single predictor.

In theoretical physics, the superconformal algebra is a graded Lie algebra or superalgebra that combines the conformal algebra and supersymmetry. In two dimensions, the superconformal algebra is infinite-dimensional. In higher dimensions, superconformal algebras are finite-dimensional and generate the superconformal group.

In mathematics, Schubert calculus is a branch of algebraic geometry introduced in the nineteenth century by Hermann Schubert in order to solve various counting problems of projective geometry and, as such, is viewed as part of enumerative geometry. Giving it a more rigorous foundation was the aim of Hilbert's 15th problem. It is related to several more modern concepts, such as characteristic classes, and both its algorithmic aspects and applications remain of current interest. The term Schubert calculus is sometimes used to mean the enumerative geometry of linear subspaces of a vector space, which is roughly equivalent to describing the cohomology ring of Grassmannians. Sometimes it is used to mean the more general enumerative geometry of algebraic varieties that are homogenous spaces of simple Lie groups. Even more generally, Schubert calculus is sometimes understood as encompassing the study of analogous questions in generalized cohomology theories.

Mixing patterns refer to systematic tendencies of one type of nodes in a network to connect to another type. For instance, nodes might tend to link to others that are very similar or very different. This feature is common in many social networks, although it also appears sometimes in non-social networks. Mixing patterns are closely related to assortativity; however, for the purposes of this article, the term is used to refer to assortative or disassortative mixing based on real-world factors, either topological or sociological.

A ratio distribution is a probability distribution constructed as the distribution of the ratio of random variables having two other known distributions. Given two random variables X and Y, the distribution of the random variable Z that is formed as the ratio Z = X/Y is a ratio distribution.

The term generalized logistic distribution is used as the name for several different families of probability distributions. For example, Johnson et al. list four forms, which are listed below.

The purpose of this page is to provide supplementary materials for the ordinary least squares article, reducing the load of the main article with mathematics and improving its accessibility, while at the same time retaining the completeness of exposition.

In continuum mechanics, an Arruda–Boyce model is a hyperelastic constitutive model used to describe the mechanical behavior of rubber and other polymeric substances. This model is based on the statistical mechanics of a material with a cubic representative volume element containing eight chains along the diagonal directions. The material is assumed to be incompressible. The model is named after Ellen Arruda and Mary Cunningham Boyce, who published it in 1993.

In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.

In mathematics, Ricci calculus constitutes the rules of index notation and manipulation for tensors and tensor fields on a differentiable manifold, with or without a metric tensor or connection. It is also the modern name for what used to be called the absolute differential calculus, developed by Gregorio Ricci-Curbastro in 1887–1896, and subsequently popularized in a paper written with his pupil Tullio Levi-Civita in 1900. Jan Arnoldus Schouten developed the modern notation and formalism for this mathematical framework, and made contributions to the theory, during its applications to general relativity and differential geometry in the early twentieth century.

The generalized distributive law (GDL) is a generalization of the distributive property which gives rise to a general message passing algorithm. It is a synthesis of the work of many authors in the information theory, digital communications, signal processing, statistics, and artificial intelligence communities. The law and algorithm were introduced in a semi-tutorial by Srinivas M. Aji and Robert J. McEliece with the same title.

In network theory, multidimensional networks, a special type of multilayer network, are networks with multiple kinds of relations. Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis, economics, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance.

References

↑ Newman, M. E. J. (27 February 2003). "Mixing patterns in networks". Physical Review E. 67 (2): 026126. arXiv: cond-mat/0209450 . Bibcode:2003PhRvE..67b6126N. doi:10.1103/physreve.67.026126. ISSN 1063-651X. PMID 12636767. S2CID 15186389.
1 2 3 Newman, M. E. J. (28 October 2002). "Assortative Mixing in Networks". Physical Review Letters. 89 (20): 208701. arXiv: cond-mat/0205405 . Bibcode:2002PhRvL..89t8701N. doi:10.1103/physrevlett.89.208701. ISSN 0031-9007. PMID 12443515. S2CID 1574486.
↑ Xulvi-Brunet, R.; Sokolov, I.M. (2005). "Changing correlations in networks: assortativity and dissortativity". Acta Physica Polonica B. 36 (5): 1431. Bibcode:2005AcPPB..36.1431X. Archived from the original on 2021-05-09. Retrieved 2019-08-15.
1 2 3 Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Assortative mixing in directed biological networks". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 9 (1): 66–78. doi:10.1109/TCBB.2010.80. PMID 20733240. S2CID 2806529.
↑ Foster, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (June 2010). "Edge direction and the structure of networks". Proceedings of the National Academy of Sciences. 107 (24): 10815–20. arXiv: 0908.4288 . Bibcode:2010PNAS..10710815F. doi: 10.1073/pnas.0912671107 . PMC 2890716 . PMID 20505119.
↑ Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). "Dynamical and Correlation Properties of the Internet". Physical Review Letters. 87 (25): 258701. arXiv: cond-mat/0105161 . Bibcode:2001PhRvL..87y8701P. doi:10.1103/physrevlett.87.258701. ISSN 0031-9007. PMID 11736611. S2CID 6232586.
↑ Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Local assortativeness in scale-free networks". EPL (Europhysics Letters). 84 (2): 28002. Bibcode:2008EL.....8428002P. doi:10.1209/0295-5075/84/28002. S2CID 250843016. Archived from the original on 2023-02-04. Retrieved 2022-03-01.
↑ Johnson, Samuel; Torres, Joaquín J.; Marro, J.; Muñoz, Miguel A. (11 March 2010). "Entropic Origin of Disassortativity in Complex Networks". Physical Review Letters. 104 (10): 108702. arXiv: 1002.3286 . Bibcode:2010PhRvL.104j8702J. doi:10.1103/physrevlett.104.108702. ISSN 0031-9007. PMID 20366458. S2CID 32880913.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[pre-1] Newman, M. E. J. (27 February 2003). "Mixing patterns in networks". Physical Review E. 67 (2): 026126. arXiv: cond-mat/0209450 . Bibcode:2003PhRvE..67b6126N. doi:10.1103/physreve.67.026126. ISSN 1063-651X. PMID 12636767. S2CID 15186389.

[amn-2] 1 2 3 Newman, M. E. J. (28 October 2002). "Assortative Mixing in Networks". Physical Review Letters. 89 (20): 208701. arXiv: cond-mat/0205405 . Bibcode:2002PhRvL..89t8701N. doi:10.1103/physrevlett.89.208701. ISSN 0031-9007. PMID 12443515. S2CID 1574486.

[un-3] Xulvi-Brunet, R.; Sokolov, I.M. (2005). "Changing correlations in networks: assortativity and dissortativity". Acta Physica Polonica B. 36 (5): 1431. Bibcode:2005AcPPB..36.1431X. Archived from the original on 2021-05-09. Retrieved 2019-08-15.

[ino-4] 1 2 3 Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Assortative mixing in directed biological networks". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 9 (1): 66–78. doi:10.1109/TCBB.2010.80. PMID 20733240. S2CID 2806529.

[5] Foster, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (June 2010). "Edge direction and the structure of networks". Proceedings of the National Academy of Sciences. 107 (24): 10815–20. arXiv: 0908.4288 . Bibcode:2010PNAS..10710815F. doi: 10.1073/pnas.0912671107 . PMC 2890716 . PMID 20505119.

[dcp-6] Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). "Dynamical and Correlation Properties of the Internet". Physical Review Letters. 87 (25): 258701. arXiv: cond-mat/0105161 . Bibcode:2001PhRvL..87y8701P. doi:10.1103/physrevlett.87.258701. ISSN 0031-9007. PMID 11736611. S2CID 6232586.

[la-7] Piraveenan, M.; Prokopenko, M.; Zomaya, A.Y. (2008). "Local assortativeness in scale-free networks". EPL (Europhysics Letters). 84 (2): 28002. Bibcode:2008EL.....8428002P. doi:10.1209/0295-5075/84/28002. S2CID 250843016. Archived from the original on 2023-02-04. Retrieved 2022-03-01.

[8] Johnson, Samuel; Torres, Joaquín J.; Marro, J.; Muñoz, Miguel A. (11 March 2010). "Entropic Origin of Disassortativity in Complex Networks". Physical Review Letters. 104 (10): 108702. arXiv: 1002.3286 . Bibcode:2010PhRvL.104j8702J. doi:10.1103/physrevlett.104.108702. ISSN 0031-9007. PMID 20366458. S2CID 32880913.

[1]

[2]

[4]

[5]

[6]

[7]

[8]