Hispanopedia Wiki
Articulo de referencia

Red libre de escala

Distribución de grados para una red con 150 000 vértices y grado medio = 6, creada mediante el modelo de Barabási-Albert (puntos azules). La distribución sigue una forma analíti...

Hispanopedia WikiContenido en espanolLectura gratuita
Distribución de grados para una red con 150 000 vértices y grado medio = 6, creada mediante el modelo de Barabási-Albert (puntos azules). La distribución sigue una forma analítica dada por la razón de dos funciones gamma (línea negra), que se aproxima a una ley de potencias.

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

PAG(k) ∼ k−γ{\displaystyle P(k)\ \sim \ k^{\boldsymbol {-\gamma }}}

dóndeγ{\displaystyle \gamma }es un parámetro cuyo valor suele estar en el rango2<γ<3{\textstyle 2<\gamma <3}(en el que el segundo momento ( parámetro de escala ) dek−γ{\displaystyle k^{\boldsymbol {-\gamma }}}es infinito pero el primer momento es finito), aunque ocasionalmente puede estar fuera de estos límites. [ 1 ] [ 2 ] El nombre "libre de escala" podría explicarse por el hecho de que algunos momentos de la distribución de grados no están definidos, de modo que la red no tiene una escala o "tamaño" característico.

Se han propuesto el acoplamiento preferencial y el modelo de aptitud como mecanismos para explicar las distribuciones de grado de ley de potencias en redes reales. Modelos alternativos como el acoplamiento preferencial superlineal y el acoplamiento preferencial de segundo vecino pueden generar redes transitorias libres de escala, pero la distribución de grado se desvía de una ley de potencias a medida que las redes se vuelven muy grandes. [ 3 ] [ 4 ]

Historia

En estudios sobre citas entre artículos científicos, Derek de Solla Price demostró en 1965 que el número de citas que recibe un artículo presenta una distribución de cola pesada que sigue una distribución de Pareto o ley de potencias . En un artículo posterior, de 1976, Price también propuso un mecanismo para explicar la aparición de leyes de potencias en redes de citas, al que denominó "ventaja acumulativa". Sin embargo, en ambos casos, las citas tratadas son cantidades escalares, en lugar de una característica fundamental de una nueva clase de redes.

El interés por las redes libres de escala comenzó en 1999 con el trabajo de Albert-László Barabási y Réka Albert en la Universidad de Notre Dame, quienes mapearon la topología de una parte de la World Wide Web, [ 5 ] descubriendo 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 conectaban a un nodo. En un artículo posterior [ 6 ] , Barabási y Albert demostraron que las leyes de potencias no son una propiedad exclusiva de la WWW, sino que la característica está presente en algunas redes reales, lo que los llevó a acuñar el término "red libre de escala" para describir la clase de redes que exhiben una distribución de grados de ley de potencias.

Barabási y Réka Albert propusieron un mecanismo generativo [ 6 ] para explicar la aparición de distribuciones de ley de potencias, al que denominaron " adjunto preferencial ". Dorogovtsev, Mendes y Samukhin [ 7 ] presentaron soluciones analíticas para este mecanismo en 2000, y posteriormente Krapivsky, Redner y Leyvraz lo hicieron de forma independiente, siendo luego demostrado rigurosamente por el matemático Béla Bollobás [ 8 ] .

Descripción general

Cuando el concepto de "libre de escala" se introdujo inicialmente en el contexto de las redes, [ 6 ] se refería principalmente a una característica específica: una distribución de ley de potencias para una variable dada.k{\displaystyle k}, expresado comoF(k)∝k−γ{\displaystyle f(k)\propto k^{-\gamma }}Esta propiedad mantiene su forma cuando se somete a una transformación de escala continua.k→k+ϵk{\displaystyle k\to k+\epsilon k}, evocando paralelismos con las técnicas del grupo de renormalización en la teoría estadística de campos. [ 9 ] [ 10 ]

Sin embargo, hay una diferencia clave. En la teoría estadística de campos, el término "escala" a menudo se refiere al tamaño del sistema. En el ámbito de las redes, "escala"k{\displaystyle k}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 con un mayor número de nodos de alto grado tienen mayor conectividad.

La distribución de grados de ley de potencias nos permite hacer afirmaciones "sin escala" sobre la prevalencia de nodos de alto grado. [ 11 ] Por ejemplo, podemos decir que "los nodos con el triple de la conectividad promedio aparecen 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. [ 12 ]

Características

Red aleatoria (a) y red libre de escala (b)
Distribución compleja del grado de red de elementos aleatorios y libres de escala

La característica más notable en una red libre de escala es la relativa frecuencia de vértices con un grado que supera ampliamente el promedio. Los nodos de mayor grado suelen denominarse "hubs" y se cree que cumplen funciones específicas en sus redes, aunque esto depende en gran medida del dominio. En una red aleatoria, el grado máximo, o el hub más grande esperado, escala como k max ~ log N , donde N es el tamaño de la red, una dependencia muy lenta. En contraste, en las redes libres de escala, el hub más grande escala como k max ~ ~N 1/(γ−1), lo que indica que los hubs aumentan polinómicamente con el tamaño de la red.

