ARS 101: Redes libres de escala

Redes libre de escala

Wikipedia

Una red libre de escala es una red cuyo grado de distribución sigue una ley de potencias, al menos asintóticamente. Es decir, la fracción de P (k) de nodos en la red que tiene conexiones a otros nodos k vale para grandes valores de k como



donde  es un parámetro cuyo valor es típicamente en el intervalo 2 < <3, aunque en ocasiones puede estar fuera de estos límites. [1] [2]

Muchas redes se conjeturaron que ser libre de escala, incluyendo los enlaces de la World Wide Web, redes biológicas, y las redes sociales, aunque la comunidad científica está todavía discutiendo estas afirmaciones como datos más sofisticadas técnicas de análisis disponibles. [3] Los enlaces preferenciales y el modelo de fitness se han propuesto como mecanismos para explicar grado distribuciones de ley de potencia conjeturado en redes reales.

Historia

En los estudios de las redes de citas entre trabajos científicos, Derek de Solla Price mostró en 1965 que el número de enlaces a documentos, 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 tanto, que la red de citas es libre de escala. Él sin embargo no utilizar el término "red libre de escala", que no fue acuñado hasta algunas décadas después. En un trabajo posterior en 1976, Price también propone un mecanismo para explicar la aparición de leyes de potencia en redes de citación, que él llamó "la ventaja acumulada", pero que es hoy más conocido bajo el nombre del archivo adjunto preferencial.

El reciente interés en las redes libres de escala se inició en 1999 con la obra de Albert-László Barabási y sus colegas en la Universidad de Notre Dame, que mapea la topología de una parte de la World Wide Web, [4] encontrando que algunos nodos, a la que llamaron "centros ", 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 conectan a un nodo. Después de encontrar que algunas otras redes, incluyendo algunas redes sociales y biológicos, también tenían grado distribuciones de cola pesada, Barabási y colaboradores acuñaron el término "red libre de escala" para describir la clase de las redes que presentan un grado de distribución de ley de potencia. Amaral et al. mostró que la mayoría de las redes del mundo real se pueden clasificar en dos grandes categorías de acuerdo a la decadencia de la distribución de grado P (k) para grandes k.

Barabási y Albert propusieron un mecanismo generativo para explicar la aparición de las distribuciones de poder de la ley, que llamaron "conexión preferencial" y que es esencialmente el mismo que el propuesto por precio. Soluciones analíticas para este mecanismo (también similar a la solución de precio) fueron presentados en 2000 por Dorogovtsev, Mendes y Samukhin [5] y de forma independiente por Krapivsky, Redner y Leyvraz, y más tarde probado rigurosamente por el matemático Béla Bollobás. [6] En particular, sin embargo, este mecanismo sólo produce un subconjunto específico de las redes en la clase libre de escala, y muchos mecanismos alternativos se han descubierto desde entonces. [7]

La historia de las redes libres de escala también incluye algunos desacuerdos. A nivel empírico, la naturaleza libre de escala de varias redes se ha puesto en duda. Por ejemplo, los tres hermanos Faloutsos creído que Internet tenía un grado de distribución de ley de potencia sobre la base de datos de traceroute; sin embargo, se ha sugerido que ésta es una ilusión capa 3 creado por routers, que aparecen como nodos de alto grado al tiempo que oculta la estructura de capas 2 interna de los sistemas autónomos que interconectan. [8] En el plano teórico, se han propuesto mejoras a la definición abstracta de escala libre. Por ejemplo, Li et al. (2005) ofreció recientemente una potencialmente más precisa "libre de escala métrica". Brevemente, sea G un grafo con el conjunto de borde E, y denota el grado de un vértice v (es decir, el número de aristas incidentes a ) por . definidos como




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


,
donde Smax es el valor máximo de s (H) para H en el conjunto de todos los grafos con grado de distribución idénticas a G. Esto da una métrica entre 0 y 1, donde un grafo G con el pequeño S (G) es "escala rica ", y un grafo G con S (G) cerca de 1 es" libre de escala ". Esta definición recoge la noción de auto-similitud implícita en el nombre de "libre de escala".


Características


La característica más notable en una red libre de escala es la commonness relativa de vértices con un grado que excede en gran medida de la media. Los nodos de más alto grado son a menudo llamados "centros", y se cree que servir a propósitos específicos en sus redes, aunque esto depende en gran medida en el dominio.


Red aleatoria (a) y de la red libre de escala (b). En la red libre de escala, se destacan los centros más grandes.

