La asociatividad , o mezcla selectiva , es una preferencia para que los nodos de una red se unan 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 assortatividad 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.
Las correlaciones entre nodos de grado similar se encuentran a menudo 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 asociatividad . Por otro lado, las redes tecnológicas y biológicas suelen mostrar una mezcla desasortativa, o desasortividad , ya que los nodos de alto grado tienden a unirse a los nodos de bajo grado. [2]
Medición
La asociatividad se opera a menudo como una correlación entre dos nodos. Sin embargo, hay varias formas de capturar dicha correlación. Las dos medidas más destacadas son el coeficiente de assortividad y la conectividad del vecino . Estas medidas se describen con más detalle a continuación.
Coeficiente de asociatividad
El coeficiente de assortividad es el coeficiente de correlación de Pearson de grado 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 de assortative perfectos, cuando r = 0 la red es no assortativa, mientras que en r = −1 la red es completamente desassortativa.
El coeficiente de assortividad viene dado por. El terminoes la distribución del grado restante . Esto captura el número de bordes que salen del nodo, distintos 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 la suma y .
En un gráfico dirigido, in-assortativity () y out-assortativity () miden las tendencias de los nodos para conectarse con otros nodos que tienen grados de entrada y salida similares a ellos, respectivamente. [4] [5] Ampliando esto aún más, se pueden considerar cuatro tipos de assortividad (ver [4] [6] ). Adoptando la notación de ese artículo, es posible definir cuatro métricas, , , y . Dejar, Ser uno de los en / fuera pares de palabras (por ejemplo,). Dejarsea el número de bordes en la red. Supongamos que etiquetamos los bordes de la red. Ventaja dada, dejar ser el -grado del vértice del nodo de origen (es decir, cola ) del borde, y ser el -grado del nodo objetivo (es decir, cabeza ) del borde. Indicamos valores medios con barras, de modo que, y son el promedio - grado de fuentes, y -grado de objetivos, respectivamente; los promedios se toman en los bordes de la red. Finalmente, tenemos
Conectividad vecina
Otro medio de capturar la correlación de grados es examinando las propiedades de , o el grado medio de vecinos de un nodo con grado k . [8] Este término se define formalmente como:, dónde 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 los nodos de alto grado. Alternativamente, si la función está disminuyendo, la red es desordenada, 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 la assortividad de una red.
Asortividad local
En redes selectivas, podría haber nodos que sean desasortativos y viceversa. Se requiere una medida de clasificación local [9] para identificar tales anomalías dentro de las redes. La asociación local se define como la contribución que cada nodo hace a la asociación de la red. La asociación local en redes no dirigidas se define como,
Dónde es el exceso de grado de un nodo en particular y es el grado de exceso promedio de sus vecinos y M es el número de enlaces en la red.
Respectivamente, la assortatividad local para redes dirigidas [5] es la contribución de un nodo a la assortatividad dirigida de una red. Contribución de un nodo a la assortividad de una red dirigida Se define como,
Dónde es el grado de salida del nodo en consideración y es el grado, es el grado medio de sus vecinos (a qué nodo } tiene una ventaja) y es el grado medio de salida de sus vecinos (de qué nodo tiene una ventaja).,.
Incluyendo los términos de escala y , nos aseguramos de que la ecuación de la assortividad local para una red dirigida satisfaga la condición .
Además, en función de si se considera la distribución de grados de entrada o de salida, es posible definir la in-assortatividad local y la assortatividad local como las respectivas medidas de assortatividad local en una red dirigida. [5]
Patrones de mezcla surtidos de redes reales
Se han examinado los patrones surtidos de una variedad de redes del mundo real. Por ejemplo, la Fig. 3 enumera los valores de r para una variedad de redes. Nótese que las redes sociales (las cinco primeras entradas) tienen una aparente mezcla selectiva. Por otro lado, las redes tecnológicas y biológicas (las seis entradas del medio) parecen ser desastrosas. Se ha sugerido que esto se debe a que la mayoría de las redes tienden a evolucionar, a menos que estén limitadas de otra manera, hacia su estado de máxima entropía, que suele ser desasortativo. [10]
La tabla también tiene el valor de r calculado analíticamente para dos modelos de redes:
- el gráfico aleatorio de Erdős y Rényi
- Modelo BA ( modelo Barabási-Albert)
En el modelo ER, dado que los bordes se colocan al azar sin tener en cuenta el grado de vértice, se deduce que r = 0 en el límite del tamaño de gráfico grande. El modelo BA sin escala también tiene 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), tenemos como en el límite de lo grande . [2]
Solicitud
Las propiedades de la assortatividad son útiles en el campo de la epidemiología, ya que pueden ayudar a comprender la propagación de enfermedades o 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 dirigidas a individuos de alto grado se propaguen a otros nodos de alto grado. Alternativamente, dentro de la red celular, que como red biológica es probablemente dissortativa, las estrategias de vacunación que se dirigen específicamente a los vértices de alto grado pueden destruir rápidamente la red epidémica.
Dessortatividad estructural
La estructura básica de una red puede hacer que estas medidas muestren desasortividad, que no es representativa de ninguna mezcla clasificatoria o desasortativa subyacente. Se debe tener especial cuidado para evitar esta desasortividad estructural.
Ver también
Referencias
- ^ Newman, MEJ (27 de febrero de 2003). "Mezcla de patrones en redes". Revisión E física . Sociedad Estadounidense de Física (APS). 67 (2): 026126. arXiv : cond-mat / 0209450 . Código Bibliográfico : 2003PhRvE..67b6126N . doi : 10.1103 / physreve.67.026126 . ISSN 1063-651X .
- ^ a b c d Newman, MEJ (28 de octubre de 2002). "Mezcla selectiva en redes". Cartas de revisión física . Sociedad Estadounidense de Física (APS). 89 (20): 208701. arXiv : cond-mat / 0205405 . Código Bibliográfico : 2002PhRvL..89t8701N . doi : 10.1103 / physrevlett.89.208701 . ISSN 0031-9007 . PMID 12443515 .
- ^ Xulvi-Brunet, R .; Sokolov, MI (2005). "Cambio de correlaciones en redes: assortatividad y dissortatividad" . Acta Physica Polonica B . 36 (5): 1431.
- ^ a b Braha, D .; Bar-Yam, Y. (2007). “La mecánica estadística del desarrollo de productos complejos: resultados empíricos y analíticos” . Ciencias de la gestión. 53 (7): 1127-1145.
- ^ a b c 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 .
- ^ Foster, Jacob; David V. Foster; Peter Grassberger; Maya Paczuski (junio de 2010). "Dirección de borde y estructura de redes" . Actas de la Academia Nacional de Ciencias . 107 (24): 10815-20. arXiv : 0908.4288 . Código bibliográfico : 2010PNAS..10710815F . doi : 10.1073 / pnas.0912671107 . PMC 2890716 . PMID 20505119 .
- ^ Lee, Sang Hoon; Kim, Pan-Jun; Jeong, Hawoong (4 de enero de 2006). "Propiedades estadísticas de las redes muestreadas" . Revisión E física . Sociedad Estadounidense de Física (APS). 73 (1): 016102. arXiv : cond-mat / 0505232 . doi : 10.1103 / physreve.73.016102 . ISSN 1539-3755 .
- ^ Pastor-Satorras, Romualdo; Vázquez, Alexei; Vespignani, Alessandro (2001). "Propiedades dinámicas y de correlación de Internet". Cartas de revisión física . Sociedad Estadounidense de Física (APS). 87 (25): 258701. arXiv : cond-mat / 0105161 . Código Bibliográfico : 2001PhRvL..87y8701P . doi : 10.1103 / physrevlett.87.258701 . ISSN 0031-9007 . PMID 11736611 .
- ^ Piraveenan, M .; Prokopenko, M .; Zomaya, AY (2008). "Assortativeness local en redes libres de escala". EPL (Cartas Europhysics) . 84 (2): 28002. Bibcode : 2008EL ..... 8428002P . doi : 10.1209 / 0295-5075 / 84/28002 .
- ^ Johnson, Samuel; Torres, Joaquín J .; Marro, J .; Muñoz, Miguel A. (11 de marzo de 2010). "Origen entrópico de la desasortatividad en redes complejas". Cartas de revisión física . Sociedad Estadounidense de Física (APS). 104 (10): 108702. arXiv : 1002.3286 . Código Bibliográfico : 2010PhRvL.104j8702J . doi : 10.1103 / physrevlett.104.108702 . ISSN 0031-9007 . PMID 20366458 .