Red libre de escala

Una red sin escala o Red libre de escala es una red cuya distribución de grados sigue una ley de potencia, al menos asintóticamente. Es decir, la fracción P (k) de nodos en la red que tienen k conexiones a otros nodos vale para valores grandes de k como

donde es un parámetro cuyo valor está típicamente en el rango (donde el segundo momento (parámetro de escala) de es infinito pero el primer momento es finito), aunque ocasionalmente puede estar fuera de estos límites.

Se ha informado que muchas redes no tienen escala, aunque el análisis estadístico ha refutado muchas de estas afirmaciones y cuestionado seriamente otras. Además, algunos han argumentado que el simple hecho de saber que una distribución de grados es de cola gruesa es más importante que saber si una red no tiene escala según definiciones estadísticamente rigurosas. El apego preferencial y el modelo de aptitud se han propuesto como mecanismos para explicar las distribuciones de grado de ley de potencia conjeturadas en redes reales. Puede parecer que los modelos alternativos, como el vínculo preferencial superlineal y el vínculo preferencial del segundo vecino, generan redes transitorias sin escala, pero la distribución de grados se desvía de una ley de potencia a medida que las redes se vuelven muy grandes.

Historia

En estudios de las redes de citas entre artículos científicos, Derek de Solla Price mostró en 1965 que el número de enlaces a artículos, es decir, el número de citas que reciben, tenía una distribución de cola pesada siguiendo una distribución de Pareto o ley de potencia, y por lo tanto, la red de citas no tiene escala. Sin embargo, no utilizó el término "red sin escala", que no se acuñó hasta algunas décadas después. En un artículo posterior de 1976, Price también propuso un mecanismo para explicar la aparición de leyes de potencia en las redes de citas, que denominó "ventaja acumulativa", pero que hoy en día se conoce más comúnmente con el nombre de apego preferencial.

El interés reciente en las redes sin escala comenzó en 1999 con el trabajo de Albert-László Barabási y sus colegas de la Universidad de Notre Dame, quienes trazaron un mapa de la topología de una parte de la World Wide Web.encontrando que algunos nodos, a los que llamaron "hubs", tenían muchas más conexiones que otros y que la red en su conjunto tenía una distribución de ley de potencias del número de enlaces que se conectaban a un nodo. Después de descubrir que algunas otras redes, incluidas algunas redes sociales y biológicas, también tenían distribuciones de grado de cola pesada, Barabási y sus colaboradores acuñaron el término "red sin escala" para describir la clase de redes que exhiben una distribución de grado de ley de potencia. Sin embargo, al estudiar siete ejemplos de redes en sistemas sociales, económicos, tecnológicos, biológicos y físicos, Amaral et al. no pudieron encontrar una red libre de escala entre estos siete ejemplos. Solo uno de estos ejemplos, la red de actores de cine, tenía una distribución de grados P (k) siguiendo un régimen de ley de potencia para k moderado, aunque eventualmente este régimen de ley de potencia fue seguido por un corte agudo que muestra una caída exponencial para k grande.

Barabási y Réka Albert propusieron un mecanismo generativo para explicar la aparición de distribuciones de ley de potencias, al que llamaron "apego preferencial" y que es esencialmente el mismo que propone Price. Las soluciones analíticas para este mecanismo (también similar a la solución de Price) fueron presentadas en 2000 por Dorogovtsev, Mendes y Samukhin e independientemente por Krapivsky, Redner y Leyvraz, y luego probadas rigurosamente por el matemático Béla Bollobás. Cabe destacar, sin embargo, que este mecanismo solo produce un subconjunto específico de redes en la clase sin escala, y desde entonces se han descubierto muchos mecanismos alternativos.

La historia de las redes libres de escala también incluye algunos desacuerdos. A nivel empírico, se ha cuestionado la naturaleza libre de escala de varias redes. Por ejemplo, los tres hermanos Faloutsos creían que Internet tenía una distribución de grado de ley de poder sobre la base de datos de rastreo de ruta; sin embargo, se ha sugerido que se trata de una ilusión de capa 3 creada por los enrutadores, que aparecen como nodos de alto grado mientras ocultan la estructura interna de capa 2 de los AS que interconectan.

A nivel teórico, se han propuesto mejoras a la definición abstracta de sin escala. Por ejemplo, Li et al. (2005) ofrecieron recientemente una "métrica sin escala" potencialmente más precisa. Brevemente, sea G un grafo con conjunto de aristas E, e indique el grado de un vértice (es decir, el número de aristas que inciden en ) por . Definir

Esto se maximiza cuando los nodos de alto grado están conectados a otros nodos de alto grado. Ahora define

