Surtatividad

Tendencia de que nodos similares se conecten

La asortatividad , o mezcla selectiva , es la preferencia de los nodos de una red por unirse a otros que son similares de alguna manera. Aunque la medida específica de similitud puede variar, los teóricos de redes a menudo examinan la asortatividad en términos del grado de un nodo . ^[1] La adición de esta característica a los modelos de red se aproxima más a los comportamientos de muchas redes del mundo real.

A menudo se encuentran correlaciones entre nodos de grado similar en los patrones de mezcla de muchas redes observables. Por ejemplo, en las redes sociales , los nodos tienden a estar conectados con otros nodos con valores de grado similares. Esta tendencia se conoce como mezcla selectiva o asortatividad . Por otro lado, las redes tecnológicas y biológicas suelen mostrar una mezcla desasortativa, o desasortatividad , ya que los nodos de alto grado tienden a unirse a nodos de bajo grado. ^[2]

Medición

Fig. 1: Redes sin escala para diferentes grados de sortatividad: (a) A = 0 (red no correlacionada), (b) A = 0,26, (c) A = 0,43, donde A indica r (el coeficiente de sortatividad , tal como se define en esta subsección). ^[3]

La asortatividad a menudo se operacionaliza como una correlación entre dos nodos. Sin embargo, hay varias maneras de captar dicha correlación. Las dos medidas más destacadas son el coeficiente de asortatividad y la conectividad de vecinos . Estas medidas se describen con más detalle a continuación.

Coeficiente de sortatividad

El coeficiente de asortatividad es el coeficiente de correlación de grado de Pearson entre pares de nodos vinculados. ^[2] Los valores positivos de r indican una correlación entre nodos de grado similar, mientras que los valores negativos indican relaciones entre nodos de diferente grado. En general, r se encuentra entre −1 y 1. Cuando r = 1, se dice que la red tiene patrones de mezcla selectivos perfectos, cuando r = 0 la red no es selectivo, mientras que en r = −1 la red es completamente desasortativa.

El coeficiente de asortatividad viene dado por . El término es la distribución del grado restante . Esto captura el número de aristas que salen del nodo, distintas del que conecta el par. La distribución de este término se deriva de la distribución de grados como . Finalmente, se refiere a la distribución de probabilidad conjunta de los grados restantes de los dos vértices. Esta cantidad es simétrica en un gráfico no dirigido y sigue las reglas de suma y . ${\displaystyle r={\frac {\sum _{jk}{jk(e_{jk}-q_{j}q_{k})}}{\sigma _{q}^{2}}}}$ ${\displaystyle q_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle q_{k}={\frac {(k+1)p_{k+1}}{\sum _{j\geq 1}jp_{j}}}}$ ${\displaystyle e_{jk}}$ ${\displaystyle \sum _{jk}{e_{jk}}=1\,}$ ${\displaystyle \sum _{j}{e_{jk}}=q_{k}\,}$