La propiedad libre de escala se correlaciona fuertemente con la robustez de la red para el fracaso. Resulta que los principales centros son seguidos de cerca por los más pequeños. Estos centros más pequeños, a su vez, son seguidos por otros nodos con un grado aún más pequeño y así sucesivamente. Esta jerarquía permite un comportamiento tolerante a fallos. Si se producen errores al azar y la gran mayoría de los nodos son aquellos con pequeño grado, la probabilidad de que un cubo se vería afectada es casi insignificante. Incluso si se produce un concentrador de fallo, la red generalmente no perder su conexión, debido a los cubos restantes. Por otro lado, si elegimos un par de cubos grandes y sacarlos de la red, la red se convierte en un conjunto de grafos más bien aislados. Por lo tanto, los centros son una fuerza y una debilidad de las redes libres de escala. Estas propiedades se han estudiado analíticamente utilizando la teoría de la percolación por Cohen et al. [9] [10] y por Callaway et al. [11]


Grado de distribución compleja red de azar y sin escala

Otra característica importante de las redes libres de escala es la distribución coeficiente de agrupamiento, que disminuye a medida que el grado nodo aumenta. Esta distribución también sigue una ley de potencias. Esto implica que los nodos de bajo grado pertenecen a muy densas sub-grafos y los sub-grafos están conectados entre sí a través de concentradores. Considere una red social en la que los nodos son las personas y los vínculos son relaciones tener conocidos entre las personas. Es fácil ver que la gente tiende a formar comunidades, es decir, pequeños grupos en los que todo el mundo sabe todo el mundo (se puede pensar en tal comunidad como un grafo completo). Además, los miembros de una comunidad también tienen algunas relaciones conocimiento con personas fuera de esa comunidad. Algunas personas, sin embargo, están conectados a un gran número de comunidades (por ejemplo, celebridades, políticos). Esas personas pueden ser considerados los centros responsables del fenómeno del mundo pequeño.

En la actualidad, las características más específicas de las redes libres de escala varían de acuerdo con el mecanismo generativo utilizado para crearlos. Por ejemplo, las redes generadas por la unión preferencial típicamente colocan los vértices de alto grado en el medio de la red, conectándolos entre sí para formar un núcleo, con nodos progresivamente menor grado que componen las regiones entre el núcleo y la periferia. La eliminación aleatoria de incluso una fracción grande de vértices impactos de la conexión global de la red muy pequeños, lo que sugiere que tales topologías podría ser útil para la seguridad, mientras que los ataques dirigidos destruye la conexión muy rápidamente. Otras redes libres de escala, que ponen los vértices de alto grado en la periferia, no presentan estas propiedades. Del mismo modo, el coeficiente de agrupamiento de las redes libres de escala puede variar significativamente dependiendo de otros datos topológicos.

Una característica final se refiere a la distancia media entre dos vértices en una red. Como con la mayoría de las redes desordenadas, como el modelo de red de mundo pequeño, esta distancia es muy pequeña en relación a una red altamente ordenada, como un grafo de celosía. En particular, un grafo de ley de potencias no correlacionados que tiene 2 <γ <3 tendrá un diámetro d ultrapequeño~ ln ln N, donde N es el número de nodos de la red, como se ha demostrado por Cohen y Havlin. El diámetro de una red libre de escala creciente podría considerarse casi constante en la práctica.

Ejemplos

Aunque muchas redes del mundo real se cree que son libres de escala, las pruebas a menudo no son concluyentes, debido principalmente a la conciencia el desarrollo de más rigurosas técnicas de análisis de datos. [3] Como tal, la naturaleza libre de escala de muchas redes sigue siendo debatido por la comunidad científica. Algunos ejemplos de redes afirmaban ser libre de escala incluir:

• Las redes sociales, incluidas las redes de colaboración. Dos ejemplos que han sido estudiados extensamente son la colaboración de agentes de la película en el cine y la co-autoría por los matemáticos de papeles.
• Hay muchos tipos de redes de ordenadores, incluyendo el Internet y la Webgrafía de la World Wide Web.
• Algunas redes financieras tales como las redes de pago interbancario [12] [13]
• Las redes de interacción proteína-proteína.
• Las redes semánticas. [14]
• Redes de aerolíneas.

La escala topología libre ha sido también encontrado en superconductores de alta temperatura [15] 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 desembocan en perfecta sincronía, sin fricción - aparecen ligados a la fractal arreglos de átomos de oxígeno aparentemente al azar y la distorsión de celosía. [16].

Referencias