Una característica clave de las redes libres de escala es su alta heterogeneidad de grado, κ = <k² > /<k> , que rige múltiples procesos basados ​​en la red, desde la robustez de la red hasta la propagación de epidemias y la sincronización de la red. Mientras que para una red aleatoria κ = <k> + 1, es decir, la proporción es independiente del tamaño de la red N , para una red libre de escala tenemos κ ~ N (3−γ)/(γ−1) , que aumenta con el tamaño de la red, lo que indica que para estas redes la heterogeneidad de grado aumenta.

Agrupación

Otra característica importante de las redes libres de 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 potencias. Esto implica que los nodos de bajo grado pertenecen a subgrafos muy densos y que estos subgrafos están conectados entre sí a través de nodos centrales. Consideremos una red social en la que los nodos son personas y los enlaces son relaciones de conocimiento entre ellas. 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 grafo completo ). Además, los miembros de una comunidad también tienen algunas relaciones de conocimiento con personas fuera de esa comunidad. Sin embargo, algunas personas están conectadas a un gran número de comunidades (por ejemplo, celebridades, políticos). Estas personas pueden considerarse los nodos centrales responsables del fenómeno del mundo pequeño .

Actualmente, 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 mediante conexión preferencial suelen ubicar los vértices de alto grado en el centro, conectándolos para formar un núcleo, mientras que los nodos de grado progresivamente menor conforman las regiones entre el núcleo y la periferia. La eliminación aleatoria, incluso de 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 libres de escala, que ubican los vértices de alto grado en la periferia, no presentan estas propiedades. De manera similar, el coeficiente de agrupamiento de las redes libres de escala puede variar significativamente según otros detalles topológicos.

Inmunización

La cuestión de cómo inmunizar eficientemente las redes libres de escala que representan redes realistas como Internet y las redes sociales se ha estudiado ampliamente. Una de estas estrategias es inmunizar los nodos de mayor grado, es decir, ataques dirigidos (intencionales) ya que para este caso pdo{\displaystyle c}es relativamente alto y se necesitan menos nodos para inmunizar. Sin embargo, en muchos casos reales, la estructura global no está disponible y se desconocen los nodos de mayor grado.

Las propiedades de un grafo aleatorio pueden cambiar o permanecer invariables bajo transformaciones de grafos. Mashaghi A. et al., por ejemplo, demostraron que una transformación que convierte grafos aleatorios en sus grafos duales de aristas (o grafos de líneas) produce un conjunto de grafos con una distribución de grados casi idéntica, pero con correlaciones de grado y un coeficiente de agrupamiento significativamente mayor. Los grafos libres de escala, como tales, permanecen libres de escala bajo dichas transformaciones. [ 13 ]

Ejemplos

Algunos ejemplos de redes que se han encontrado libres de escala son:

También se ha encontrado topología libre de escala en superconductores de alta temperatura. [ 18 ] 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 vinculadas a las disposiciones fractales de átomos de oxígeno aparentemente aleatorios y a la distorsión de la red. [ 19 ]

Modelos generativos

Las redes libres de escala no surgen por mera casualidad. Erdős y Rényi (1960) estudiaron un modelo de crecimiento para grafos en el que, en cada paso, se eligen dos nodos al azar y se inserta un enlace entre ellos. Las propiedades de estos grafos aleatorios difieren de las que se encuentran en las redes libres de escala, por lo que 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 "los ricos se hacen más ricos" 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 al grado de entrada actual de las páginas web. Según este proceso, una página con muchos enlaces de entrada atraerá más enlaces de entrada que una página regular. Esto genera una ley de potencias, pero el grafo resultante difiere del grafo 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, Pachon et al. (2018) propusieron una variante del modelo generativo "los ricos se hacen más ricos " que tiene en cuenta dos reglas de conexión diferentes: un mecanismo de conexión preferencial y una elección uniforme solo para los nodos más recientes. [ 20 ] Para una revisión, véase el libro de Dorogovtsev y Mendes . Algunos mecanismos, como la conexión preferencial superlineal y la conexión de segundos vecinos, generan redes que son transitoriamente libres de escala, pero se desvían de una ley de potencias a medida que las redes crecen. [ 3 ] [ 4 ]

Pennock et al. (2002) propusieron un modelo generativo algo diferente para los enlaces web. Analizaron comunidades con intereses en temas específicos, como las páginas de inicio de universidades, empresas públicas, periódicos o científicos, y descartaron los principales nodos de la web. En este caso, la distribución de enlaces dejó de seguir una ley de potencias y se asemejó a una distribución normal . Basándose en estas observaciones, los autores propusieron un modelo generativo que combina la vinculación preferencial con una probabilidad base de obtener un enlace.

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