En un gráfico dirigido, la asortatividad ( ) y la asortatividad ( ) miden las tendencias de los nodos a conectarse con otros nodos que tienen grados de entrada y salida similares a ellos, respectivamente. ^[4] Ampliando esto aún más, se pueden considerar cuatro tipos de sortatividad (ver ^[5] ). Adoptando la notación de ese artículo, es posible definir cuatro métricas , , y . Sea , uno de los pares de palabras de entrada / salida (p. ej. ). Sea el número de aristas de la red. Supongamos que etiquetamos los bordes de la red . Dado edge , sea el grado del vértice del nodo de origen (es decir, la cola ) del borde y el grado del nodo objetivo (es decir, la cabeza ) del borde . Indicamos los valores promedio con barras, de modo que , y son el grado promedio de fuentes y el grado de objetivos, respectivamente; Se toman promedios en los bordes de la red. Finalmente, tenemos ${\displaystyle r({\text{in}},{\text{in}})}$ ${\displaystyle r({\text{out}},{\text{out}})}$ ${\displaystyle r({\text{in}},{\text{in}})}$ ${\displaystyle r({\text{in}},{\text{out}})}$ ${\displaystyle r({\text{out}},{\text{in}})}$ ${\displaystyle r({\text{out}},{\text{out}})}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle (\alpha ,\beta )=({\text{out}},{\text{in}})}$ ${\displaystyle E}$ ${\displaystyle 1,\ldots ,E}$ ${\displaystyle i}$ ${\displaystyle j_{i}^{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle k_{i}^{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle i}$ ${\displaystyle {\bar {j^{\alpha }}}}$ ${\displaystyle {\bar {k^{\beta }}}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$

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

Conectividad vecina

Otra forma de capturar el grado de correlación es examinando las propiedades de , o el grado promedio de los vecinos de un nodo con grado k . ^[6] Este término se define formalmente como: , donde es la probabilidad condicional de que un borde de un nodo con grado k apunte a un nodo con grado k' . Si esta función es creciente, la red es selectiva, ya que muestra que los nodos de alto grado se conectan, en promedio, a nodos de alto grado. Alternativamente, si la función es decreciente, la red es desasortativa, ya que los nodos de alto grado tienden a conectarse a nodos de menor grado. La función se puede trazar en un gráfico (ver Fig. 2) para representar la tendencia general de variabilidad de una red. ${\displaystyle \langle k_{nn}\rangle }$ ${\displaystyle \langle k_{nn}\rangle =\sum _{k'}{k'P(k'|k)}}$ ${\displaystyle P(k'|k)}$

Surtatividad local

En redes asortativas, podría haber nodos desasortativos y viceversa. Se requiere una medida de selección local ^[7] para identificar tales anomalías dentro de las redes. La asortatividad local se define como la contribución que cada nodo hace a la asortatividad de la red. La asortatividad local en redes no dirigidas se define como,

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

Donde es el grado de exceso de un nodo particular y es el grado de exceso promedio de sus vecinos y M es el número de enlaces en la red. ${\displaystyle j}$ ${\displaystyle {\overline {k}}}$

Respectivamente, la asortatividad local para redes dirigidas ^[4] es la contribución de un nodo a la asortatividad dirigida de una red. La contribución de un nodo a la variabilidad de una red dirigida se define como, ${\displaystyle r_{d}}$ ${\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}}}}$

Donde es el grado de salida del nodo bajo consideración y es el grado de entrada, es el grado de entrada promedio de sus vecinos (hacia qué nodo } tiene una ventaja) y es el grado de salida promedio de sus vecinos (a partir de qué nodo tiene una ventaja). , . ${\displaystyle j_{out}}$ ${\displaystyle j_{in}}$ ${\displaystyle {\overline {k}}_{in}}$ ${\displaystyle v}$ ${\displaystyle {\overline {k}}_{out}}$ ${\displaystyle v}$ ${\displaystyle {\sigma }_{q}^{in}\ \neq 0}$ ${\displaystyle \ {\ \sigma }_{q}^{out}\ \neq 0}$

Al incluir los términos de escala y , nos aseguramos de que la ecuación de sortatividad local para una red dirigida satisfaga la condición . ${\displaystyle {\sigma }_{q}^{in}}$ ${\displaystyle {\ \sigma }_{q}^{out}}$ ${\displaystyle r_{d}=\ \sum _{i=1}^{N}{{\rho }_{d}}}$

Además, en función de si se considera la distribución de grado de entrada o de grado de salida, es posible definir la asortatividad local y la asortatividad local como las respectivas medidas de asortatividad local en una red dirigida. ^[4]

Patrones de mezcla variados de redes reales.

Se han examinado los patrones de clasificación de una variedad de redes del mundo real. Por ejemplo, la Fig. 3 enumera valores de r para una variedad de redes. Tenga en cuenta que las redes sociales (las primeras cinco entradas) tienen una aparente mezcla variada. Por otro lado, las redes tecnológica y biológica (las seis entradas intermedias) parecen no estar diferenciadas. Se ha sugerido que esto se debe a que la mayoría de las redes tienen una tendencia a evolucionar, a menos que se les restrinja lo contrario, hacia su estado de máxima entropía, que suele ser desasortativo. ^[8]

La tabla también tiene el valor de r calculado analíticamente para dos modelos de redes:

1. el gráfico aleatorio de Erdős y Rényi
2. Modelo BA (modelo Barabási-Albert)