1. Onnela, J. -P.; Saramaki, J.; Hyvonen, J.; Szabo, G.; Lazer, D.; Kaski, K.; Kertesz, J.; Barabasi, A. -L. (2007). "Structure and tie strengths in mobile communication networks". Proceedings of the National Academy of Sciences 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). "Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure". Journal of Statistical Physics 151 (6): 1175. Bibcode:2013JSP...151.1175C. doi:10.1007/s10955-013-0749-1. 
3. Clauset, Aaron; Cosma Rohilla Shalizi; M. E. J Newman (2007-06-07). "Power-law distributions in empirical data". 0706.1062. arXiv:0706.1062. Bibcode:2009SIAMR..51..661C. doi:10.1137/070710111.
4. Barabási, Albert-László; Albert, Réka. (October 15, 1999). "Emergence of scaling in random networks". Science 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. MR 2091634. PMID 10521342.
5. Dorogovtsev, S.; Mendes, J.; Samukhin, A. (2000). "Structure of Growing Networks with Preferential Linking". Physical Review Letters 85 (21): 4633–4636. arXiv:cond-mat/0004434. Bibcode:2000PhRvL..85.4633D. doi:10.1103/PhysRevLett.85.4633. PMID 11082614. 
6. Bollobás, B.; Riordan, O.; Spencer, J.; Tusn�Dy, G. (2001). "The degree sequence of a scale-free random graph process". Random Structures and Algorithms 18 (3): 279–290. doi:10.1002/rsa.1009. MR 1824277. 
7. Dorogovtsev, S. N.; Mendes, J. F. F. (2002). "Evolution of networks". Advances in Physics 51 (4): 1079. doi:10.1080/00018730110112519. 
8. Willinger, Walter; David Alderson; John C. Doyle (May 2009). "Mathematics and the Internet: A Source of Enormous Confusion and Great Potential". Notices of the AMS (American Mathematical Society) 56 (5): 586–599. Retrieved 2011-02-03.
9. Cohen, Reoven; K. Erez, D. ben-Avraham and S. Havlin (2000). "Resilience of the Internet to Random Breakdowns". Phys. Rev. Lett. 85: 4626–8. arXiv:cond-mat/0007048. Bibcode:2000PhRvL..85.4626C. doi:10.1103/PhysRevLett.85.4626.
10. Cohen, Reoven; K. Erez, D. ben-Avraham and S. Havlin (2001). "Breakdown of the Internet under Intentional Attack". Phys. Rev. Lett. 86: 3682–5. arXiv:cond-mat/0010251. Bibcode:2001PhRvL..86.3682C. doi:10.1103/PhysRevLett.86.3682. PMID 11328053.
11. Callaway, Duncan S.; M. E. J. Newman, S. H. Strogatz and D. J. Watts (2000). "Network Robustness and Fragility: Percolation on Random Graphs". Phys. Rev. Lett. 85: 5468–71. arXiv:cond-mat/0007300. Bibcode:2000PhRvL..85.5468C. doi:10.1103/PhysRevLett.85.5468.
12. De Masi, Giulia; et. al (2006). "Fitness model for the Italian interbank money market". Physical Review E 74: 066112. doi:10.1103/PhysRevE.74.066112.
13. Soramäki, Kimmo; et. al (2007). "The topology of interbank payment flows". Physica A: Statistical Mechanics and its Applications 379 (1): 317–333. Bibcode:2007PhyA..379..317S. doi:10.1016/j.physa.2006.11.093.
14. Steyvers, Mark; Joshua B. Tenenbaum (2005). "The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth". Cognitive Science 29 (1): 41–78. doi:10.1207/s15516709cog2901_3.
15. Fratini, Michela, Poccia, Nicola, Ricci, Alessandro, Campi, Gaetano, Burghammer, Manfred, Aeppli, Gabriel Bianconi, Antonio (2010). "Scale-free structural organization of oxygen interstitials in La2CuO4+y". Nature 466 (7308): 841–4. arXiv:1008.2015. Bibcode:2010Natur.466..841F. doi:10.1038/nature09260. PMID 20703301.
16. Poccia, Nicola, Ricci, Alessandro, Campi, Gaetano, Fratini, Michela, Puri, Alessandro, Di Gioacchino, Daniele, Marcelli, Augusto, Reynolds, Michael, Burghammer, Manfred, Saini, Naurang L., Aeppli, Gabriel Bianconi, Antonio, (2012). "Optimum inhomogeneity of local lattice distortions in La2CuO4+y". Proc. Natl. Acad. Sci. U.S.A. 109 (39): 15685–15690. arXiv:1208.0101. doi:10.1073/pnas.1208492109.