Una red de mundo pequeño es un gráfico caracterizado por un alto coeficiente de agrupación y distancias bajas . En un ejemplo de red social, una alta agrupación implica una alta probabilidad de que dos amigos de una persona sean amigos. Las distancias bajas, por el contrario, significan que existe una corta cadena de conexiones sociales entre dos personas cualesquiera (este efecto se conoce como seis grados de separación ). [1] Específicamente, una red de mundo pequeño se define como una red donde la distancia típica L entre dos nodos elegidos al azar (el número de pasos requeridos) crece proporcionalmente al logaritmo del número de nodos N en la red, es decir : [2]
mientras que el coeficiente de agrupamiento global no es pequeño.
En el contexto de una red social, esto da como resultado el fenómeno del pequeño mundo en el que extraños están unidos por una corta cadena de conocidos . Muchos gráficos empíricos muestran el efecto del mundo pequeño, incluidas las redes sociales , wikis como Wikipedia, redes genéticas e incluso la arquitectura subyacente de Internet . Es la inspiración para muchas arquitecturas de red en chip en el hardware informático contemporáneo . [3]
Duncan Watts y Steven Strogatz identificaron una determinada categoría de redes de mundos pequeños como una clase de gráficos aleatorios en 1998. [4] Señalaron que los gráficos podrían clasificarse de acuerdo con dos características estructurales independientes, a saber, el coeficiente de agrupamiento y el nodo promedio. Distancia entre nodos (también conocida como longitud promedio de ruta más corta ). Los gráficos puramente aleatorios, construidos según el modelo Erdős-Rényi (ER) , exhiben una longitud de ruta más corta promedio pequeña (que varía típicamente como el logaritmo del número de nodos) junto con un pequeño coeficiente de agrupación. Watts y Strogatz midieron que, de hecho, muchas redes del mundo real tienen una longitud de ruta más corta promedio pequeña, pero también un coeficiente de agrupamiento significativamente mayor de lo esperado por azar. Watts y Strogatz luego propusieron un nuevo modelo gráfico, actualmente denominado modelo de Watts y Strogatz , con (i) una longitud de camino más corta promedio pequeña y (ii) un coeficiente de agrupación grande. El cruce en el modelo Watts-Strogatz entre un "mundo grande" (como una red) y un mundo pequeño fue descrito por primera vez por Barthelemy y Amaral en 1999. [5] A este trabajo le siguieron muchos estudios, incluidos resultados exactos (Barrat y Weigt, 1999; Dorogovtsev y Mendes ; Barmpoutis y Murray, 2010).
Las redes de mundos pequeños tienden a contener camarillas y casi camarillas, es decir, subredes que tienen conexiones entre casi dos nodos cualesquiera dentro de ellas. Esto se desprende de la propiedad definitoria de un coeficiente de agrupamiento alto . En segundo lugar, la mayoría de los pares de nodos estarán conectados por al menos un camino corto. Esto se deduce de la propiedad definitoria de que la longitud media del camino más corto sea pequeña. Varias otras propiedades suelen asociarse con redes de mundos pequeños. Normalmente hay una sobreabundancia de hubs : nodos en la red con un gran número de conexiones (conocidos como nodos de alto grado ). Estos centros sirven como conexiones comunes que median los recorridos cortos entre otros bordes. Por analogía, la red de vuelos de aerolíneas del pequeño mundo tiene una longitud media de ruta pequeña (es decir, entre dos ciudades cualesquiera es probable que tengas que tomar tres vuelos o menos) porque muchos vuelos se dirigen a través de ciudades centrales . Esta propiedad a menudo se analiza considerando la fracción de nodos de la red que tienen un número particular de conexiones (la distribución de grados de la red). Las redes con un número de centros mayor al esperado tendrán una mayor fracción de nodos con alto grado y, en consecuencia, la distribución de grados se enriquecerá con valores de alto grado. Esto se conoce coloquialmente como distribución de cola gruesa . Los grafos de topología muy diferente califican como redes de mundo pequeño siempre que satisfagan los dos requisitos de definición anteriores.
El carácter pequeño de la red se ha cuantificado mediante un coeficiente pequeño, calculado comparando la agrupación y la longitud de la ruta de una red determinada con una red aleatoria equivalente con el mismo grado en promedio. [6] [7]
Otro método para cuantificar el carácter pequeño de una red utiliza la definición original de red de mundo pequeño comparando la agrupación de una red determinada con una red reticular equivalente y la longitud de su ruta con una red aleatoria equivalente. La medida del mundo pequeño ( ) se define como [8]
Donde la longitud de ruta característica L y el coeficiente de agrupamiento C se calculan a partir de la red que está probando, C ℓ es el coeficiente de agrupamiento para una red de celosía equivalente y L r es la longitud de ruta característica para una red aleatoria equivalente.
Otro método más para cuantificar el mundo pequeño normaliza tanto la agrupación de la red como la longitud de la ruta en relación con estas características en redes aleatorias y de red equivalentes. El Índice del Mundo Pequeño (SWI) se define como [9]
Tanto ω ′ como SWI oscilan entre 0 y 1, y se ha demostrado que capturan aspectos del mundo pequeño. Sin embargo, adoptan concepciones ligeramente diferentes del mundo pequeño ideal. Para un conjunto dado de restricciones (por ejemplo, tamaño, densidad, distribución de grados), existe una red para la cual ω ′ = 1 y, por lo tanto, ω pretende capturar el grado en que una red con restricciones dadas es lo más pequeña posible. Por el contrario, puede que no exista una red para la cual SWI = 1; por lo tanto, SWI tiene como objetivo capturar el grado en que una red con restricciones dadas se acerca al ideal teórico del mundo pequeño de una red donde C ≈ C ℓ y L ≈ L r . [9]
Las propiedades del mundo pequeño se encuentran en muchos fenómenos del mundo real, incluidos sitios web con menús de navegación, redes tróficas, redes de energía eléctrica, redes de procesamiento de metabolitos, redes de neuronas cerebrales , redes de votantes, gráficos de llamadas telefónicas y redes de aeropuertos. [10] También se ha demostrado que las redes culturales [11] y las redes de coexistencia de palabras [12] son redes de mundo pequeño.
Las redes de proteínas conectadas tienen propiedades de mundo pequeño, como la ley de potencia que obedece a distribuciones de grados. [13] De manera similar, las redes transcripcionales , en las que los nodos son genes y están vinculados si un gen tiene una influencia genética reguladora hacia arriba o hacia abajo sobre el otro, tienen propiedades de red de mundo pequeño. [14]
En otro ejemplo, la famosa teoría de los " seis grados de separación " entre personas supone tácitamente que el dominio del discurso es el conjunto de personas vivas en un momento dado. Es casi seguro que el número de grados de separación entre Albert Einstein y Alejandro Magno es superior a 30 [15] y esta red no tiene propiedades de mundo pequeño. Una red igualmente limitada sería la red "fui a la escuela con": si dos personas fueron a la misma universidad con diez años de diferencia, es poco probable que tengan conocidos en común entre el alumnado.
De manera similar, el número de estaciones repetidoras por las que debe pasar un mensaje no siempre fue pequeño. En los días en que el correo se transportaba en mano o a caballo, el número de veces que una carta cambiaba de manos entre su origen y su destino habría sido mucho mayor que hoy. El número de veces que un mensaje cambiaba de manos en la época del telégrafo visual (alrededor de 1800-1850) estaba determinado por el requisito de que dos estaciones estuvieran conectadas mediante línea de visión.
Los supuestos tácitos, si no se examinan, pueden causar un sesgo en la literatura sobre gráficos a favor de encontrar redes de mundo pequeño (un ejemplo del efecto cajón de archivos resultante del sesgo de publicación ).
Algunos investigadores, como Albert-László Barabási , plantean la hipótesis de que la prevalencia de redes de mundos pequeños en los sistemas biológicos puede reflejar una ventaja evolutiva de dicha arquitectura. Una posibilidad es que las redes de mundos pequeños sean más resistentes a las perturbaciones que otras arquitecturas de red. Si este fuera el caso, proporcionaría una ventaja a los sistemas biológicos que están sujetos a daños por mutación o infección viral .
En una red mundial pequeña con una distribución de grados que sigue una ley de potencia , la eliminación de un nodo aleatorio rara vez causa un aumento dramático en la longitud media del camino más corto (o una disminución dramática en el coeficiente de agrupamiento ). Esto se debe al hecho de que la mayoría de los caminos más cortos entre nodos fluyen a través de concentradores , y si se elimina un nodo periférico es poco probable que interfiera con el paso entre otros nodos periféricos. Como la fracción de nodos periféricos en una red mundial pequeña es mucho mayor que la fracción de concentradores , la probabilidad de eliminar un nodo importante es muy baja. Por ejemplo, si se cerrara el pequeño aeropuerto de Sun Valley, Idaho , no aumentaría el número promedio de vuelos que otros pasajeros que viajan en Estados Unidos tendrían que tomar para llegar a sus respectivos destinos. Sin embargo, si la eliminación aleatoria de un nodo llega a un centro por casualidad, la longitud promedio de la ruta puede aumentar dramáticamente. Esto se puede observar anualmente cuando los aeropuertos centrales del norte, como el aeropuerto O'Hare de Chicago , se cierran debido a la nieve; Mucha gente tiene que tomar vuelos adicionales.
Por el contrario, en una red aleatoria, en la que todos los nodos tienen aproximadamente el mismo número de conexiones, es probable que eliminar un nodo aleatorio aumente ligera pero significativamente la longitud media de la ruta más corta para casi cualquier nodo eliminado. En este sentido, las redes aleatorias son vulnerables a perturbaciones aleatorias, mientras que las redes de mundos pequeños son robustas. Sin embargo, las redes de mundos pequeños son vulnerables a ataques dirigidos a centros, mientras que las redes aleatorias no pueden ser objeto de fallas catastróficas.
El principal mecanismo para construir redes de mundos pequeños es el mecanismo de Watts-Strogatz .
Las redes de mundos pequeños también pueden introducirse con retardo de tiempo, [16] lo que no sólo producirá fractales sino también caos [17] en las condiciones adecuadas, o transición al caos en redes dinámicas. [18]
Poco después de la publicación del mecanismo de Watts-Strogatz , Mashaghi y sus colaboradores desarrollaron enfoques para generar modelos de red que exhiben correlaciones de alto grado, preservando al mismo tiempo la distribución de grados deseada y las propiedades de mundo pequeño. Estos enfoques se basan en la transformación de borde dual y se pueden utilizar para generar modelos de redes de mundo pequeño con solución analítica para la investigación de estos sistemas. [19]
Los gráficos grado-diámetro se construyen de manera que el número de vecinos que tiene cada vértice en la red esté acotado, mientras que la distancia desde cualquier vértice dado en la red a cualquier otro vértice (el diámetro de la red) se minimice. La construcción de redes de mundos tan pequeños se realiza como parte del esfuerzo por encontrar gráficos de orden cercanos al límite de Moore .
Otra forma de construir una pequeña red mundial desde cero se ofrece en Barmpoutis et al. , [20] donde se construye una red con una distancia promedio muy pequeña y una agrupación promedio muy grande. Se proporciona un algoritmo rápido de complejidad constante, junto con mediciones de la robustez de los gráficos resultantes. Dependiendo de la aplicación de cada red, se puede comenzar con una de esas redes de "mundo ultrapequeño" y luego volver a cablear algunos bordes, o usar varias redes pequeñas como subgrafos de un gráfico más grande.
Las propiedades del mundo pequeño pueden surgir naturalmente en las redes sociales y otros sistemas del mundo real a través del proceso de evolución de doble fase . Esto es particularmente común cuando las limitaciones de tiempo o espacio limitan la adición de conexiones entre vértices. El mecanismo generalmente implica cambios periódicos entre fases, con conexiones que se agregan durante una fase "global" y se refuerzan o eliminan durante una fase "local".
Las redes de mundos pequeños pueden pasar de una clase sin escala a una clase de gran escala cuya distribución de conectividad tiene un corte brusco siguiendo un régimen de ley de potencia debido a restricciones que limitan la adición de nuevos enlaces. [21] Para restricciones suficientemente fuertes, las redes sin escala pueden incluso convertirse en redes de escala única cuya distribución de conectividad se caracteriza por una rápida decadencia. [21] También se demostró analíticamente que las redes sin escala son ultrapequeñas, lo que significa que la distancia se escala de acuerdo con . [22]
Las ventajas de las redes de mundos pequeños para los grupos de movimientos sociales son su resistencia al cambio debido al aparato de filtrado que implica el uso de nodos altamente conectados, y su mayor efectividad para transmitir información mientras se mantiene al mínimo el número de enlaces necesarios para conectar una red. [23]
El modelo de red del mundo pequeño es directamente aplicable a la teoría de grupos de afinidad representada en los argumentos sociológicos de William Finnegan . Los grupos de afinidad son grupos de movimientos sociales que son pequeños y semiindependientes comprometidos con un objetivo o función más amplio. Aunque en gran medida no están afiliados a nivel de nodo, algunos miembros de alta conectividad funcionan como nodos de conectividad, vinculando a los diferentes grupos a través de redes. Este modelo de mundo pequeño ha demostrado ser una táctica de organización de protesta extremadamente eficaz contra la acción policial. [24] Clay Shirky sostiene que cuanto más grande sea la red social creada a través de redes de mundos pequeños, más valiosos serán los nodos de alta conectividad dentro de la red. [23] Lo mismo puede decirse del modelo de grupo de afinidad, donde las pocas personas dentro de cada grupo conectadas con grupos externos permitieron una gran cantidad de movilización y adaptación. Un ejemplo práctico de esto es la creación de redes en pequeños mundos a través de grupos de afinidad que William Finnegan describe en referencia a las protestas de 1999 en Seattle ante la OMC .
Se ha demostrado que muchas redes estudiadas en geología y geofísica tienen características de redes de mundos pequeños. Redes definidas en sistemas de fractura y sustancias porosas han demostrado estas características. [25] La red sísmica en la región del sur de California puede ser una red de mundo pequeño. [26] Los ejemplos anteriores ocurren en escalas espaciales muy diferentes, lo que demuestra la invariancia de escala del fenómeno en las ciencias de la tierra.
Se han utilizado redes de mundos pequeños para estimar la usabilidad de la información almacenada en grandes bases de datos. La medida se denomina Medida de transformación de datos del pequeño mundo. [27] [28] Cuanto más se alineen los enlaces de la base de datos con una red de mundo pequeño, más probabilidades habrá de que un usuario pueda extraer información en el futuro. Esta usabilidad generalmente tiene el costo de la cantidad de información que se puede almacenar en el mismo repositorio.
Se ha demostrado que la red Freenet peer-to-peer forma una red de mundo pequeño en simulación, [29] permitiendo almacenar y recuperar información de una manera que aumenta la eficiencia a medida que crece la red.
Las soluciones de búsqueda de vecinos más cercanos , como HNSW, utilizan redes de mundos pequeños para encontrar de manera eficiente la información en grandes corpus de elementos. [30] [31]
Tanto las conexiones anatómicas en el cerebro [32] como las redes de sincronización de las neuronas corticales [33] exhiben una topología de mundo pequeño.
También se ha descubierto que la conectividad estructural y funcional en el cerebro refleja la topología de mundo pequeño de caminos cortos y de alta agrupación. [34] La estructura de la red se ha encontrado en la corteza de los mamíferos en todas las especies, así como en estudios de imágenes a gran escala en humanos. [35] Los avances en conectómica y neurociencia de redes han descubierto que el pequeño mundo de las redes neuronales está asociado con una comunicación eficiente. [36]
En las redes neuronales, la longitud corta entre los nodos y la alta agrupación en los centros de la red respaldan la comunicación eficiente entre las regiones del cerebro con el menor costo energético. [36] El cerebro procesa y se adapta constantemente a nueva información y el modelo de red de mundo pequeño respalda las intensas demandas de comunicación de las redes neuronales. [37] La alta agrupación de nodos forma redes locales que a menudo están funcionalmente relacionadas. La corta longitud del camino entre estos centros respalda una comunicación global eficiente. [38] Este equilibrio permite la eficiencia de la red global y al mismo tiempo equipa al cerebro para manejar las interrupciones y mantener la homeostasis, debido a que los subsistemas locales están aislados de la red global. [39] Se ha descubierto que la pérdida de la estructura de la red del mundo pequeño indica cambios en la cognición y un mayor riesgo de trastornos psicológicos. [9]
Además de caracterizar la conectividad funcional y estructural de todo el cerebro, sistemas neuronales específicos, como el sistema visual, exhiben propiedades de red de mundo pequeño. [6]
Una red de neuronas de un mundo pequeño puede exhibir memoria a corto plazo . Un modelo informático desarrollado por Sara Solla [40] [41] tenía dos estados estables, una propiedad (llamada biestabilidad ) que se cree que es importante en el almacenamiento de memoria . Un pulso de activación generó bucles autosostenidos de actividad de comunicación entre las neuronas. Un segundo pulso puso fin a esta actividad. Los pulsos cambiaron el sistema entre estados estables: flujo (grabar una "memoria") y estasis (mantenerla). Las redes neuronales de mundos pequeños también se han utilizado como modelos para comprender las convulsiones . [42]