Red de mundo pequeño
Una red de mundo pequeño o red de mundillo es un tipo de gráfico matemático en el que la mayoría de los nodos no son vecinos entre sí, pero es probable que los vecinos de cualquier nodo dado sean vecinos entre sí y se puede llegar a la mayoría de los nodos desde cualquier otro nodo por un pequeño número de saltos o pasos. 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:
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 mundo pequeño de extraños unidos por una cadena corta de conocidos. Muchos gráficos empíricos muestran el efecto del mundo pequeño, incluidas las redes sociales, wikis como Wikipedia, redes de genes 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.
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.Señalaron que los gráficos podrían clasificarse de acuerdo con dos características estructurales independientes, a saber, el coeficiente de agrupación y la distancia promedio de nodo a nodo (también conocida como longitud de ruta más corta promedio). Los gráficos puramente aleatorios, construidos de acuerdo con 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 coeficiente de agrupación pequeño. 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 más alto de lo esperado por casualidad. Watts y Strogatz luego propusieron un modelo de gráfico novedoso, actualmente denominado modelo de Watts y Strogatz, con (i) una longitud de ruta más corta promedio pequeña y (ii) un coeficiente de agrupación grande.Este trabajo fue seguido por muchos estudios, incluyendo resultados exactos (Barrat y Weigt, 1999; Dorogovtsev y Mendes; Barmpoutis y Murray, 2010).
Propiedades de las redes de mundo pequeño
Las redes de mundo pequeño tienden a contener camarillas y casi camarillas, es decir, subredes que tienen conexiones entre casi dos nodos dentro de ellas. Esto se deriva de la propiedad definitoria de un alto coeficiente de agrupamiento. 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 a menudo se asocian con redes de mundo pequeño. Por lo general, hay una sobreabundancia de centros– nodos en la red con un alto número de conexiones (conocidos como nodos de alto grado). Estos concentradores sirven como conexiones comunes que median las longitudes de camino corto entre otros bordes. Por analogía, la red de vuelos de líneas aéreas del mundo pequeño tiene una longitud de ruta media pequeña (es decir, entre dos ciudades es probable que tenga que tomar tres vuelos o menos) porque muchos vuelos se enrutan a través de ciudades centrales. Esta propiedad a menudo se analiza considerando la fracción de nodos en 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 hubs superior 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 gorda.
El carácter de mundo pequeño de la red se ha cuantificado mediante un coeficiente pequeño 
Otro método para cuantificar el mundo pequeño de la red utiliza la definición original de la red del mundo pequeño comparando el agrupamiento de una red dada con una red de celosía equivalente y su longitud de ruta con una red aleatoria equivalente. La medida del mundo pequeño (
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 el agrupamiento de la red como la longitud de la ruta en relación con estas características en redes reticulares y aleatorias equivalentes. El Small World Index (SWI) se define como
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 (p. ej., tamaño, densidad, distribución de grados), existe una red para la cual ω ′ = 1 y, por lo tanto, ω pretende capturar hasta qué punto 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 que SWI tiene como objetivo capturar la medida 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.
Ejemplos de redes de mundo pequeño
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 alimentarias, 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. También se ha demostrado que las redes culturales y las redes de coocurrencia de palabras son redes de mundo pequeño.
Las redes de proteínas conectadas tienen propiedades de mundo pequeño, como leyes de potencia que obedecen a distribuciones de grado. 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.
Ejemplos de redes de mundo no pequeño
En otro ejemplo, la famosa teoría de los "seis grados de separación" entre las 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 y esta red no tiene propiedades de mundo pequeño. Una red con restricciones similares sería la red "fue 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.
Del mismo modo, el número de estaciones repetidoras por las que debe pasar un mensaje no siempre es pequeño. En la época en que el correo se transportaba a mano oa caballo, el número de veces que una carta cambiaba de mano entre su origen y su destino habría sido mucho mayor que en la actualidad. 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 por línea de visión.
Las suposiciones tácitas, 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 del cajón de archivos resultante del sesgo de publicación).
Robustez de la red
Algunos investigadores, como 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 mundo pequeño 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ño por mutación o infección viral.
En una red mundial pequeña con una distribución de grados que sigue una ley de potencias, la eliminación de un nodo aleatorio rara vez provoca un aumento drástico en la longitud media del camino más corto (o una disminución drástica en el coeficiente de agrupamiento). Esto se deriva del hecho de que la mayoría de las rutas más cortas 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 la cantidad promedio de vuelos que otros pasajeros que viajan en los 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 concentrador por casualidad, la longitud de ruta promedio puede aumentar drásticamente. 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 la eliminación de un nodo aleatorio aumente leve pero significativamente la longitud media de la ruta más corta para casi todos los nodos eliminados. En este sentido, las redes aleatorias son vulnerables a perturbaciones aleatorias, mientras que las redes de mundo pequeño son robustas. Sin embargo, las redes de mundo pequeño son vulnerables a los ataques dirigidos a los concentradores, mientras que las redes aleatorias no pueden ser objeto de fallas catastróficas.
Construcción de redes de mundo pequeño
El mecanismo principal para construir redes de mundo pequeño es el mecanismo de Watts-Strogatz.
Las redes de mundo pequeño también se pueden introducir con retardo de tiempo, lo que no solo producirá fractales sino también caos en las condiciones adecuadas, o transición al caos en redes dinámicas.
Los gráficos de grados-diámetro se construyen de tal 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 minimiza. La construcción de tales redes de mundos 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 red mundial pequeña desde cero se da en Barmpoutis et al. , donde se construye una red con una distancia media muy pequeña y un agrupamiento medio muy grande. Se proporciona un algoritmo rápido de complejidad constante, junto con medidas de la robustez de los gráficos resultantes. Dependiendo de la aplicación de cada red, uno 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 para 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 restricciones 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 mundo pequeño pueden cambiar de una clase sin escala a una clase de gran escala cuya distribución de conectividad tiene un corte brusco después de un régimen de ley de potencia debido a las restricciones que limitan la adición de nuevos enlaces. Para restricciones lo suficientemente fuertes, las redes sin escala pueden incluso convertirse en redes de una sola escala cuya distribución de conectividad se caracteriza por un rápido deterioro. También se demostró analíticamente que las redes sin escala son ultrapequeñas, lo que significa que la distancia escala según 
Aplicaciones
Aplicaciones a la sociología
Las ventajas de las redes de pequeños mundos para los grupos de movimientos sociales son su resistencia al cambio debido al aparato de filtrado del uso de nodos altamente conectados, y su mejor eficacia para transmitir información mientras se mantiene al mínimo la cantidad de enlaces necesarios para conectar una red.
El modelo de red de 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 una meta o función mayor. 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 efectiva contra la acción policial. Clay Shirky argumenta que cuanto más grande es la red social creada a través de redes de mundo pequeño, más valiosos son los nodos de alta conectividad dentro de la red.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 red mundial pequeña a través de grupos de afinidad que William Finnegan describe en referencia a las protestas de la OMC en Seattle en 1999.
Aplicaciones a las ciencias de la tierra
Se ha demostrado que muchas redes estudiadas en geología y geofísica tienen características de redes de mundo pequeño. Las redes definidas en sistemas de fractura y sustancias porosas han demostrado estas características. La red sísmica en la región del sur de California puede ser una red de mundo pequeño. 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.
Aplicaciones a la informática
Las redes de mundo pequeño se han utilizado para estimar la usabilidad de la información almacenada en grandes bases de datos. La medida se denomina Small World Data Transformation Measure. Cuanto más se alineen los enlaces de la base de datos con una red de mundo pequeño, más probable es que un usuario pueda extraer información en el futuro. Esta facilidad de uso generalmente tiene el costo de la cantidad de información que se puede almacenar en el mismo repositorio.
Se ha demostrado que la red de igual a igual de Freenet forma una red de mundo pequeño en simulación, lo que permite almacenar y recuperar información de una manera que escala la eficiencia a medida que crece la red.
Redes neuronales de mundo pequeño en el cerebro
Tanto las conexiones anatómicas en el cerebro como las redes de sincronización de las neuronas corticales exhiben una topología de mundo pequeño.
También se ha encontrado que la conectividad estructural y funcional en el cerebro refleja la topología del mundo pequeño de longitud de ruta corta y alta agrupación. 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. Los avances en la conectómica y la neurociencia de redes han encontrado que el pequeño mundo de las redes neuronales está asociado con una comunicación eficiente.
En las redes neuronales, la longitud de ruta 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 al costo energético más bajo. El cerebro está constantemente procesando y adaptándose a nueva información y el modelo de red de mundo pequeño respalda las intensas demandas de comunicación de las redes neuronales. La alta agrupación de nodos forma redes locales que a menudo están funcionalmente relacionadas. La longitud de ruta corta entre estos concentradores admite una comunicación global eficiente. Este equilibrio permite la eficiencia de la red global al mismo tiempo que equipa al cerebro para manejar las interrupciones y mantener la homeostasis, debido a que los subsistemas locales están aislados de la red global.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.
Además de caracterizar la conectividad funcional y estructural de todo el cerebro, los sistemas neuronales específicos, como el sistema visual, exhiben propiedades de red de mundo pequeño.
Una red de neuronas de un mundo pequeño puede exhibir memoria a corto plazo. Un modelo de computadora desarrollado por Sara Solla tenía dos estados estables, una propiedad (llamada biestabilidad) que se pensaba que era 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 (grabando un "recuerdo") y estasis (manteniéndolo). Las redes neuronales de mundo pequeño también se han utilizado como modelos para comprender las convulsiones.
Contenido relacionado
Máquina de código P
Programación defensiva
Código de bytes