Red de mundo pequeño

Red de mundo pequeño

Red de mundo pequeño

Las redes de mundo pequeño permiten conectar dos nodos con relativamente pocos saltos entre ellos. En la ilustración puede verse una red que sigue el modelo Watts-Strogatz

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í, pero 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. En el caso de una red social, donde los nodos son personas y los enlaces son el conocimiento/relación entre ellos se puede decir que 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.

Contenido

Historia

En los años 60 el matemático 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 pequeños mundos por los matemáticos Duncan Watts y Steven Strogatz en el año 1998, el estudio se centró en el análisis de redes realizado sobre 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 medio mínimo entre nodos que depende logarítmicamente con el número de nodos en la red, poseyendo además bajos índices 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) una longitud mínima media entre nodos de valor pequeño y (ii) un gran valor del coeficiente de agrupamiento. 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 medias estaban las redes de mundo pequeño.[5] Tras este estudio realizado en el año 1999, se empezaron a describir muchas propiedades de las redes de mundo pequeño.

Concepto

Artículo principal: modelo Watts y Strogatz

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 algorito denominado búsqueda en anchura.

En un grafo aleatorio el grado medio es < k > y coincide con el valor medio de vecinos, el de segundos vecinos es de < k > 2 y el de terceros < k > 3, 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 (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 (reticulos) y ls 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 < k > y de tal forma que cada nodo sea conectado con cualesquiera otro con una probabilidad p. Esta contrucció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

  1. "Linked: The New Science of Networks", Albert-László Barabási, Ed. Basic Books, 2003
  2. S. Milgram," The small world problem," Psychology Today 1 (1967)
  3. a b Watts, D.J.; Strogatz, S.H. (1998). «Collective dynamics of 'small-world' networks.» Nature. Vol. 393. n.º 6684. pp. 409–10. DOI 10.1038/30918.
  4. a b Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of 'small-world' networks". Nature 393: 440–442.
  5. Barthelemy, M.; Amaral, LAN. (1999). "Small-world networks: Evidence for a crossover picture". Phys. Rev. Lett. 82: 3180
  6. "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
  7. "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
  8. "Classes of small-world networks", L. A. N. Amaral, A. Scala,M. Barthélémy y H. E. Stanley, PNAS, September 26, 2000

Véase también

Obtenido de "Red de mundo peque%C3%B1o"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Mundo pequeño — Se ha sugerido que este artículo o sección sea fusionado con Red de mundo pequeño (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí. Mundo pequeño es una propiedad que presentan algunas redes… …   Wikipedia Español

  • Experimento del Mundo Pequeño — Saltar a navegación, búsqueda El experimento del mundo pequeño comprende varios experimentos llevados a cabo por el psicólogo social Stanley Milgram, en su investigación sobre las redes sociales en los Estados Unidos. Lo innovador de esta… …   Wikipedia Español

  • Red social — Saltar a navegación, búsqueda Una red social es una estructura social que se puede representar en forma de uno o varios grafos en los cuales los nodos representan individuos (a veces denominados actores) y las aristas relaciones entre ellos.… …   Wikipedia Español

  • Red Hot Chili Peppers — tocando en la ceremonia de los Premios Grammy de 2007. Datos generales Origen …   Wikipedia Español

  • Red ferroviaria argentina — Saltar a navegación, búsqueda La red ferroviaria argentina, con 34.059 km de vías[1] fue, en su momento, una de las más grandes del mundo y sigue siendo la más extensa de Latinoamérica. Llegó a tener cerca de 47.000 km de rieles,[2] pero el… …   Wikipedia Español

  • Red Arrows — Saltar a navegación, búsqueda Red Arrows Los Red Arrows en 2009 Activa 1964 actualidad …   Wikipedia Español

  • Pequeño Recorrido — Saltar a navegación, búsqueda Señalización de un sendero de Pequeño Recorrido PR …   Wikipedia Español

  • Mundo de The League of Extraordinary Gentlemen — Este artículo o sección sobre historieta necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 4 de mayo de 2007. También puedes ayud …   Wikipedia Español

  • Historia del mundo Warcraft — La siguiente, es un resumen sobre los hechos que suceden en la saga de videojuegos de estrategia Warcraft. Para mayor información, véase el artículo principal. Contenido 1 Los orígenes 1.1 Génesis Universal Del universo 1.2 Sargeras y la traición …   Wikipedia Español

  • Mundos del Mundo Atmos — Anexo:Mundos del Mundo Atmos Saltar a navegación, búsqueda Contenido 1 Tierras 2 Amazonia 3 Aquanos 4 Atmosia …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”