En el contexto de la teoría de redes , una red compleja es un grafo (red) con características topológicas no triviales , características que no ocurren en redes simples como redes o grafos 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 de computadoras , 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 características topológicas no triviales sustanciales, 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 disasortatividad entre vértices, estructura de comunidad y estructura jerárquica . En el caso de redes dirigidas, estas características también incluyen reciprocidad , perfil de significancia 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 los retículos y los grafos 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 al hecho de que el contenido máximo de información ( entropía ) se obtiene para probabilidades medias.
Dos clases de redes complejas muy conocidas y estudiadas son las redes sin escala [7] y las redes de mundo pequeño [8] [9], cuyo descubrimiento y definición son casos de estudio canónicos en el campo. Ambas se caracterizan por características estructurales específicas: distribuciones de grado de ley de potencia para las primeras y longitudes de ruta cortas y alta agrupación para las segundas. Sin embargo, a medida que el estudio de redes complejas ha seguido creciendo en importancia y popularidad, muchos otros aspectos de las estructuras de red 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 las matemáticas , la física , los sistemas de energía eléctrica, [10] la biología , el clima , la informática , la sociología , la epidemiología y otras. [11] Las ideas y herramientas de la ciencia y la ingeniería de redes se han aplicado al análisis de redes reguladoras metabólicas y genéticas; el estudio de la estabilidad y robustez de los ecosistemas; [12] la 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 lego 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. Los ejemplos de redes con una única escala incluyen el grafo aleatorio Erdős–Rényi (ER) , los grafos regulares aleatorios, las redes regulares y los hipercubos . Algunos modelos de redes en crecimiento que producen distribuciones de grados invariantes en la escala son el modelo Barabási–Albert y el modelo de aptitud . En una red con una distribución de grados libre de 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 pueda verse como un centro. Si existiera ese umbral, la red no sería libre de escala.
El interés en las redes libres de escala comenzó a fines de la década de 1990 con los informes de descubrimientos de distribuciones de grado 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, redes de interacción de proteínas, redes de correo electrónico, etc. La mayoría de estas "leyes de potencia" reportadas fallan cuando se cuestionan con pruebas estadísticas rigurosas, pero la idea más general de distribuciones de grado de cola pesada, que muchas de estas redes exhiben genuinamente (antes de que ocurran los 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 grado de ley de potencia. El proceso de Yule es un proceso generativo canónico para leyes de potencia, y se conoce desde 1925. Sin embargo, se lo conoce con muchos otros nombres debido a su frecuente reinvención, por ejemplo, el principio de Gibrat de Herbert A. Simon , el efecto Matthew , la ventaja acumulativa y la fijación preferencial de Barabási y Albert para distribuciones de grado de ley de potencia. Recientemente, se han sugerido los gráficos geométricos hiperbólicos como otra forma de construir redes libres de escala.
Algunas redes con una distribución de grados de ley de potencia (y otros tipos específicos de estructura) pueden ser altamente 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. Dichas redes también pueden ser bastante sensibles a ataques dirigidos a fracturar la red rápidamente. Cuando el grafo es uniformemente aleatorio excepto por la distribución de grados, estos vértices críticos son los que tienen el grado más alto y, por lo tanto, han sido implicados en la propagación de enfermedades (naturales y artificiales) en redes sociales y de comunicación, y en la propagación de modas (ambas modeladas por un proceso de percolación o ramificación ). Mientras que los grafos aleatorios (ER) tienen una distancia promedio de orden log N [8] entre nodos, donde N es el número de nodos, el grafo libre de escala puede 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, que fue 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 solo seis grados de separación, es decir, el diámetro del grafo correspondiente 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 solo parámetro interpola suavemente entre un grafo 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 grafo 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 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 grafos abstractos exhiben la propiedad de mundo pequeño, por ejemplo, grafos aleatorios y redes libres de 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 coocurrencia 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 grafos aleatorios dispersos tienen un coeficiente de agrupamiento extremadamente pequeño, mientras que las redes del mundo real a menudo tienen un coeficiente significativamente mayor. Los científicos señalan esta diferencia como una sugerencia de 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, al tiempo que preservan la distribución de grados deseada y las propiedades de mundo pequeño. Estos enfoques se pueden utilizar para generar modelos de juguete analíticamente solucionables para la investigación de estos sistemas. [16]
Existen muchas redes reales integradas en el espacio, como las redes de transporte y otras redes de infraestructura, o las redes cerebrales. [3] [4] Se han desarrollado varios modelos de redes espaciales. [17]