Hay dos componentes principales que explican la aparición de la distribución de ley de potencias en el modelo de Barabási-Albert : el crecimiento y la conexión preferencial. [ 22 ] Por "crecimiento" se entiende un proceso de crecimiento donde, durante un período 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 en 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, hay una mayor probabilidad de que cada vez más nodos se conecten a aquel que ya tiene muchos enlaces, llevando a este nodo a convertirse en un hub . [ 6 ] Dependiendo de la red, los hubs pueden ser asociativos o disasortativos. La asociatividad se encontraría en redes sociales en las que las personas bien conectadas/famosas tenderían a conocerse mejor entre sí. La disasortatividad se encontraría en redes tecnológicas (Internet, World Wide Web) y biológicas (interacción de proteínas, metabolismo). [ 22 ]

Sin embargo, el crecimiento de las redes (la adición de nuevos nodos) no es una condición necesaria para crear una red libre de escala (véase Dangalchev [ 23 ] ). Una posibilidad (Caldarelli et al. 2002) es considerar la estructura como estática y establecer un vínculo entre los vértices según una propiedad particular de los dos vértices involucrados. Una vez especificada la distribución estadística de estas propiedades de los vértices (aptitudes), se observa que, en algunas circunstancias, incluso las redes estáticas desarrollan propiedades libres de escala.

Modelo generalizado libre de escala

Se ha producido un auge de actividad en el modelado de redes complejas libres de escala . La receta de Barabási y Albert [ 24 ] ha sido seguida por varias variaciones y generalizaciones [ 25 ] [ 26 ] [ 27 ] [ 28 ] [ 20 ] y la revisión de trabajos matemáticos previos. [ 29 ]

En términos actuales, si una red compleja tiene una distribución de ley de potencias en cualquiera de sus métricas, generalmente se considera una red libre de escala. De manera similar, cualquier modelo con esta característica se denomina modelo libre de escala. [ 11 ]

Características

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

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

2. Adhesión preferencial : La probabilidadΠ{\displaystyle \Pi }que los nuevos nodos se conectarán al nodo "antiguo".

Cabe señalar que algunos modelos (véase Dangalchev [ 23 ] y el modelo de aptitud más adelante) también pueden funcionar de forma estática, sin modificar el número de nodos. Asimismo, conviene tener en cuenta que el hecho de que los modelos de "conexión preferencial" den lugar a redes libres de escala no prueba que este sea el mecanismo subyacente a la evolución de las redes libres de escala del mundo real, ya que podrían existir otros mecanismos en funcionamiento en los sistemas del mundo real que, no obstante, den lugar a la escalabilidad.

Ejemplos

Se han realizado varios intentos para generar propiedades de red libres de escala. Aquí hay algunos ejemplos:

El modelo de Barabási-Albert

El modelo de Barabási-Albert , una versión no dirigida del modelo de Price, tiene una afiliación preferencial lineal.Π(ki)=ki∑jkj{\displaystyle \Pi (k_{i})={\frac {k_{i}}{\sum _{j}k_{j}}}}y agrega un nuevo nodo en cada paso de tiempo.

(Nota: otra característica general deΠ(k){\displaystyle \Pi (k)}en redes reales es queΠ(0)≠0{\displaystyle \Pi (0)\neq 0}, es decir, existe una probabilidad distinta de cero de que un nuevo nodo se conecte a un nodo aislado. Por lo tanto, en generalΠ(k){\displaystyle \Pi (k)}tiene la formaΠ(k)=A+kα{\displaystyle \Pi (k)=A+k^{\alpha }}, dóndeA{\displaystyle A}es el atractivo inicial del nodo.)

Modelo de red de dos niveles

Dangalchev (véase [ 23 ] ) 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 solo del número de nodos conectados a él, sino también del número de enlaces en cada uno de estos nodos.

Π(ki)=ki+do∑(i,j)kj∑jkj+do∑jkj2,{\displaystyle \Pi (k_{i})={\frac {k_{i}+C\sum _{(i,j)}k_{j}}{\sum _{j}k_{j}+C\sum _{j}k_{j}^{2}}},}

donde C es un coeficiente entre 0 y  1.

Una variante del modelo 2-L, el modelo k2, donde los nodos vecinos de primer y segundo orden contribuyen por igual al atractivo de un nodo objetivo, demuestra la aparición de redes transitorias libres de escala. [ 4 ] En el modelo k2, la distribución de grados parece aproximadamente libre de escala mientras la red es 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 redes reales.

Adhesión preferencial no lineal

El modelo Barabási-Albert supone que la probabilidadΠ(k){\displaystyle \Pi (k)}que un nodo se conecta a otro nodoi{\displaystyle i}es proporcional al gradok{\displaystyle k}del nodoi{\displaystyle i}. Esta suposición implica dos hipótesis: primero, queΠ(k){\displaystyle \Pi (k)}depende dek{\displaystyle k}, en contraste con los gráficos aleatorios en los queΠ(k)=pag{\displaystyle \Pi (k)=p}y segundo, que la forma funcional deΠ(k){\displaystyle \Pi (k)}es lineal enk{\displaystyle k}.

En el apego preferencial no lineal, la forma deΠ(k){\displaystyle \Pi (k)}no es lineal, y estudios recientes han demostrado que la distribución de grados depende fuertemente de la forma de la función.Π(k){\displaystyle \Pi (k)}