donde s _max es el valor máximo de s (H) para H en el conjunto de todos los gráficos con distribución de grados idéntica a la de G. Esto da una métrica entre 0 y 1, donde un gráfico G con S (G) pequeño es "rico en escala", y un gráfico G con S (G) cercano a 1 es "sin escala". Esta definición captura la noción de autosimilitud implícita en el nombre "sin escala".

Visión general

Hay dos componentes principales que explican el surgimiento de la propiedad libre de escala en redes complejas: el crecimiento y el apego preferencial. Por "crecimiento" se entiende un proceso de crecimiento en el que, durante un período de tiempo prolongado, nuevos nodos se unen a un sistema ya existente, una red (como la World Wide Web, que ha crecido en miles de millones de páginas web durante 10 años). Finalmente, por "conexión preferencial" se entiende que los nuevos nodos prefieren conectarse a nodos que ya tienen un alto número de enlaces con otros. Por lo tanto, existe una mayor probabilidad de que más y más nodos se enlacen a uno que ya tiene muchos enlaces, lo que lleva a este nodo a un concentrador in-fine. Dependiendo de la red, los concentradores pueden ser selectivos o no selectivos. La variedad se encontraría en las redes sociales en las que las personas bien conectadas/famosas tenderían a conocerse mejor. La dissortatividad se encontraría en redes tecnológicas (Internet, World Wide Web) y biológicas (interacción de proteínas, metabolismo).

Características

La característica más notable en una red sin escala es la relativa frecuencia de los vértices con un grado que supera con creces el promedio. Los nodos de grado más alto a menudo se denominan "concentradores" y se cree que cumplen propósitos específicos en sus redes, aunque esto depende en gran medida del dominio.

Agrupación

Otra característica importante de las redes sin escala es la distribución del coeficiente de agrupamiento, que disminuye a medida que aumenta el grado del nodo. Esta distribución también sigue una ley de potencia. Esto implica que los nodos de bajo grado pertenecen a subgrafos muy densos y esos subgrafos están conectados entre sí a través de hubs. Considere una red social en la que los nodos son personas y los enlaces son relaciones conocidas entre personas. Es fácil ver que las personas tienden a formar comunidades, es decir, pequeños grupos en los que todos conocen a todos (se puede pensar en dicha comunidad como un grafo completo). Además, los miembros de una comunidad también tienen algunas relaciones de amistad con personas fuera de esa comunidad. Algunas personas, sin embargo, están conectadas a un gran número de comunidades (p. ej., celebridades, políticos).

En la actualidad, las características más específicas de las redes libres de escala varían según el mecanismo generativo utilizado para crearlas. Por ejemplo, las redes generadas por apego preferencial normalmente colocan los vértices de alto grado en el medio de la red, conectándolos para formar un núcleo, con nodos de grado cada vez más bajo que forman las regiones entre el núcleo y la periferia. La eliminación aleatoria de incluso una gran fracción de vértices afecta muy poco la conectividad general de la red, lo que sugiere que tales topologías podrían ser útiles para la seguridad, mientras que los ataques dirigidos destruyen la conectividad muy rápidamente. Otras redes sin escala, que colocan los vértices de alto grado en la periferia, no presentan estas propiedades. Similarmente,

Inmunización

La cuestión de cómo inmunizar eficientemente redes libres escalables que representan redes realistas como Internet y las redes sociales ha sido estudiada extensamente. Una de tales estrategias es inmunizar los nodos de mayor grado, es decir, ataques dirigidos (intencionales) ya que para este caso p es relativamente alto y se necesitan menos nodos para ser inmunizados. Sin embargo, en muchos casos realistas, la estructura global no está disponible y los nodos de mayor grado no se conocen.

Las propiedades del gráfico aleatorio pueden cambiar o permanecer invariantes bajo las transformaciones de gráfico. Mashaghi A. et al., por ejemplo, demostraron que una transformación que convierte gráficos aleatorios en sus gráficos de borde dual (o gráficos lineales) produce un conjunto de gráficos con casi la misma distribución de grados, pero con correlaciones de grado y una agrupación significativamente mayor. coeficiente. Los gráficos sin escala, como tales, permanecen sin escala bajo tales transformaciones.

Ejemplos

Aunque se cree que muchas redes del mundo real no tienen escala, la evidencia a menudo no es concluyente, principalmente debido a la creciente conciencia de técnicas de análisis de datos más rigurosas. Como tal, la naturaleza libre de escala de muchas redes todavía está siendo debatida por la comunidad científica. Algunos ejemplos de redes que se afirma que no tienen escala incluyen:

