Una red sin escala es una red cuya distribución de grados sigue una ley potencial , al menos asintóticamente. Es decir, la fracción P ( k ) de nodos en la red que tienen k conexiones a otros nodos se aplica a valores grandes de k como
donde es un parámetro cuyo valor suele estar 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. [1] [2] El nombre "sin escala" podría explicarse por el hecho de que algunos momentos de la distribución de grados no están definidos, por lo que la red no tiene una escala o "tamaño" característico.
Se ha informado que muchas redes no tienen escala, aunque el análisis estadístico ha refutado muchas de estas afirmaciones y ha cuestionado seriamente otras. [3] [4] Además, algunos han argumentado que simplemente saber que una distribución de grados tiene cola gruesa es más importante que saber si una red no tiene escala según definiciones estadísticamente rigurosas. [5] [6] El apego preferencial y el modelo de aptitud se han propuesto como mecanismos para explicar distribuciones de grados de leyes de potencia conjeturadas en redes reales. Puede parecer que modelos alternativos, como el vínculo preferencial superlineal y el vínculo preferencial de 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. [7] [8]
En estudios de las redes de citas entre artículos científicos, Derek de Solla Price demostró 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 de esta manera 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, al que llamó "ventaja acumulativa", pero que hoy en día se conoce más comúnmente con el nombre de vínculo preferencial .
El interés reciente por las redes sin escala comenzó en 1999 con el trabajo de Albert-László Barabási y Réka Albert de la Universidad de Notre Dame, quienes mapearon la topología de una parte de la World Wide Web, [9] y descubrieron 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 potencial 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 grados de cola pesada, Barabási y Réka Albert acuñaron el término "red sin escala" para describir la clase de redes que exhiben una distribución de grados 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 pudimos encontrar una red libre de escala entre estos siete ejemplos. Sólo 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 mostraba una caída exponencial para k grande . [10]
Barabási y Réka Albert propusieron un mecanismo generativo para explicar la aparición de distribuciones de leyes de potencia, al que llamaron " vínculo preferencial " y que es esencialmente el mismo que el propuesto por 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 [11] e independientemente por Krapivsky, Redner y Leyvraz, y posteriormente probadas rigurosamente por el matemático Béla Bollobás . [12] Sin embargo, cabe destacar 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. [13]
La historia de las redes sin 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 grados de ley de potencia basada en datos de traceroute ; sin embargo, se ha sugerido que se trata de una ilusión de capa 3 creada por enrutadores, que aparecen como nodos de alto grado mientras ocultan la estructura interna de capa 2 de los AS que interconectan. [14]
A nivel teórico, se han propuesto mejoras a la definición abstracta de libre de escala. Por ejemplo, Li et al. (2005) ofrecieron una "métrica sin escala" potencialmente más precisa. Brevemente, sea G un gráfico con un conjunto de aristas E y denote el grado de un vértice (es decir, el número de aristas incidentes 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 todas las gráficas 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 está "libre de escala". Esta definición captura la noción de autosemejanza implícita en el nombre "sin escala".
Cuando el concepto de "escala libre" se introdujo inicialmente en el contexto de las redes, [9] se refería principalmente a un rasgo específico: una distribución de ley de potencia para una variable determinada , expresada como . Esta propiedad mantiene su forma cuando se somete a una transformación de escala continua , evocando paralelismos con las técnicas de grupos de renormalización en la teoría estadística de campos. [15] [16]
Sin embargo, hay una diferencia clave. En la teoría de campo estadístico, el término "escala" a menudo se refiere al tamaño del sistema. En el ámbito de las redes, la "escala" es una medida de conectividad, generalmente cuantificada por el grado de un nodo, es decir, el número de enlaces conectados a él. Se considera que las redes que presentan un mayor número de nodos de alto grado tienen mayor conectividad.
La distribución de grados de la ley de potencias nos permite hacer afirmaciones "sin escala" sobre la prevalencia de nodos de alto grado. [17] Por ejemplo, podemos decir que "los nodos con el triple de conectividad promedio ocurren con la mitad de frecuencia que los nodos con conectividad promedio". El valor numérico específico de lo que constituye la "conectividad promedio" se vuelve irrelevante, ya sea cien o un millón. [18]
La característica más notable en una red sin escala es la relativa comunidad de vértices con un grado que supera con creces el promedio. Los nodos de mayor grado a menudo se denominan "hubs" y se cree que cumplen propósitos específicos en sus redes, aunque esto depende en gran medida del dominio.
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 centros. Considere una red social en la que los nodos son personas y los enlaces son relaciones de conocimiento entre personas. Es fácil ver que las personas tienden a formar comunidades, es decir, pequeños grupos en los que todos se conocen (se puede pensar en dicha comunidad como un gráfico completo ). Además, los miembros de una comunidad también tienen algunas relaciones de amistad con personas ajenas a esa comunidad. Algunas personas, sin embargo, están conectadas con un gran número de comunidades (por ejemplo, celebridades, políticos). Esas personas pueden considerarse los centros responsables del fenómeno del mundo pequeño .
En la actualidad, las características más específicas de las redes sin escala varían según el mecanismo generativo utilizado para crearlas. Por ejemplo, las redes generadas por unión preferencial generalmente colocan los vértices de alto grado en el medio de la red, conectándolos entre sí para formar un núcleo, con nodos de grado progresivamente más bajos 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 dichas 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. De manera similar, el coeficiente de agrupamiento de redes sin escala puede variar significativamente dependiendo de otros detalles topológicos.
Se ha estudiado ampliamente la cuestión de cómo inmunizar de manera eficiente redes libres a escala que representen redes realistas como Internet y las redes sociales. Una de esas 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 inmunizar. Sin embargo, en muchos casos realistas la estructura global no está disponible y no se conocen los nodos de mayor grado.
Las propiedades del gráfico aleatorio pueden cambiar o permanecer invariantes bajo las transformaciones del 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. [19]
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 sobre técnicas de análisis de datos más rigurosas. [3] Como tal, la comunidad científica todavía debate la naturaleza libre de escala de muchas redes. Algunos ejemplos de redes que se afirma que no tienen escala incluyen:
También se ha encontrado topología libre de escala en superconductores de alta temperatura. [23] 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 vinculadas a las disposiciones fractales de átomos de oxígeno aparentemente aleatorios y a la distorsión de la red. [24]
Recientemente se ha propuesto una estructura celular que llena el espacio, la red estocástica plana ponderada (WPSL), cuya distribución del número de coordinación sigue una ley de potencia. Implica que la red tiene unos pocos bloques que tienen un número sorprendentemente grande de vecinos con quienes 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 continuación, el generador se aplica secuencialmente una y otra vez a sólo uno de los bloques disponibles elegidos preferentemente con respecto a sus áreas. El resultado es la división de la plaza en bloques rectangulares cada vez más pequeños y mutuamente excluyentes. El dual de la WPSL (DWPSL), que se obtiene reemplazando cada bloque con un nodo en su centro, y cada frontera común entre bloques con una arista que une los dos vértices correspondientes, surge como una red cuya distribución de grados sigue una ley potencial. . [25] [26] La razón es que crece siguiendo la regla del modelo de apego impulsado por la mediación que también encarna la regla de apego preferencial pero disfrazada.
Las redes sin escala no surgen sólo por casualidad. Erdős y Rényi (1960) estudiaron un modelo de crecimiento para gráficos 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 sin 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 entrantes atraerá más enlaces entrantes 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 los ricos se vuelven más ricos 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. [27] Para una reseña, consulte el libro de Dorogovtsev y Mendes . [ cita necesaria ] Algunos mecanismos, como la conexión preferencial superlineal y la conexión de segundo vecino, generan redes que no tienen escala transitoriamente, pero se desvían de una ley de potencia a medida que las redes crecen. [7] [8]
Pennock et al. han sugerido un modelo generativo algo diferente para enlaces web. (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 parecía a una distribución normal . Con base en estas observaciones, los autores propusieron un modelo generativo que combina el apego preferencial con una probabilidad base de obtener un vínculo.
Otro modelo generativo es el modelo de copia estudiado por Kumar et al. [28] (2000), en el que nuevos nodos eligen un nodo existente al azar y copian una fracción de los enlaces del nodo existente. Esto también genera una ley de potencia.
Hay dos componentes principales que explican el surgimiento de la distribución de la ley de potencias en el modelo de Barabási-Albert : el crecimiento y el vínculo preferencial. [29] Por "crecimiento" se entiende un proceso de crecimiento en el que, durante un período prolongado de tiempo, 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 en 10 años). Finalmente, por "conexión preferencial" se entiende que los nuevos nodos prefieren conectarse a nodos que ya tienen un gran número de enlaces con otros. Por lo tanto, existe una mayor probabilidad de que cada vez más nodos se vinculen a aquel que ya tiene muchos enlaces, llevando a este nodo a un centro infinito . [9] Dependiendo de la red, los centros pueden ser selectivos o desasortativos. La variabilidad se encontraría en las redes sociales en las que las personas famosas o bien conectadas tenderían a conocerse mejor entre sí. La desasortatividad se encontraría en redes tecnológicas (Internet, World Wide Web) y biológicas (interacción de proteínas, metabolismo). [29]
Sin embargo, el crecimiento de las redes (agregar nuevos nodos) no es una condición necesaria para crear una red sin escala (ver Dangalchev [30] ). 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 los vértices (fitness), resulta que en algunas circunstancias también las redes estáticas desarrollan propiedades sin escala.
Ha habido una explosión de actividad en el modelado de redes complejas sin escala . La receta de Barabási y Albert [31] ha sido seguida por varias variaciones y generalizaciones [32] [33] [34] [35] [27] y la renovación de trabajos matemáticos anteriores. [36]
En términos actuales, si una red compleja tiene una distribución de ley de potencia de cualquiera de sus métricas, generalmente se considera una red sin escala. De manera similar, cualquier modelo con esta característica se denomina modelo sin escala. [17]
Muchas redes reales no tienen escala (aproximadamente) 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 . Normalmente nos concentramos en hacer crecer la red, es decir, agregar nodos.
2. Adjunto preferencial : la probabilidad de que nuevos nodos se conecten al nodo "antiguo".
Tenga en cuenta que algunos modelos (consulte Dangalchev [30] y el modelo Fitness a continuación) también pueden funcionar de forma estática, sin cambiar el número de nodos. También debe tenerse en cuenta que el hecho de que los modelos de "vínculo preferencial" den lugar a redes sin escala no prueba que éste sea el mecanismo subyacente a la evolución de las redes sin escala en el mundo real, ya que pueden existir diferentes mecanismos a nivel funcionan en sistemas del mundo real que, sin embargo, dan lugar a escalamiento.
Ha habido varios intentos de generar propiedades de red sin escala. Aquí hay unos ejemplos:
El modelo Barabási-Albert , una versión no dirigida del modelo de Price, tiene un vínculo preferencial lineal y agrega un nuevo nodo en cada paso de tiempo.
(Tenga en cuenta 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 conecte a un nodo aislado. Por lo tanto, en general tiene la forma , donde es el atractivo inicial del nodo).
Dangalchev (ver [30] ) construye un modelo 2-L considerando la importancia de cada uno de los vecinos de un nodo objetivo en la conexión preferencial. El atractivo de un nodo en el modelo 2-L depende no sólo 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 segundo nodo vecino contribuyen por igual al atractivo de un nodo objetivo, demuestra el surgimiento de redes transitorias sin escala. [8] En el modelo k2, la distribución de grados parece aproximadamente libre de escala siempre que la red sea relativamente pequeña, pero surgen desviaciones significativas del régimen libre de escala a medida que la red crece. Esto da como resultado que el atractivo relativo de los nodos con diferentes grados cambie con el tiempo, una característica que también se observa en las redes reales.
En el modelo de adjunto impulsado por mediación (MDA) , un nuevo nodo que viene con bordes selecciona al azar un nodo conectado existente 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 la inversa de la media armónica (IHM) de 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 mayores sean los vínculos (grado) que tenga un nodo, mayores serán sus posibilidades de obtener más vínculos, ya que se puede llegar a ellos de un mayor número de maneras a través de mediadores, lo que esencialmente encarna la idea intuitiva del mecanismo de que los ricos se hacen más ricos (o el mecanismo preferencial). regla de apego del modelo Barabasi-Albert). Por lo tanto, se puede ver que la red MDA sigue la regla de la PA, pero disfrazada. [37]
Sin embargo, describe el mecanismo del ganador se lo lleva todo, ya que encontramos que casi del total de nodos tiene grado uno y el uno es súper rico en grado. A medida que el valor aumenta, la disparidad entre los súper ricos y los pobres disminuye y a medida que encontramos una transición de un mecanismo de transición de ricos que se vuelven súper ricos a ricos que se vuelven más ricos.
El modelo de Barabási-Albert supone que la probabilidad de que un nodo se una a un nodo es proporcional al grado del nodo . Este supuesto implica dos hipótesis: primero, que depende de , en contraste con los gráficos aleatorios en los cuales , y segundo, que la forma funcional de es lineal en .
En la vinculación 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 [34] demuestran que la naturaleza libre de escala de la red se destruye por el vínculo preferencial no lineal. El único caso en el que la topología de la red es libre de escala es aquel en el que el vínculo preferencial es asintóticamente lineal, es decir, como . En este caso la ecuación de tasa conduce a
De esta manera, el exponente de la distribución de grados se puede ajustar a cualquier valor entre 2 y . [ se necesita aclaración ]
Los modelos de red jerárquicos son, por diseño, escalables y tienen una alta agrupación de nodos. [38]
La construcción iterativa conduce a una red jerárquica. A partir de un grupo de cinco nodos completamente conectado, creamos cuatro réplicas idénticas que conectan los nodos periféricos de cada grupo con el nodo central del grupo original. 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.
La idea es que el enlace entre dos vértices se asigne de forma no aleatoria con una probabilidad p igual para todo el par de vértices. Más bien, para cada vértice j existe una aptitud intrínseca x j y se crea un vínculo entre los vértices i y j con una probabilidad . [39] En el caso de World Trade Web es posible reconstruir todas las propiedades utilizando como aptitudes del país su PIB, y tomando
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énea simplemente refleja la curvatura negativa y las propiedades métricas de la geometría hiperbólica subyacente. [41]
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 y coeficientes de agrupamiento mucho más altos aplicando una transformación de borde dual. [19]
El modelo UPA es una variante del modelo de apego preferencial (propuesto por Pachon et al.) que tiene en cuenta dos reglas de apego diferentes: un mecanismo de apego preferencial (con probabilidad 1-p) que enfatiza que los ricos se hacen más ricos 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 de grados asintóticamente según la ley de potencias. [27]
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 son capaces de reproducir distribuciones de tamaño de ciudades 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 de crecimiento de conglomerados competitivo. [42] [43] En modelos de redes ideales sin escala es posible demostrar que el número de Dunbar es la causa del fenómeno conocido como los ' seis grados de separación '.
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 . [44]
La estimación del exponente de la ley de potencia de una red sin escala generalmente se realiza utilizando la estimación de máxima verosimilitud con los grados de unos pocos nodos muestreados uniformemente. [3] 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 potencial, este método puede producir un gran sesgo y una varianza. Recientemente se ha propuesto muestrear amigos aleatorios (es decir, extremos aleatorios de vínculos aleatorios) que probablemente provengan de la cola de la distribución de grados como resultado de la paradoja de la amistad . [45] [46] Teóricamente, la estimación de máxima verosimilitud con amigos aleatorios conduce a un sesgo y una varianza más pequeños en comparación con el enfoque clásico basado en un muestreo uniforme. [46]