Krapivsky, Redner y Leyvraz [ 27 ] demuestran que la naturaleza libre de escala de la red se destruye para la conexión preferencial no lineal. El único caso en el que la topología de la red es libre de escala es aquel en el que la conexión preferencial es asintóticamente lineal, es decirΠ(ki)∼a∞ki{\displaystyle \Pi (k_{i})\sim a_{\infty }k_{i}}comoki→∞{\displaystyle k_{i}\to \infty }En este caso, la ecuación de velocidad conduce a

PAG(k)∼k−γ con γ=1+μa∞.{\displaystyle P(k)\sim k^{-\gamma }{\text{ with }}\gamma =1+{\frac {\mu }{a_{\infty }}}.}

De esta forma, el exponente de la distribución de grados se puede ajustar a cualquier valor entre 2 y∞{\displaystyle \infty }.

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. [ 30 ]

La construcción iterativa da lugar 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. De esta forma, 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 una se conectan al nodo central de los nodos creados en el primer paso. Esto da como resultado N  =  125, y el proceso puede continuar indefinidamente.

Modelo de fitness

La idea es que el vínculo entre dos vértices no se asigna aleatoriamente con una probabilidad p igual para cada par de vértices. Más bien, para cada vértice j hay una aptitud intrínseca x j y se crea un vínculo entre los vértices i y j con una probabilidad pag(incógnitai,incógnitaj){\displaystyle p(x_{i},x_{j})}. [ 31 ] En el caso de World Trade Web es posible reconstruir todas las propiedades utilizando como aptitudes del país su PIB y tomando

pag(incógnitai,incógnitaj)=δincógnitaiincógnitaj1+δincógnitaiincógnitaj.{\displaystyle p(x_{i},x_{j})={\frac {\delta x_{i}x_{j}}{1+\delta x_{i}x_{j}}}.}[ 32 ]

Gráficas geométricas hiperbólicas

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

Transformación dual de aristas para generar grafos libres de escala con las propiedades deseadas.

Partiendo de grafos libres de escala con baja correlación de grado y coeficiente de agrupamiento, se pueden generar nuevos grafos con correlaciones de grado y coeficientes de agrupamiento mucho mayores aplicando una transformación de dualidad de aristas. [ 13 ]

Modelo de fijación preferencial uniforme (modelo UPA)

El modelo UPA es una variante del modelo de conexión preferencial (propuesto por Pachon et al.) que considera dos reglas de conexión diferentes: un mecanismo de conexión preferencial (con probabilidad 1−p) que enfatiza el sistema de 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 de ley de potencias. [ 20 ]

Redes ideales sin escala