En el modelo ER, dado que los bordes se colocan al azar sin tener en cuenta el grado del vértice, se deduce que r = 0 en el límite del tamaño del gráfico grande. El modelo BA sin escala también cumple esta propiedad. Para el modelo BA en el caso especial de m=1 (donde cada nodo entrante se une a solo uno de los nodos existentes con una probabilidad proporcional al grado), se conoce un resultado más preciso: como (el número de vértices) tiende a infinito , r tiende a 0 a la misma velocidad que . ^[2] ${\displaystyle N}$ ${\displaystyle (\log ^{2}N)/N}$

Solicitud

Las propiedades de la asortatividad son útiles en el campo de la epidemiología, ya que pueden ayudar a comprender la propagación de enfermedades o sus curas. Por ejemplo, la eliminación de una parte de los vértices de una red puede corresponder a curar, vacunar o poner en cuarentena a individuos o células. Dado que las redes sociales demuestran una mezcla selectiva, es probable que las enfermedades que afectan a individuos de alto grado se propaguen a otros nodos de alto grado. Alternativamente, dentro de la red celular (que, como red biológica, probablemente sea dissortiva), las estrategias de vacunación dirigidas específicamente a los vértices de alto grado pueden destruir rápidamente la red epidémica.

Desasortatividad estructural

La estructura básica de una red puede hacer que estas medidas muestren desasortatividad, que no es representativa de ninguna mezcla assortativa o desasortativa subyacente. Se debe tener especial precaución para evitar esta desasortatividad estructural.

Ver también

• Mezcla variada
• Apego preferencial
• homofilia
• corte estructural
• Coeficiente del club rico

Referencias

1. Newman, MEJ (27 de febrero de 2003). "Mezcla de patrones en redes". Revisión física E. 67 (2): 026126. arXiv : cond-mat/0209450 . Código bibliográfico : 2003PhRvE..67b6126N. doi :10.1103/physreve.67.026126. ISSN  1063-651X. PMID  12636767. S2CID  15186389.
2. Newman, MEJ (28 de octubre de 2002). "Mezcla selectiva en redes". Cartas de revisión física . 89 (20): 208701. arXiv : cond-mat/0205405 . Código bibliográfico : 2002PhRvL..89t8701N. doi : 10.1103/physrevlett.89.208701. ISSN  0031-9007. PMID  12443515. S2CID  1574486.
3. Xulvi-Brunet, R.; Sokolov, IM (2005). "Cambio de correlaciones en redes: asortatividad y disortatividad". Acta Física Polonica B. 36 (5): 1431. Código bibliográfico : 2005AcPPB..36.1431X. Archivado desde el original el 9 de mayo de 2021 . Consultado el 15 de agosto de 2019 .
4. Piraveenan, M.; Prokopenko, M.; Zomaya, AY (2008). "Mezcla selectiva en redes biológicas dirigidas". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 9 (1): 66–78. doi :10.1109/TCBB.2010.80. PMID  20733240. S2CID  2806529.
5. Fomentar, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (junio de 2010). "Dirección de los bordes y estructura de las redes". Procedimientos de la Academia Nacional de Ciencias . 107 (24): 10815–20. arXiv : 0908.4288 . Código Bib : 2010PNAS..10710815F. doi : 10.1073/pnas.0912671107 . PMC 2890716 . PMID  20505119. 
6. Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). "Propiedades dinámicas y de correlación de Internet". Cartas de revisión física . 87 (25): 258701. arXiv : cond-mat/0105161 . Código Bib : 2001PhRvL..87y8701P. doi : 10.1103/physrevlett.87.258701. ISSN  0031-9007. PMID  11736611. S2CID  6232586.
7. Piraveenan, M.; Prokopenko, M.; Zomaya, AY (2008). "Selección local en redes sin escala". EPL (Letras de Eurofísica) . 84 (2): 28002. Código bibliográfico : 2008EL.....8428002P. doi :10.1209/0295-5075/84/28002. S2CID  250843016. Archivado desde el original el 4 de febrero de 2023 . Consultado el 1 de marzo de 2022 .
8. Johnson, Samuel; Torres, Joaquín J.; Marro, J.; Muñoz, Miguel A. (11 de marzo de 2010). "Origen entrópico de la dissortatividad en redes complejas". Cartas de revisión física . 104 (10): 108702. arXiv : 1002.3286 . Código Bib : 2010PhRvL.104j8702J. doi : 10.1103/physrevlett.104.108702. ISSN  0031-9007. PMID  20366458. S2CID  32880913.