• Algunas redes sociales, incluidas las redes de colaboración. Dos ejemplos que han sido ampliamente estudiados son la colaboración de actores de cine en películas y la coautoría de papers por parte de matemáticos.
• Muchos tipos de redes informáticas, incluidos Internet y el gráfico web de la World Wide Web.
• Gráficos de dependencia de software, algunos de ellos descritos con un modelo generativo.
• Algunas redes financieras como las redes de pagos interbancarios
• Redes de interacción proteína-proteína.
• Redes semánticas.
• Redes de aerolíneas.

La topología sin escala también se ha encontrado en superconductores de alta temperatura. Las cualidades de un superconductor de alta temperatura, un compuesto en el que los electrones obedecen las leyes de la física cuántica y fluyen en perfecta sincronía, sin fricción, parecen estar relacionadas con los arreglos fractales de los átomos de oxígeno aparentemente aleatorios y la distorsión de la red.

Recientemente se ha propuesto una estructura celular que llena el espacio, una red estocástica plana ponderada (WPSL), cuya distribución de números de coordinación sigue una ley de potencia. Implica que la red tiene unos pocos bloques que tienen un número asombrosamente grande de vecinos con los que comparten fronteras comunes. Su construcción comienza con un iniciador, digamos un cuadrado de unidad de área, y un generador que lo divide aleatoriamente en cuatro bloques. A partir de entonces, el generador se aplica secuencialmente una y otra vez a solo uno de los bloques disponibles elegidos preferentemente con respecto a sus áreas. Da como resultado la partición del cuadrado en bloques rectangulares mutuamente excluyentes cada vez más pequeños. El dual del WPSL (DWPSL), que se obtiene reemplazando cada bloque con un nodo en su centro,La razón de esto es que crece siguiendo la regla del modelo de apego impulsado por la mediación que también incorpora la regla de apego preferencial pero disfrazada.

Modelos generativos

Las redes libres de escala no surgen solo por casualidad. Erdős y Rényi (1960) estudiaron un modelo de crecimiento para grafos en el que, en cada paso, se eligen dos nodos uniformemente al azar y se inserta un enlace entre ellos. Las propiedades de estos gráficos aleatorios son diferentes de las propiedades que se encuentran en las redes sin escala y, por lo tanto, se necesita un modelo para este proceso de crecimiento.

El modelo generativo más conocido para un subconjunto de redes libres de escala es el modelo generativo Rich Get Richer de Barabási y Albert (1999) en el que cada nueva página web crea enlaces a páginas web existentes con una distribución de probabilidad que no es uniforme, sino proporcional a el grado de entrada actual de las páginas Web. Este modelo fue inventado originalmente por Derek J. de Solla Price en 1965 bajo el término ventaja acumulativa., pero no alcanzó popularidad hasta que Barabási redescubrió los resultados bajo su nombre actual (Modelo BA). Según este proceso, una página con muchos enlaces internos atraerá más enlaces internos que una página normal. Esto genera una ley de potencia, pero el gráfico resultante difiere del gráfico web real en otras propiedades, como la presencia de pequeñas comunidades estrechamente conectadas. Se han propuesto y estudiado modelos y características de red más generales. Por ejemplo, Pachón et al. (2018) propusieron una variante del modelo generativo Rich Get Richer que tiene en cuenta dos reglas de vinculación diferentes: un mecanismo de vinculación preferencial y una elección uniforme solo para los nodos más recientes. Para una reseña ver el libro de Dorogovtsev y Mendes.Algunos mecanismos, como la vinculación preferencial superlineal y la vinculación con un segundo vecino, generan redes que transitoriamente no tienen escala, pero se desvían de una ley de potencia a medida que las redes crecen.

Un modelo generativo algo diferente para los enlaces web ha sido sugerido por Pennock et al. (2002). Examinaron comunidades con intereses en un tema específico, como las páginas de inicio de universidades, empresas públicas, periódicos o científicos, y descartaron los principales centros de la Web. En este caso, la distribución de enlaces ya no era una ley de potencia sino que se asemejaba a una distribución normal. Con base en estas observaciones, los autores propusieron un modelo generativo que combina el apego preferencial con una probabilidad de referencia de obtener un vínculo.

Otro modelo generativo es el modelo de copia estudiado por Kumar et al. (2000), en el que los nuevos nodos eligen aleatoriamente un nodo existente y copian una fracción de los enlaces del nodo existente. Esto también genera una ley de potencia.