En el contexto de la teoría de redes, una red ideal libre de escala es una red aleatoria con una distribución de grados que sigue la distribución de densidad de gas ideal libre de escala . Estas redes pueden reproducir distribuciones de tamaño de ciudades y resultados electorales al desentrañar la distribución de tamaño de grupos sociales con la teoría de la información en redes complejas cuando se aplica un proceso de crecimiento de clústeres competitivos a la red. [ 34 ] [ 35 ] 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 libre de escala connorte{\displaystyle n}nodos y exponente de ley de potenciasγ>3{\displaystyle \gamma >3}, el subgrafo inducido construido por vértices con grados mayores queregistro⁡norte×registro∗⁡norte{\displaystyle \log {n}\times \log ^{*}{n}}es una red libre de escala conγ′=2{\displaystyle \gamma '=2}, casi con seguridad . [ 36 ]

La métrica libre de escala

A nivel teórico, se han propuesto refinamientos a la definición abstracta de escala libre. Por ejemplo, Li et al. (2005) ofrecieron una "métrica de escala libre" potencialmente más precisa. Brevemente, sea G un grafo con conjunto de aristas E , y denotemos el grado de un vértice.v{\displaystyle v}(es decir, el número de aristas incidentes av{\displaystyle v}) porgrados⁡(v){\displaystyle \deg(v)}. Definir

s(GRAMO)=∑(tú,v)∈migrados⁡(tú)⋅grados⁡(v).{\displaystyle s(G)=\sum _{(u,v)\in E}\deg(u)\cdot \deg(v).}

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

S(GRAMO)=s(GRAMO)smáximo,{\displaystyle S(G)={\frac {s(G)}{s_{\max }}},}

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

Estimación del exponente de la ley de potencias

Estimación del exponente de la ley de potenciasγ{\displaystyle \gamma }La estimación de una red libre de escala se realiza típicamente mediante la estimación de máxima verosimilitud con los grados de unos pocos nodos muestreados uniformemente. [ 37 ] Sin embargo, dado que el muestreo uniforme no obtiene suficientes muestras de la importante cola pesada de la distribución de grados de 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 tienen más probabilidades de provenir de la cola de la distribución de grados como resultado de la paradoja de la amistad . [ 38 ] [ 39 ] Teóricamente, 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 el muestreo uniforme. [ 39 ]

No todas las redes son escalables.

La propiedad generalizada de la invariancia de escala en sistemas sociales, biológicos y tecnológicos no implica que todas las redes reales sean invariantes de escala. De hecho, varias redes importantes no comparten esta propiedad, como las redes presentes en la ciencia de los materiales, que describen los enlaces entre los átomos en materiales cristalinos o amorfos. En estas redes, cada nodo tiene el mismo grado, determinado químicamente. Asimismo, se ha demostrado que la red neuronal del gusano C. elegans y la red eléctrica, compuesta por generadores e interruptores conectados por líneas de transmisión, presentan distribuciones de grado exponenciales. Además, en algunas redes del mundo real, la invariancia de escala puede ser mayor o menor. Por ejemplo, las redes sociales tienden a ser débilmente invariantes de escala, mientras que algunas redes tecnológicas y biológicas pueden ser fuertemente invariantes de escala. [ 40 ]

Véase también

Referencias

  1. ↑ Onnela, J.-P.; Saramaki, J.; Hyvonen, J.; Szabo, G.; Lazer, D.; Kaski, K.; Kertesz, J.; Barabasi, A. -L. (2007). "Estructura y fuerza de los enlaces en redes de comunicación móvil" . Actas de la Academia Nacional de Ciencias . 104 (18): 7332– 7336. arXiv : physics/0610104 . Bibcode : 2007PNAS..104.7332O . doi : 10.1073/pnas.0610245104 . PMC 1863470. PMID 17456605 .  
  2. ↑ Choromański, K.; Matuszak, M.; MiȩKisz, J. (2013). "Grafo libre de escala con conexión preferencial y estructura interna de vértices en evolución" . Journal of Statistical Physics . 151 (6): 1175– 1183. Bibcode : 2013JSP...151.1175C . doi : 10.1007/s10955-013-0749-1 .
  3. 1 2 Krapivsky, Paul; Krioukov, Dmitri (21 de agosto de 2008). "Redes libres de escala como regímenes preasintóticos de conexión preferencial superlineal". Physical Review E . 78 (2) 026114. arXiv : 0804.1366 . Bibcode : 2008PhRvE..78b6114K . doi : 10.1103/PhysRevE.78.026114 . PMID 18850904 . S2CID 14292535 .  
  4. 1 2 3 Falkenberg, Max; Lee, Jong-Hyeok; Amano, Shun-ichi; Ogawa, Ken-ichiro; Yano, Kazuo; Miyake, Yoshihiro; Evans, Tim S.; Christensen, Kim (18 de junio de 2020). "Identificación de la dependencia temporal en el crecimiento de la red" . Physical Review Research . 2 (2) 023352. arXiv : 2001.09118 . Bibcode : 2020PhRvR...2b3352F . doi : 10.1103/PhysRevResearch.2.023352 .
  5. ^ Alberto, Réka; Jeong, Hawoong; Barabási, Albert-László (9 de septiembre de 1999). "Diámetro de la World-Wide Web" . Naturaleza . 401 (6749): 130– 131. arXiv : cond-mat/9907038 . doi : 10.1038/43601 . ISSN 1476-4687 . 
  6. 1 2 3 4 Barabási, Albert-László ; Alberto, Réka. (15 de octubre de 1999). "Aparición del escalado en redes aleatorias". Ciencia . 286 (5439): 509– 512. arXiv : cond-mat/9910332 . Código Bib : 1999Sci...286..509B . doi : 10.1126/ciencia.286.5439.509 . SEÑOR 2091634 . PMID 10521342 . S2CID 524106 .   
  7. ↑ Dorogovtsev, S.; Mendes, J.; Samukhin, A. (2000). "Estructura de redes en crecimiento con enlaces preferenciales". Physical Review Letters . 85 (21): 4633– 4636. arXiv : cond-mat/0004434 . Bibcode : 2000PhRvL..85.4633D . doi : 10.1103/PhysRevLett.85.4633 . PMID 11082614 . S2CID 118876189 .  
  8. ↑ Bollobás, B .; Riordan, O.; Spencer, J.; Tusnády, G. (2001). "La secuencia de grados de un proceso de grafo aleatorio libre de escala". Random Structures and Algorithms . 18 (3): 279– 290. doi : 10.1002/rsa.1009 . MR 1824277. S2CID 1486779 .  
  9. ↑ Itzykson, Claude; Drouffe, Jean-Michel (1989). Teoría estadística de campos: Volumen 1, Del movimiento browniano a la renormalización y la teoría de gauge reticular (1.ª ed.). Nueva York: Cambridge University Press. ISBN  978-0-521-34058-8.
  10. ↑ Itzykson, Claude; Drouffe, Jean-Michel (1989). Teoría estadística de campos: Volumen 2, Acoplamiento fuerte, métodos de Monte Carlo, teoría de campos conformes y sistemas aleatorios (1.ª ed.). Nueva York: Cambridge University Press. ISBN  978-0-521-37012-7.
  11. 1 2 Meng, Xiangyi; Zhou, Bin (2023). "Redes libres de escala más allá de la distribución de grado de ley de potencias". Chaos, Solitons & Fractals . 176 114173. arXiv : 2310.08110 . Bibcode : 2023CSF...17614173M . doi : 10.1016/j.chaos.2023.114173 . S2CID 263909425 . 
  12. ↑ Tanaka, Reiko (2005). "Redes metabólicas ricas en escalas". Phys. Rev. Lett . 94 (16) 168101. Bibcode : 2005PhRvL..94p8101T . doi : 10.1103/PhysRevLett.94.168101 . PMID 15904266 . 
  13. 1 2 Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003). "Generación de redes correlacionadas a partir de redes no correlacionadas". Phys. Rev. E . 67 (4) 046107. arXiv : cond-mat/0212469 . Bibcode : 2003PhRvE..67d6107R . doi : 10.1103/PhysRevE.67.046107 . PMID 12786436 . S2CID 33054818 .  
  14. ↑ T. Mens (2016). "Tendencias de investigación en complejidad estructural del software". arXiv : 1608.01533 [ cs.SE ].
  15. ↑ De Masi, Giulia; et al. (2006). "Modelo de aptitud para el mercado monetario interbancario italiano". Physical Review E . 74 (6) 066112. arXiv : physics/0610108 . Bibcode : 2006PhRvE..74f6112D . doi : 10.1103/PhysRevE.74.066112 . PMID 17280126 . S2CID 30814484 .   
  16. ↑ Soramäki, Kimmo; et al. (2007). "La topología de los flujos de pagos interbancarios". Physica A: Mecánica estadística y sus aplicaciones . 379 (1): 317– 333. Bibcode : 2007PhyA..379..317S . doi : 10.1016/j.physa.2006.11.093 . hdl : 10419/60649 . 
  17. ↑ Steyvers, Mark; Joshua B. Tenenbaum (2005). "La estructura a gran escala de las redes semánticas: análisis estadísticos y un modelo de crecimiento semántico". Cognitive Science . 29 (1): 41– 78. arXiv : cond-mat/0110012 . doi : 10.1207/s15516709cog2901_3 . PMID 21702767. S2CID 6000627 .  
  18. ↑ Fratini, Michela; Poccia, Nicola; Ricci, Alejandro; Campi, Gaetano; Burghammer, Manfred; Aeppli, Gabriel; Bianconi, Antonio (2010). "Organización estructural libre de escala de intersticiales de oxígeno en La2CuO4+y". Naturaleza . 466 (7308): 841– ​​4. arXiv : 1008.2015 . Código Bib : 2010Natur.466..841F . doi : 10.1038/naturaleza09260 . PMID 20703301 . S2CID 4405620 .  
  19. ↑ Poccia, Nicola; Ricci, Alejandro; Campi, Gaetano; Fratini, Michela; Puri, Alejandro; Di Gioacchino, Daniele; Marcelli, Augusto; Reynolds, Michael; Burghammer, Manfred; Saini, Naurang L.; Aeppli, Gabriel; Bianconi, Antonio (2012). "Óptima falta de homogeneidad de las distorsiones de la red local en La2CuO4+y" . PNAS . 109 (39): 15685–15690 . arXiv : 1208.0101 . Código Bib : 2012PNAS..10915685P . doi : 10.1073/pnas.1208492109 . PMC 3465392 . PMID 22961255 .  
  20. 1 2 3 Pachon, Angelica; Sacerdote, Laura; Yang, Shuyi (2018). "Comportamiento libre de escala de redes con la copresencia de reglas de conexión preferenciales y uniformes". Physica D: Nonlinear Phenomena . 371 : 1– 12. arXiv : 1704.08597 . Bibcode : 2018PhyD..371....1P . doi : 10.1016/j.physd.2018.01.005 . S2CID 119320331 . 
  21. ↑ Kumar, Ravi; Raghavan, Prabhakar (2000). Modelos estocásticos para el grafo web (PDF) . Fundamentos de la informática, 41.º simposio anual sobre. págs. 57–65 . doi : 10.1109/SFCS.2000.892065 . Archivado (PDF) del original el 3 de marzo de 2016. Recuperado el 10 de febrero de 2016 . 
  22. 1 2 Barabási, Albert-László ; Zoltán N., Oltvai. (2004). "Biología de redes: comprensión de la organización funcional de la célula". Naturaleza Reseñas Genética . 5 (2): 101– 113. doi : 10.1038/nrg1272 . PMID 14735121 . S2CID 10950726 .  
  23. 1 2 3 Dangalchev, Chavdar (julio de 2004). "Modelos de generación para redes libres de escala" . Physica A: Mecánica estadística y sus aplicaciones . 338 ( 3–4 ): 659–671 . Bibcode : 2004PhyA..338..659D . doi : 10.1016/j.physa.2004.01.056 .
  24. ^ Barabási, A.-L. y R. Albert, Science 286 , 509 (1999).
  25. ^ R. Albert y AL Barabási, Phys. Rev. Lett. 85 , 5234 (2000).
  26. ^ SN Dorogovtsev, JFF Mendes y AN Samukhim, cond-mat/0011115.
  27. 1 2 P.L. Krapivsky, S. Redner y F. Leyvraz, Phys. Rev. Lett. 85 , 4629 (2000).
  28. ↑ B. Tadic, Physica A 293 , 273(2001).
  29. ↑ S. Bomholdt y H. Ebel, cond-mat/0008465; HA Simon, Bimetrika 42 , 425 (1955).
  30. ↑ Ravasz, E.; Barabási (2003). "Organización jerárquica en redes complejas". Física. Rev. E. 67 (2) 026112. arXiv : cond-mat/0206130 . Código Bib : 2003PhRvE..67b6112R . doi : 10.1103/physreve.67.026112 . PMID 12636753 . S2CID 17777155 .  
  31. ↑ Caldarelli, G.; et al. (2002). "Redes libres de escala a partir de la aptitud intrínseca variable de los vértices" (PDF) . Phys. Rev. Lett . 89 (25) 258702. Bibcode : 2002PhRvL..89y8702C . doi : 10.1103/physrevlett.89.258702 . PMID 12484927 .  
  32. ↑ Garlaschelli, D.; et al. (2004). "Propiedades topológicas dependientes de la aptitud de la red del comercio mundial". Phys. Rev. Lett . 93 (18) 188701. arXiv : cond-mat/0403051 . Bibcode : 2004PhRvL..93r8701G . doi : 10.1103 /physrevlett.93.188701 . PMID 15525215. S2CID 16367275 .   
  33. ↑ Krioukov, Dmitri; Papadopoulos, Fragkiskos; Kitsak, Maksim; Vahdat, Amin; Boguñá, Marián (2010). "Geometría hiperbólica de redes complejas". Revisión física E. 82 (3) 036106. arXiv : 1006.5169 . Código Bib : 2010PhRvE..82c6106K . doi : 10.1103/PhysRevE.82.036106 . PMID 21230138 . S2CID 6451908 .  
  34. ↑ A. Hernando; D. Villuendas; C. Vesperinas; M. Abad; A. Plastino (2009). "Desentrañando la distribución del tamaño de los grupos sociales con la teoría de la información en redes complejas". arXiv : 0905.3704 [ physics.soc-ph ]., enviado a European Physical Journal B
  35. ↑ André A. Moreira; Demétrius R. Paula; Raimundo N. Costa Filho; José S. Andrade, Jr. (2006). "Crecimiento competitivo de clusters en redes complejas". Revisión física E. 73 (6) 065101. arXiv : cond-mat/0603272 . Código Bib : 2006PhRvE..73f5101M . doi : 10.1103/PhysRevE.73.065101 . PMID 16906890 . S2CID 45651735 .  
  36. ↑ Heydari, H.; Taheri, SM; Kaveh, K. (2018). "Distributed Maximal Independent Set on Scale-Free Networks". arXiv : 1804.02513 [ cs.DC ].
  37. ↑ Clauset, Aaron; Cosma Rohilla Shalizi; ME J Newman (2009). "Distribuciones de ley de potencias en datos empíricos". SIAM Review . 51 (4): 661– 703. arXiv : 0706.1062 . Bibcode : 2009SIAMR..51..661C . doi : 10.1137/070710111 . S2CID 9155618 . 
  38. ↑ Eom, Young-Ho; Jo, Hang-Hyun (2015-05-11). "Tail-scope: Uso de amigos para estimar colas pesadas de distribuciones de grado en redes complejas a gran escala" . Scientific Reports . 5 (1): 9752. arXiv : 1411.6871 . Bibcode : 2015NatSR...5.9752E . doi : 10.1038/srep09752 . ISSN 2045-2322 . PMC 4426729. PMID 25959097 .   
  39. 1 2 Nettasinghe, Buddhika; Krishnamurthy, Vikram (2021-05-19). "Estimación de máxima verosimilitud de distribuciones de grado de ley de potencias mediante muestreo basado en la paradoja de la amistad" . ACM Transactions on Knowledge Discovery from Data . 15 (6): 1– 28. arXiv : 1908.00310 . doi : 10.1145/3451166 . ISSN 1556-4681 . 
  40. ↑ Broido, Anna D.; Clauset, Aaron (2019). "Las redes libres de escala son raras" . Nature Communications . 10 (1) 1017. arXiv : 1801.03400 . Bibcode : 2019NatCo..10.1017B . doi : 10.1038/ s41467-019-08746-5 . PMC 6399239. PMID 30833554 .  

