Red en evolución

Las redes evolutivas son redes que cambian en función del tiempo. Son una extensión natural de la ciencia de redes , ya que casi todas las redes del mundo real evolucionan con el tiempo, ya sea agregando o eliminando nodos o enlaces a lo largo del tiempo. A menudo, todos estos procesos ocurren simultáneamente, como en las redes sociales , donde las personas hacen y pierden amigos con el tiempo, creando y destruyendo así bordes, y algunas personas se convierten en parte de nuevas redes sociales o abandonan sus redes, cambiando los nodos de la red. Los conceptos de redes evolutivas se basan en la teoría de redes establecida y ahora se están introduciendo en el estudio de redes en muchos campos diversos.

El estudio de las redes tiene sus fundamentos en el desarrollo de la teoría de grafos , que fue analizada por primera vez por Leonhard Euler en 1736 cuando escribió el famoso artículo Los siete puentes de Königsberg . La teoría probabilística de redes se desarrolló luego con la ayuda de ocho artículos famosos que estudiaban grafos aleatorios escritos por Paul Erdős y Alfréd Rényi . El modelo Erdős–Rényi (ER) supone que un grafo está compuesto de N nodos etiquetados donde cada par de nodos está conectado por una probabilidad preestablecida p .

Si bien la simplicidad del modelo ER ha ayudado a encontrar muchas aplicaciones, no describe con precisión muchas redes del mundo real. El modelo ER no genera agrupamiento local y cierres triádicos con tanta frecuencia como se encuentran en las redes del mundo real. Por lo tanto, se propuso el modelo de Watts y Strogatz , mediante el cual una red se construye como una red de anillos regular y luego los nodos se reconectan de acuerdo con cierta probabilidad β . ^[1] Esto produce una red agrupada localmente y reduce drásticamente la longitud de ruta promedio , creando redes que representan el fenómeno del mundo pequeño observado en muchas redes del mundo real. ^[2]

A pesar de este logro, tanto el modelo ER como el de Watts y Storgatz no tienen en cuenta la formulación de los ejes que se observa en muchas redes del mundo real. La distribución de grados en el modelo ER sigue una distribución de Poisson , mientras que el modelo de Watts y Strogatz produce grafos que son homogéneos en grado . En cambio, muchas redes son libres de escala, lo que significa que su distribución de grados sigue una ley de potencia de la forma:

${\displaystyle P(k)\sim k^{-\gamma }}$

Este exponente resulta ser aproximadamente 3 para muchas redes del mundo real, sin embargo, no es una constante universal y depende continuamente de los parámetros de la red ^[3].

El modelo Barabási–Albert (BA) fue el primer modelo ampliamente aceptado para producir redes sin escala . Esto se logró incorporando la vinculación preferencial y el crecimiento, donde los nodos se agregan a la red con el tiempo y tienen más probabilidades de vincularse con otros nodos con distribuciones de alto grado. El modelo BA se aplicó por primera vez a las distribuciones de grado en la web, donde ambos efectos se pueden ver claramente. Se agregan nuevas páginas web con el tiempo y es más probable que cada página nueva se vincule con centros altamente visibles como Google , que tienen distribuciones de alto grado, que con nodos con solo unos pocos vínculos. Formalmente, esta vinculación preferencial es:

${\displaystyle p_{i}={\frac {k_{i}}{\displaystyle \sum _{j}k_{j}}},}$

El modelo BA fue el primer modelo que derivó la topología de la red a partir de la forma en que se construyó la red con nodos y enlaces que se agregaron con el tiempo. Sin embargo, el modelo solo hace los supuestos más simples necesarios para que surja una red sin escala, a saber, que hay crecimiento lineal y unión preferencial lineal. Este modelo mínimo no captura variaciones en la forma de la distribución de grados, variaciones en el exponente de grados o el coeficiente de agrupamiento independiente del tamaño . Por lo tanto, el modelo original ha sido modificado desde entonces ^{[ ¿por quién? ]} para capturar de manera más completa las propiedades de las redes en evolución mediante la introducción de algunas propiedades nuevas.

Una de las preocupaciones del modelo BA es que las distribuciones de grado de cada nodo experimentan una fuerte retroalimentación positiva , por lo que los primeros nodos con distribuciones de grado alto continúan dominando la red indefinidamente. Sin embargo, esto se puede aliviar introduciendo una aptitud para cada nodo, que modifica la probabilidad de que se creen nuevos vínculos con ese nodo o incluso de que se eliminen vínculos con ese nodo. ^[4]

Para preservar la conexión preferencial del modelo BA, esta aptitud se multiplica luego por la conexión preferencial basada en la distribución de grados para obtener la probabilidad real de que se cree un enlace que se conecte al nodo i .

${\displaystyle \Pi (k_{i})={\frac {\eta _{i}k_{i}}{\displaystyle \sum _{j}\eta _{j}k_{j}}},}$

