Red compleja

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 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 (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, redes climáticas y redes sociales.

Definición

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 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 las redes dirigidas, estas características también incluyen la reciprocidad, el perfil de importancia de la 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.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 libres de escala y las redes de mundo pequeño, cuyo descubrimiento y definición son estudios de casos canónicos en el campo. Ambos se caracterizan por características estructurales específicas: distribuciones de grado de ley de potencia 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 red también han llamado la atención.

El campo continúa desarrollándose a un ritmo acelerado y ha reunido a investigadores de muchas áreas, incluidas las matemáticas, la física, los sistemas de energía eléctrica, la biología, el clima, la informática, la sociología, la epidemiología y otras. Las ideas y herramientas de la ciencia e 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; ciencia clínica; el modelado y diseño de redes de comunicación escalables como la generación y visualización de redes inalámbricas complejas; 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 el tema de numerosos libros tanto para el profano como para el experto.

Redes sin escala

Una red se llama libre de escala. 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 la que cada nodo tiene (aproximadamente) el mismo grado. Los ejemplos de redes con una sola escala incluyen el gráfico aleatorio de Erdős-Rényi (ER), los gráficos regulares aleatorios, las redes regulares y los hipercubos. Algunos modelos de redes en crecimiento que producen distribuciones de grado 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 pueda verse como un centro. Si hubiera tal umbral, la red no estaría libre de escala.

El interés en las redes sin escala comenzó a fines de la década de 1990 con el informe 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, interacción de proteínas redes, redes de correo electrónico, etc. La mayoría de estas "leyes de poder" informadas fallan cuando se las desafía con pruebas estadísticas rigurosas, pero la idea más general de las distribuciones de grado 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 cabría esperar si las aristas existieran de forma independiente y aleatoria (es decir, si siguieran una distribución de Poisson). Hay muchas maneras diferentes de construir una red con una distribución de grados de ley de potencias. El proceso de Yule es un proceso generativo canónico de leyes de potencia, y se conoce desde 1925. Sin embargo, es conocido por muchos otros nombres debido a su frecuente reinvención, por ejemplo, el principio Gibrat de Herbert A. Simon, el efecto Matthew, la ventaja acumulativa y el apego preferencial de Barabási y Albert por el poder. distribuciones de licenciatura en derecho. Recientemente, se han sugerido los gráficos geométricos hiperbólicos como otra forma de construir redes sin escala.

Algunas redes con una distribución de grado de ley de potencias (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. Dichas redes también pueden ser bastante sensibles a los ataques dirigidos destinados 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, se han implicado en la propagación de enfermedades (naturales y artificiales) en las redes sociales y de comunicación, y en la propagación de modas. (ambos modelados por un proceso de percolación o ramificación). Mientras que los gráficos aleatorios (ER) tienen una distancia promedio de orden log Nentre nodos, donde N es el número de nodos, el gráfico sin escala puede tener una distancia de log log N.

Redes de mundo pequeño

Una red se denomina red de mundo pequeño 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 sólo seis grados de separación, es decir, el diámetro de la correspondiente gráfico de conexiones sociales no es mucho más grande 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 sin problemas entre un gráfico aleatorio y una red.Su modelo demostró que con la adición de solo 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 "pequeño mundo" en el que el número medio de los bordes entre dos vértices 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 presentan 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 "pequeño mundo". Además de referirse al tamaño del diámetro de la red, también puede referirse a la concurrencia de un diámetro pequeño y un alto coeficiente de agrupamiento. 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 muy pequeño, mientras que las redes del mundo real a menudo tienen 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.

Redes espaciales

Muchas redes reales están incrustadas en el espacio. Los ejemplos incluyen, transporte y otras redes de infraestructura, redes cerebrales. Se han desarrollado varios modelos para redes espaciales.