Lecturas adicionales

  • Albert R.; Barabási A.-L. (2002). "Mecánica estadística de redes complejas" . Rev. Mod. Phys . 74 (1): 47– 97. arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . S2CID 60545 . 
  • Amaral LAN, Scala A, Barthelemy M, Stanley HE (2000). "Clases de redes de mundo pequeño" . PNAS . 97 (21): 11149– 52. arXiv : cond-mat/0001458 . Bibcode : 2000PNAS ...9711149A . doi : 10.1073/pnas.200327197 . PMC 17168. PMID 11005838 .  
  • Barabási, Albert-László (2004). Vinculado: Cómo todo está conectado con todo lo demás . Pub Perseo. ISBN 0-452-28439-2.
  • Barabási, Albert-László; Bonabeau, Eric (mayo de 2003). "Redes sin escala" (PDF) . Científico americano . 288 (5): 50– 9. Bibcode : 2003SciAm.288e..60B . doi : 10.1038/scientificamerican0503-60 . PMID 12701331 . 
  • Dan Braha; Yaneer Bar-Yam (2004). "Topología de redes de resolución de problemas de ingeniería a gran escala" (PDF) . Phys. Rev. E. 69 ( 1) 016113. Bibcode : 2004PhRvE..69a6113B . doi : 10.1103/ PhysRevE.69.016113 . PMID 14995673. S2CID 1001176 .  
  • Caldarelli G. " Redes libres de escala" Oxford University Press, Oxford (2007).
  • Caldarelli G.; Capocci A.; De Los Rios P.; Muñoz MA (2002). "Redes libres de escala a partir de aptitud intrínseca de vértice variable". Physical Review Letters . 89 (25) 258702. arXiv : cond-mat/0207366 . Bibcode : 2002PhRvL..89y8702C . doi : 10.1103/PhysRevLett.89.258702 . PMID 12484927 . 
  • Dangalchev, Ch. (2004). "Modelos de generación para redes libres de escala" . Physica A. 338 ( 3–4 ) : 659–671 . Bibcode : 2004PhyA..338..659D . doi : 10.1016/j.physa.2004.01.056 .
  • Dorogovtsev, SN; Mendes, JFF; Samukhin, AN (2000). "Estructura de redes en crecimiento: solución exacta del modelo de Barabási-Albert". Phys. Rev. Lett . 85 (21): 4633– 6. arXiv : cond - mat/0004434 . Bibcode : 2000PhRvL..85.4633D . doi : 10.1103/PhysRevLett.85.4633 . PMID 11082614. S2CID 118876189 .  
  • Dorogovtsev, SN; Mendes, JFF (2003). Evolución de las redes: de las redes biológicas a Internet y la WWW . Oxford University Press. ISBN 0-19-851590-1.
  • Dorogovtsev, SN; Goltsev AV; Mendes, JFF (2008). "Fenómenos críticos en redes complejas". Rev. Mod. Phys . 80 (4): 1275– 1335. arXiv : 0705.0010 . Bibcode : 2008RvMP...80.1275D . doi : 10.1103/RevModPhys.80.1275 . S2CID 3174463 . 
  • Dorogovtsev, SN; Mendes, JFF (2002). "Evolución de las redes". Advances in Physics . 51 (4): 1079– 1187. arXiv : cond-mat/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080/00018730110112519 . S2CID 429546 . 
  • Erdős, P. ; Rényi, A. (1960). Sobre la evolución de los grafos aleatorios (PDF) . Vol.  5. Publicación del Instituto Matemático de la Academia Húngara de Ciencias. pp. 17– 61. 
  • Faloutsos, M.; Faloutsos, P.; Faloutsos, C. (1999). "Sobre las relaciones de ley de potencias de la topología de Internet". ACM SIGCOMM Computer Communication Review . 29 (4): 251– 262. doi : 10.1145/316194.316229 .
  • Li, L.; Alderson, D.; Tanaka, R.; Doyle, JC; Willinger, W. (2005). "Hacia una teoría de grafos libres de escala: definición, propiedades e implicaciones (versión extendida)". arXiv : cond-mat/0501169 .
  • Kumar, R.; Raghavan, P.; Rajagopalan, S.; Sivakumar, D.; Tomkins, A.; Upfal, E. (2000). "Modelos estocásticos para el grafo web" (PDF) . Actas del 41.º Simposio Anual sobre Fundamentos de la Informática (FOCS) . Redondo Beach, CA: IEEE CS Press. págs. 57–65 . 
  • Matlis, Jan (4 de noviembre de 2002). "Redes libres de escala" .
  • Newman, Mark EJ (2003). "La estructura y función de las redes complejas". SIAM Review . 45 (2): 167– 256. arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137/S003614450342480 . S2CID 221278130 . 
  • Pastor-Satorras, R.; Vespignani, A. (2004). Evolución y estructura de Internet: Un enfoque de física estadística . Cambridge University Press. ISBN 0-521-82698-5.
  • Pennock, DM; Flake, GW; Lawrence, S.; Glover, EJ; Giles, CL (2002). "Los ganadores no se lo llevan todo: Caracterización de la competencia por los enlaces en la web" . PNAS . 99 (8): 5207– 11. Bibcode : 2002PNAS...99.5207P . doi : 10.1073 / pnas.032085699 . PMC 122747. PMID 16578867 .  
  • Robb, John. Redes libres de escala y terrorismo , 2004.
  • Keller, EF (2005). "Revisitando las redes "libres de escala" . BioEssays . 27 (10): 1060– 8. Bibcode : 2005BiEss..27.1060F . doi : 10.1002/bies.20294 . PMID 16163729 . {{cite journal}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  • Onody, RN; de Castro, PA (2004). "Estudio de redes complejas de un jugador de fútbol brasileño". Phys. Rev. E . 70 (3) 037103. arXiv : cond-mat/0409609 . Bibcode : 2004PhRvE..70c7103O . doi : 10.1103/PhysRevE.70.037103 . PMID 15524675 . S2CID 31653489 .  
  • Kasthurirathna, D.; Piraveenan, M. (2015). "Estudio de redes complejas de jugadores de fútbol brasileños". Sci. Rep . En prensa.