El crecimiento de las redes (agregar nuevos nodos) no es una condición necesaria para crear una red sin escala. Una posibilidad (Caldarelli et al. 2002) es considerar la estructura como estática y trazar un vínculo entre los vértices de acuerdo con una propiedad particular de los dos vértices involucrados. Una vez especificada la distribución estadística para estas propiedades de vértice (fitness), resulta que en algunas circunstancias también las redes estáticas desarrollan propiedades libres de escala.

Modelo generalizado sin escala

Ha habido un estallido de actividad en el modelado de redes complejas sin escala. La receta de Barabási y Albert ha sido seguida por varias variaciones y generalizaciones y la renovación de trabajos matemáticos anteriores. Siempre que haya una distribución de ley de potencia en un modelo, es una red sin escala, y un modelo de esa red es un modelo sin escala.

Características

Muchas redes reales son (aproximadamente) sin escala y, por lo tanto, requieren modelos sin escala para describirlas. En el esquema de Price, se necesitan dos ingredientes para construir un modelo sin escala:

1. Agregar o eliminar nodos. Por lo general, nos concentramos en hacer crecer la red, es decir, agregar nodos.

2. Conexión preferencial: la probabilidad de que los nuevos nodos se conecten al nodo "antiguo".

Tenga en cuenta que algunos modelos (consulte el modelo Dangalchev y Fitness a continuación) también pueden funcionar de forma estática, sin cambiar la cantidad de nodos. También debe tenerse en cuenta que el hecho de que los modelos de "conexión preferencial" den lugar a redes sin escala no prueba que este sea el mecanismo subyacente a la evolución de las redes sin escala en el mundo real, ya que pueden existir diferentes mecanismos en trabajar en sistemas del mundo real que, sin embargo, dan lugar a la escala.

Ejemplos

Ha habido varios intentos de generar propiedades de red sin escala. Aquí hay unos ejemplos:

El modelo Barabási-Albert

El modelo de Barabási-Albert, una versión no dirigida del modelo de Price, tiene un apego preferencial lineal y agrega un nuevo nodo en cada paso de tiempo.

(Observe que otra característica general de las redes reales es que , es decir, existe una probabilidad distinta de cero de que un nuevo nodo se una a un nodo aislado. Por lo tanto, en general tiene la forma , donde es el atractivo inicial del nodo).

Modelo de red de dos niveles

Dangalchev (ver [43]) construye un modelo de 2 L considerando la importancia de cada uno de los vecinos de un nodo de destino en el apego preferencial. El atractivo de un nodo en el modelo 2-L depende no solo del número de nodos vinculados a él, sino también del número de enlaces en cada uno de estos nodos.

donde C es un coeficiente entre 0 y 1.

Una variante del modelo 2-L, el modelo k2, donde el primer y el segundo nodo vecino contribuyen por igual al atractivo del nodo objetivo, demuestra la aparición de redes transitorias sin escala. En el modelo k2, la distribución de grados aparece aproximadamente sin escala siempre que la red sea relativamente pequeña, pero surgen desviaciones significativas del régimen sin escala a medida que la red crece. Esto da como resultado el atractivo relativo de los nodos con diferentes grados de cambio con el tiempo, una característica que también se observa en las redes reales.

Modelo de apego impulsado por la mediación (MDA)

En el modelo de conexión impulsada por la mediación (MDA), un nuevo nodo que viene con bordes elige un nodo conectado existente al azar y luego se conecta, no con ese, sino con sus vecinos, también elegidos al azar. La probabilidad de que el nodo del nodo existente elegido sea

El factor es el inverso de la media armónica (IHM) de los grados de los vecinos de un nodo . Una extensa investigación numérica sugiere que aproximadamente el valor medio de IHM en el límite grande se convierte en una constante, lo que significa . Implica que cuanto más altos sean los enlaces (grado) que tiene un nodo, mayor será su probabilidad de obtener más enlaces, ya que se puede llegar a ellos de un mayor número de formas a través de mediadores, lo que esencialmente encarna la idea intuitiva del mecanismo rico se vuelve más rico (o el mecanismo preferencial). regla de apego del modelo Barabasi-Albert). Por lo tanto, se puede ver que la red MDA sigue la regla PA pero disfrazada.

Sin embargo, para describir el mecanismo ganador se lo lleva todo, ya que encontramos que casi del total de nodos tiene grado uno y uno es súper rico en grado. A medida que aumenta el valor, la disparidad entre los superricos y los pobres disminuye y, a medida que encontramos una transición de un mecanismo rico que se vuelve súper rico a un mecanismo rico que se vuelve más rico.

Apego preferencial no lineal