¿Dónde está la aptitud, que también puede depender del tiempo? Puede ocurrir una disminución de la aptitud con respecto al tiempo y puede formalizarse mediante ${\displaystyle \eta }$

${\displaystyle \Pi (k_{i})\propto k_{i}(t-t_{i})^{-\nu },}$

donde aumenta con${\displaystyle \gamma }$${\displaystyle \nu .}$

Surgen más complicaciones porque los nodos pueden eliminarse de la red con cierta probabilidad. Además, los enlaces existentes pueden destruirse y pueden crearse nuevos enlaces entre nodos existentes. La probabilidad de que ocurran estas acciones puede depender del tiempo y también puede estar relacionada con la aptitud del nodo. Se pueden asignar probabilidades a estos eventos estudiando las características de la red en cuestión para desarrollar una red modelo con propiedades idénticas. Este crecimiento se llevaría a cabo con una de las siguientes acciones ocurriendo en cada paso de tiempo:

Prob p: agregar un enlace interno.

Prob q: eliminar un enlace.

Prob r: eliminar un nodo.

Prob 1-pqr: agregar un nodo.

Además de desarrollar modelos de red como los descritos anteriormente, puede haber ocasiones en que otros métodos sean más útiles o convenientes para caracterizar ciertas propiedades de redes en evolución.

En los sistemas en red donde se toman decisiones competitivas, la teoría de juegos se utiliza a menudo para modelar la dinámica del sistema, y ​​la convergencia hacia los equilibrios puede considerarse un factor impulsor de la evolución topológica. Por ejemplo, Kasthurirathna y Piraveenan ^[5] han demostrado que cuando los individuos de un sistema muestran distintos niveles de racionalidad, la mejora de la racionalidad general del sistema podría ser una razón evolutiva para el surgimiento de redes sin escala. Lo demostraron aplicando presión evolutiva sobre una red inicialmente aleatoria que simula una serie de juegos clásicos, de modo que la red converge hacia los equilibrios de Nash mientras se le permite volver a conectar. Las redes se vuelven cada vez más sin escala durante este proceso.

La forma más común de ver las redes en evolución es considerándolas como redes estáticas sucesivas. Esto podría conceptualizarse como las imágenes fijas individuales que componen una película . Existen muchos parámetros simples para describir una red estática (número de nodos, aristas, longitud de ruta, componentes conectados) o para describir nodos específicos en el gráfico, como el número de enlaces o el coeficiente de agrupamiento. Estas propiedades pueden luego estudiarse individualmente como una serie temporal utilizando nociones de procesamiento de señales. ^[6] Por ejemplo, podemos rastrear el número de enlaces establecidos a un servidor por minuto mirando las instantáneas sucesivas de la red y contando estos enlaces en cada instantánea.

Lamentablemente, la analogía de las instantáneas con una película también revela la principal dificultad de este enfoque: los pasos de tiempo empleados rara vez son sugeridos por la red y, en cambio, son arbitrarios. El uso de pasos de tiempo extremadamente pequeños entre cada instantánea preserva la resolución, pero en realidad puede ocultar tendencias más amplias que solo se vuelven visibles en escalas de tiempo más largas. Por el contrario, el uso de escalas de tiempo más grandes pierde el orden temporal de los eventos dentro de cada instantánea. Por lo tanto, puede ser difícil encontrar la escala de tiempo adecuada para dividir la evolución de una red en instantáneas estáticas.

Puede ser importante observar propiedades que no se pueden observar directamente al tratar las redes en evolución como una secuencia de instantáneas, como la duración de los contactos entre nodos ^[7]. Se pueden definir otras propiedades similares y luego es posible rastrear estas propiedades a través de la evolución de una red y visualizarlas directamente.

Otro problema con el uso de instantáneas sucesivas es que sólo cambios leves en la topología de la red pueden tener grandes efectos en el resultado de los algoritmos diseñados para encontrar comunidades. Por lo tanto, es necesario utilizar una definición no clásica de comunidades que permita seguir la evolución de la comunidad a través de un conjunto de reglas como nacimiento, muerte, fusión, división, crecimiento y contracción. ^{[8] [9]}

Casi todas las redes del mundo real son redes en evolución, ya que se construyen a lo largo del tiempo. Al variar las respectivas probabilidades descritas anteriormente, es posible utilizar el modelo BA expandido para construir una red con propiedades casi idénticas a muchas redes observadas. ^[10] Además, el concepto de redes libres de escala nos muestra que la evolución temporal es una parte necesaria para comprender las propiedades de la red y que es difícil modelar una red existente como si hubiera sido creada instantáneamente. Las redes en evolución reales que se están estudiando actualmente incluyen redes sociales , redes de comunicaciones , Internet , la red de actores de cine , la World Wide Web y redes de transporte .

• "Entendiendo la ciencia de redes", https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
• "Linked: La nueva ciencia de las redes", A.-L. Barabási Perseus Publishing, Cambridge.