En el contexto de la teoría de redes , una red compleja es un gráfico (red) con características topológicas no triviales , características que no ocurren en redes simples como redes o gráficos aleatorios , pero que a menudo ocurren en redes que representan sistemas reales. El estudio de redes complejas es un área joven y activa de investigación científica [1] [2] (desde 2000) inspirada en gran medida por hallazgos empíricos de redes del mundo real, como redes informáticas , redes biológicas , redes tecnológicas, redes cerebrales , [3 ] [4] [5] Redes climáticas y redes sociales .
La mayoría de las redes sociales , biológicas y tecnológicas muestran importantes características topológicas no triviales, con patrones de conexión entre sus elementos que no son ni puramente regulares ni puramente aleatorios. Tales características incluyen una cola pesada en la distribución de grados , un alto coeficiente de agrupamiento , asortatividad o desasortatividad entre vértices, estructura comunitaria y estructura jerárquica . En el caso de redes dirigidas, estas características también incluyen reciprocidad , perfil de importancia de tríada y otras características. Por el contrario, muchos de los modelos matemáticos de redes que se han estudiado en el pasado, como las redes y los gráficos aleatorios , no muestran estas características. Las estructuras más complejas pueden realizarse mediante redes con un número medio de interacciones. [6] Esto corresponde a que el máximo contenido de información ( entropía ) se obtiene para probabilidades medias.
Dos clases de redes complejas bien conocidas y muy estudiadas son las redes sin escala [7] y las redes de mundo pequeño , [8] [9] cuyo descubrimiento y definición son estudios de casos canónicos en este campo. Ambos se caracterizan por características estructurales específicas: distribuciones de grados de ley potencial para el primero y longitudes de camino cortas y alta agrupación para el segundo. Sin embargo, a medida que el estudio de redes complejas ha seguido creciendo en importancia y popularidad, muchos otros aspectos de las estructuras de redes también han atraído la atención.
El campo continúa desarrollándose a un ritmo rápido y ha reunido a investigadores de muchas áreas, incluidas matemáticas , física , sistemas de energía eléctrica, [10] biología , clima , informática , sociología , epidemiología y otras. [11] Se han aplicado ideas y herramientas de la ciencia y la ingeniería de redes al análisis de redes reguladoras metabólicas y genéticas; el estudio de la estabilidad y robustez de los ecosistemas; [12] ciencia clínica; [13] el modelado y diseño de redes de comunicación escalables como la generación y visualización de redes inalámbricas complejas; [14] y una amplia gama de otras cuestiones prácticas. La ciencia de redes es el tema de muchas conferencias en una variedad de campos diferentes, y ha sido objeto de numerosos libros tanto para el profano como para el experto.
Una red se llama libre de escala [7] [15] si su distribución de grados, es decir, la probabilidad de que un nodo seleccionado uniformemente al azar tenga un cierto número de enlaces (grado), sigue una función matemática llamada ley de potencia . La ley de potencia implica que la distribución de grados de estas redes no tiene una escala característica. Por el contrario, las redes con una única escala bien definida son algo similares a una red en el sentido de que cada nodo tiene (aproximadamente) el mismo grado. Ejemplos de redes con una sola escala incluyen el gráfico aleatorio Erdős-Rényi (ER) , los gráficos regulares aleatorios, las celosías regulares y los hipercubos . Algunos modelos de redes en crecimiento que producen distribuciones de grados invariantes de escala son el modelo de Barabási-Albert y el modelo de aptitud . En una red con una distribución de grados sin escala, algunos vértices tienen un grado que es órdenes de magnitud mayor que el promedio; estos vértices a menudo se denominan "centros", aunque este lenguaje es engañoso ya que, por definición, no existe un umbral inherente. por encima del cual un nodo puede verse como un centro. Si existiera tal umbral, la red no estaría libre de escala.
El interés en las redes sin escala comenzó a finales de la década de 1990 con el informe de descubrimientos de distribuciones de grados de ley de potencia en redes del mundo real como la World Wide Web , la red de sistemas autónomos (AS), algunas redes de enrutadores de Internet, interacción de proteínas. redes, redes de correo electrónico, etc. La mayoría de estas "leyes de potencia" reportadas fallan cuando se las cuestiona con pruebas estadísticas rigurosas, pero la idea más general de distribuciones de grados de cola pesada, que muchas de estas redes realmente exhiben (antes de que ocurran efectos de tamaño finito) ) - son muy diferentes de lo que uno esperaría si los bordes existieran de forma independiente y aleatoria (es decir, si siguieran una distribución de Poisson ). Hay muchas formas diferentes de construir una red con una distribución de grados de ley de potencia. El proceso de Yule es un proceso generativo canónico para las leyes de potencia y se conoce desde 1925. Sin embargo, se le conoce con muchos otros nombres debido a su frecuente reinvención, por ejemplo, el principio de Gibrat de Herbert A. Simon , el efecto Matthew, el efecto acumulativo. ventaja y apego preferencial de Barabási y Albert para las distribuciones de grados de ley de potencia. Recientemente, se han sugerido gráficos geométricos hiperbólicos como otra forma más de construir redes sin escala.
Algunas redes con una distribución de grados de ley potencial (y otros tipos específicos de estructura) pueden ser muy resistentes a la eliminación aleatoria de vértices; es decir, la gran mayoría de los vértices permanecen conectados entre sí en un componente gigante. Estas redes también pueden ser bastante sensibles a ataques dirigidos a fracturar la red rápidamente. Cuando el gráfico es uniformemente aleatorio excepto por la distribución de grados, estos vértices críticos son los de mayor grado y, por lo tanto, han estado implicados en la propagación de enfermedades (naturales y artificiales) en las redes sociales y de comunicación, y en la propagación de modas pasajeras. (ambos modelados mediante un proceso de percolación o ramificación ). Mientras que los gráficos aleatorios (ER) tienen una distancia promedio de orden log N [8] entre nodos, donde N es el número de nodos, los gráficos sin escala pueden tener una distancia de log log N.
Una red se denomina red de mundo pequeño [8] por analogía con el fenómeno del mundo pequeño (conocido popularmente como seis grados de separación ). La hipótesis del mundo pequeño, descrita por primera vez por el escritor húngaro Frigyes Karinthy en 1929 y probada experimentalmente por Stanley Milgram (1967), es la idea de que dos personas arbitrarias están conectadas por sólo seis grados de separación, es decir, el diámetro de su correspondiente El gráfico de conexiones sociales no es mucho mayor que seis. En 1998, Duncan J. Watts y Steven Strogatz publicaron el primer modelo de red de mundo pequeño, que a través de un único parámetro interpola suavemente entre un gráfico aleatorio y una red. [8] Su modelo demostró que con la adición de sólo un pequeño número de enlaces de largo alcance, un gráfico regular, en el que el diámetro es proporcional al tamaño de la red, se puede transformar en un "mundo pequeño" en el que el El número promedio de aristas entre dos vértices cualesquiera es muy pequeño (matemáticamente, debería crecer como el logaritmo del tamaño de la red), mientras que el coeficiente de agrupamiento se mantiene grande. Se sabe que una amplia variedad de gráficos abstractos exhiben la propiedad del mundo pequeño, por ejemplo, gráficos aleatorios y redes sin escala. Además, las redes del mundo real, como la World Wide Web y la red metabólica, también exhiben esta propiedad.
En la literatura científica sobre redes existe cierta ambigüedad asociada con el término "mundo pequeño". Además de referirse al tamaño del diámetro de la red, también puede referirse a la coexistencia de un diámetro pequeño y un coeficiente de agrupamiento alto . El coeficiente de agrupamiento es una métrica que representa la densidad de triángulos en la red. Por ejemplo, los gráficos aleatorios dispersos tienen un coeficiente de agrupamiento extremadamente pequeño, mientras que las redes del mundo real suelen tener un coeficiente significativamente mayor. Los científicos señalan que esta diferencia sugiere que los bordes están correlacionados en las redes del mundo real. Se han desarrollado enfoques para generar modelos de red que exhiben altas correlaciones, preservando al mismo tiempo la distribución de grados deseada y las propiedades de mundo pequeño. Estos enfoques se pueden utilizar para generar modelos de juguetes con solución analítica para la investigación de estos sistemas. [dieciséis]
Muchas redes reales están integradas en el espacio. Los ejemplos incluyen transporte y otras redes de infraestructura, redes cerebrales. [3] [4] Se han desarrollado varios modelos para redes espaciales. [17]