El modelo de Barabási-Albert asume que la probabilidad de que un nodo se adhiera a nodo es proporcional al grado de nodo . Esta suposición involucra dos hipótesis: primero, que depende de , a diferencia de los grafos aleatorios en los que , y segundo, que la forma funcional de es lineal en .

En el apego preferencial no lineal, la forma de no es lineal, y estudios recientes han demostrado que la distribución de grados depende en gran medida de la forma de la función.

Krapivsky, Redner y Leyvraz demuestran que la naturaleza libre de escala de la red se destruye por el apego preferencial no lineal. El único caso en el que la topología de la red no tiene escala es en el que la conexión preferencial es asintóticamente lineal, es decir, como . En este caso, la ecuación de velocidad conduce a

De esta forma, el exponente de la distribución de grados puede ajustarse a cualquier valor entre 2 y .

Modelo de red jerárquica

Los modelos de red jerárquica son, por diseño, libres de escala y tienen una alta agrupación de nodos.

La construcción iterativa conduce a una red jerárquica. Partiendo de un clúster completamente conectado de cinco nodos, creamos cuatro réplicas idénticas que conectan los nodos periféricos de cada clúster con el nodo central del clúster original. A partir de esto, obtenemos una red de 25 nodos (N = 25). Repitiendo el mismo proceso, podemos crear cuatro réplicas más del clúster original: los cuatro nodos periféricos de cada uno se conectan al nodo central de los nodos creados en el primer paso. Esto da N = 125 y el proceso puede continuar indefinidamente.

Modelo de fitness

La idea es que el enlace entre dos vértices se asigne no aleatoriamente con una probabilidad p igual para todos los vértices. Más bien, para cada vértice j existe una aptitud intrínseca x _j y se crea un vínculo entre el vértice i y j con una probabilidad . En el caso de World Trade Web es posible reconstruir todas las propiedades usando como aptitudes del país su PIB, y tomando

Gráficos geométricos hiperbólicos

Suponiendo que una red tiene una geometría hiperbólica subyacente, se puede utilizar el marco de las redes espaciales para generar distribuciones de grados sin escala. Esta distribución de grados heterogéneos simplemente refleja la curvatura negativa y las propiedades métricas de la geometría hiperbólica subyacente.

Transformación dual de borde para generar gráficos sin escala con las propiedades deseadas

Comenzando con gráficos sin escala con correlación de bajo grado y coeficiente de agrupamiento, se pueden generar nuevos gráficos con correlaciones de grado mucho más altos y coeficientes de agrupamiento aplicando transformación de borde dual.

Modelo de apego preferencial uniforme (modelo UPA)

El modelo UPA es una variante del modelo de vinculación preferencial (propuesto por Pachon et al.) que tiene en cuenta dos reglas de vinculación diferentes: un mecanismo de vinculación preferencial (con probabilidad 1−p) que hace hincapié en el sistema rico se enriquece, y una elección uniforme (con probabilidad p) para los nodos más recientes. Esta modificación es interesante para estudiar la robustez del comportamiento libre de escala de la distribución de grados. Se demuestra analíticamente que se conserva la distribución asintótica de grados de ley de potencias.

Redes ideales sin escala

En el contexto de la teoría de redes, una red ideal sin escala es una red aleatoria con una distribución de grados que sigue la distribución de densidad del gas ideal sin escala. Estas redes pueden reproducir distribuciones de tamaño de ciudad y resultados electorales al desentrañar la distribución de tamaño de grupos sociales con teoría de la información en redes complejas cuando se aplica a la red un proceso competitivo de crecimiento de conglomerados. En modelos de redes ideales libres de escala es posible demostrar que el número de Dunbar es la causa del fenómeno conocido como los 'seis grados de separación'.

Características novedosas

Para una red sin escala con nodos y exponente de ley de potencia , el subgrafo inducido construido por vértices con grados mayores que es una red sin escala con , casi con seguridad.

Estimación del exponente de la ley de potencia

La estimación del exponente de la ley de potencias de una red sin escala se suele realizar utilizando la estimación de máxima verosimilitud con los grados de unos pocos nodos muestreados uniformemente. Sin embargo, dado que el muestreo uniforme no obtiene suficientes muestras de la importante cola pesada de la distribución de grados de la ley de potencias, este método puede producir un gran sesgo y una varianza. Recientemente se ha propuesto muestrear amigos aleatorios (es decir, extremos aleatorios de enlaces aleatorios) que es más probable que provengan de la cola de la distribución de grados como resultado de la paradoja de la amistad. En teoría, la estimación de máxima verosimilitud con amigos aleatorios conduce a un sesgo y una varianza menores en comparación con el enfoque clásico basado en un muestreo uniforme.