Red de mundo pequeño
En matemática y física una red de mundo pequeño es un tipo de grafo para el que la mayoría de los nodos no son vecinos entre sí, y sin embargo la mayoría de los nodos pueden ser alcanzados desde cualquier nodo origen a través de un número relativamente corto de saltos entre ellos. Una red social, donde los nodos son personas y los enlaces son el conocimiento/relación entre ellos, captura muchos de los fenómenos de las redes de mundo pequeño.[1] Pronto se empezaría a ver que las redes de mundo pequeño son más frecuentes de lo que se presupone y pronto aparecieron otras redes bajo esta categoría: un ejemplo muy claro es la topología de Internet. Este fenómeno ha dado la posibilidad de aplicación de este tipo de redes en diferentes áreas de la ciencia como puede ser el modelado de redes sociales, física, biología, epidemiología, etc.
Historia
En los años 1960 el psicólogo Stanley Milgram empezó un experimento que denominó como: experimento del Mundo Pequeño en la Harvard University, llegando a la conclusión de que se podía conectar a dos personas en Estados Unidos con tan solo seis saltos de media, este fenómeno se denominó: seis grados de separación.[2] En este experimento se empezó la investigación de una cierta categoría de redes de mundo pequeño. En el año 1998 los matemáticos Duncan Watts y Steven Strogatz llevaron a cabo un estudio centrado en el análisis de redes concentrándose en cierto tipo de grafos aleatorios que mostraba propiedades de conectividad peculiares.[3] Uno de los modelos empleados para la generación de estos grafos aleatorios se denomina modelo Erdös–Rényi, este tipo de redes exhiben un trayecto mínimo promedio entre nodos que crece logarítmicamente con el número de nodos en la red, poseyendo además bajos coeficientes de agrupamiento. En su estudio Watts y Strogatz mostraron que las redes se podían clasificar en función de dos parámetros: el coeficiente de agrupamiento (clustering coefficient) y la distancia.[4] Watts y Strogatz propusieron un modelo de redes de mundo pequeño a partir del modelo Erdös-Rényi, denominado modelo Watts y Strogatz en el que se tiene: (i) un trayecto mínimo promedio entre nodos de valor pequeño y (ii) un coeficiente de agrupamiento de valor grande. La primera descripción del modelo de Watts y Strogatz puso en evidencia que había una gradación entre lo que se puede denominar un “mundo grande” (un retículo) y un grafo aleatorio (totalmente desordenadas), entre estos dos extremos estaban las redes de mundo pequeño. Tras el estudio[5] de Barthelemy y Amaral realizado en el año 1999, se empezaron a describir muchas propiedades de las redes de mundo pequeño.
Concepto
La idea central de la generación de redes de pequeño mundo está fundamentado en dos propiedades:
- El fenómeno del mundo pequeño - es decir que cualesquiera dos nodos de la red se comunican por un camino de nodos intermedios relativamente pequeño (pequeño número de nodos). Comprobando que la distancia máxima entre dos nodos crece logarítmicamente con el número de nodos en la red.[6]
- Poseen valores altos de coeficiente de agrupamiento (clustering coefficent) - este valor fue empleado por Watts y Strogatz.[4] Este valor viene a indicar que si dos vértices o nodos no están conectados directamente entre sí existe una gran probabilidad de que conecten mediante la intervención de otros nodos.
Dada una red cualesquiera, el efecto de pequeño mundo en ella es fácil de medir: simplemente se debe buscar las distancias entre pares de vértices en la red y calcular su distancia media. Entre los métodos más comunes para hacer esta operación se encuentra el algoritmo denominado búsqueda en anchura.
En un grafo aleatorio el grado medio es y coincide con el valor medio de vecinos, el de segundos vecinos es de y el de terceros , etc. El modelo que genera este tipo de redes se denomina Watts y Strogatz y comienza con una red en la existen N nodos en forma de anillo, en esta red cada nodo está conectado a sus primeros k vecinos (k/2 por cada lado), en este estado cada vez que se añade un nodo se enlaza con el resto empleando una probabilidad de p para cualquier nodo de la red.[3] El modelo se llegó a conocer como el modelo beta (Watts) al haber formulado β para formularlo en su popular libro científico Six Degrees: The Science of a Connected Age (2003) [Seis grados: La ciencia de una época conectada].
Una de las características exploradas por Watts y Steve Strogatz es que la distribución de grado de este tipo de redes de pequeño mundo que son generadas debía corresponder a una distribución de Poisson, pero pronto se vio que las redes de mundo pequeño pueden tener distribuciones de grado que siguen una distribución exponencial (como es el caso de las redes libres de escala). Otras propiedades como un valor bajo del diámetro.
Construcción
Se puede ver por la construcción que las redes de mundo pequeño están a medio camino entre las redes ordenadas (retículos) y las que muestran una estructura caótica. Para construir una red de mundo pequeño es necesario comenzar con una disposición circular de N vértices completamente desconectados. Supongamos que tenemos que reconectar los vértices con un valor de grado medio y de tal forma que cada nodo sea conectado con cualesquiera otro con una probabilidad p. Esta construcción nos permite ajustar la topología de la red, desde un valor p=0 (red regular, como por ejemplo un retículo en el que cada nodo está conectado regularmente con sus z vecinos) hasta el más completo desorden (p=1). Se puede ver que las redes que cumplen 0 < p < 1 tienen efectos de mundo pequeño.
Ejemplos
Ejemplos de redes de pequeño mundo se han encontrado en numerosas redes presentes en la naturaleza, una de ellas es la que define las proteínas que interaccionan en el metabolismo de las bacterias.[7] Dentro de la biología se encuentran las redes transcripcionales de los genes que poseen distribuciones de grado completamente exponenciales. La red neuronal del gusano caenorhabditis elegans.[8]
Otros ejemplos encontrados en la teoría de redes se acercan al estudio de redes de transporte tales como pueden ser las redes de carreteras, estaciones de autobuses, etc.
Referencias
- "Linked: The New Science of Networks", Albert-László Barabási, Ed. Basic Books, 2003
- S. Milgram," The small world problem," Psychology Today 1 (1967)
- ↑ Watts, D.J.; Strogatz, S.H. (1998). «Collective dynamics of 'small-world' networks.». Nature 393 (6684): 409-10. doi:10.1038/30918. Consultado el 25 de febrero de 2008.
- ↑ Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature 393: 440–442.
- Barthelemy, M.; Amaral, LAN. (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82: 3180
- "The Structure and Dynamics of Networks", Mark E. J. Newman, Albert-László Barabási, Duncan J. Watts, Mark E. J. Newman, Albert-László Barabási, Duncan J. Watts, Ed. Princeton University Press, 2006, ISBN 0-691-11357-2
- "Protein interaction networks from yeast to human", Peer Bork, Lars J Jensen, Christian von Mering, Arun K Ramani,Insuk Lee y Edward M. Marcotte, Current Opinion in Structural Biology, 2004, 14:292–299
- "Classes of small-world networks", L. A. N. Amaral, A. Scala,M. Barthélémy y H. E. Stanley, PNAS, September 26, 2000