Red en evolución

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Las redes en evolución o red evolutiva 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 con el 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 vuelven parte de nuevas redes sociales o abandonan sus redes, cambiando los nodos en la red. Los conceptos de redes en evolución se basan en la teoría de redes establecida y ahora se están introduciendo en el estudio de redes en muchos campos diversos.

Antecedentes de la teoría de redes

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 Seven Bridges of Königsberg. La teoría de la red probabilística luego se desarrolló con la ayuda de ocho artículos famosos que estudiaban gráficos aleatorios escritos por Paul Erdős y Alfréd Rényi. El modelo de Erdős-Rényi (ER) supone que un grafo se compone de N nodos etiquetados donde cada par de nodos está conectado por una probabilidad preestablecida p.

Si bien la simplicidad del modelo ER lo ha ayudado a encontrar muchas aplicaciones, no describe con precisión muchas redes del mundo real. El modelo ER no genera agrupaciones locales ni 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 se construye una red como un enrejado de anillo regular, y luego los nodos se vuelven a cablear de acuerdo con alguna probabilidad β. 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.

A pesar de este logro, tanto el modelo ER como el de Watts y Storgatz no tienen en cuenta la formulación de hubs como 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 gráficos que son homogéneos en grado. En cambio, muchas redes no tienen 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.

Primer modelo de red en evolución: redes sin escala

El modelo Barabási-Albert (BA) fue el primer modelo ampliamente aceptado para producir redes sin escala. Esto se logró mediante la incorporación de la conexión preferencial y el crecimiento, donde los nodos se agregan a la red con el tiempo y es más probable que se vinculen con otros nodos con distribuciones de alto grado. El modelo BA se aplicó por primera vez a las distribuciones de grados en la web, donde ambos efectos pueden verse claramente. Se agregan nuevas páginas web con el tiempo, y es más probable que cada nueva página se vincule a centros altamente visibles como Google, que tienen distribuciones de alto grado, que a nodos con solo unos pocos enlaces. Formalmente este apego preferencial es: $p_{i}={frac {k_{i}}{displaystyle sum_{j}k_{j}}},$

Adiciones al modelo BA

El modelo BA fue el primer modelo en derivar 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 las suposiciones más simples necesarias para que surja una red sin escala, a saber, que hay un crecimiento lineal y un vínculo 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 se ha modificado desde entonces para capturar más completamente las propiedades de las redes en evolución mediante la introducción de algunas propiedades nuevas.

Aptitud física

Una preocupación con el 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 alto grado continúan dominando la red indefinidamente. Sin embargo, esto se puede paliar introduciendo una aptitud para cada nodo, que modifica la probabilidad de que se creen nuevos enlaces con ese nodo o incluso de que se eliminen enlaces a ese nodo.

Para preservar la conexión preferencial del modelo BA, esta aptitud se multiplica por la conexión preferencial basada en la distribución de grados para dar la verdadera probabilidad de que se cree un enlace que se conecta al nodo i. $Pi (k_{i})={frac {eta _{i}k_{i}}{displaystyle sum _{j}eta _{j}k_{j}}},$

¿Dónde $eta$ está la aptitud, que también puede depender del tiempo. Puede ocurrir un deterioro de la aptitud con respecto al tiempo y puede formalizarse mediante $Pi (k_{i})propto k_{i}(t-t_{i})^{{-nu }},$

donde $gama$ aumenta con $nu.$

Eliminación de nodos y recableado de enlaces

Surgen más complicaciones porque los nodos pueden eliminarse de la red con cierta probabilidad. Además, se pueden destruir los enlaces existentes y se pueden crear nuevos enlaces entre los 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 hacer crecer una red modelo con propiedades idénticas. Este crecimiento tendría lugar con una de las siguientes acciones ocurriendo en cada paso de tiempo:

Prob p: agregue un enlace interno.

Prob q: eliminar un enlace.

Problema: eliminar un nodo.

Prob 1-pqr: agregue un nodo.

Otras formas de caracterizar las redes en evolución

Además de los modelos de redes en crecimiento como se describió anteriormente, puede haber momentos en que otros métodos sean más útiles o convenientes para caracterizar ciertas propiedades de las redes en evolución.

Convergencia hacia el equilibrio

En los sistemas en red donde tiene lugar una toma de decisiones competitiva, la teoría de juegos se utiliza a menudo para modelar la dinámica del sistema, y la convergencia hacia el equilibrio puede considerarse como un motor de la evolución topológica. Por ejemplo, Kasthurirathna y Piraveenan han demostrado que cuando los individuos de un sistema muestran diferentes niveles de racionalidad, mejorar 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 en una red inicialmente aleatoria que simula una variedad de juegos clásicos, de modo que la red converge hacia los equilibrios de Nash mientras se le permite volver a cablear. Las redes se vuelven cada vez más libres de escala durante este proceso.

Tratar las redes en evolución como instantáneas sucesivas de una red estática

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, bordes, longitud de la ruta, componentes conectados) o para describir nodos específicos en el gráfico, como el número de enlaces o el coeficiente de agrupación. Estas propiedades se pueden estudiar individualmente como una serie de tiempo usando nociones de procesamiento de señales. Por ejemplo, podemos rastrear la cantidad de enlaces establecidos a un servidor por minuto mirando las sucesivas instantáneas de la red y contando estos enlaces en cada instantánea.

Desafortunadamente, la analogía de las instantáneas con una película también revela la principal dificultad de este enfoque: los intervalos 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 conserva 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.

Definir propiedades dinámicas

Puede ser importante observar las 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 los nodos. Se pueden definir otras propiedades similares y luego es posible rastrear estas propiedades a lo largo de la evolución. de una red y visualizarlos directamente.

Otro problema con el uso de instantáneas sucesivas es que solo pequeños cambios 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 el nacimiento, la muerte, la fusión, la división, el crecimiento y la contracción.

Aplicaciones

Casi todas las redes del mundo real son redes en evolución, ya que se construyen con el tiempo. Al variar las probabilidades respectivas descritas anteriormente, es posible usar el modelo BA expandido para construir una red con propiedades casi idénticas a muchas redes observadas. 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 se hubiera creado instantáneamente. Las redes reales en evolución que se están estudiando actualmente incluyen las redes sociales, las redes de comunicaciones, Internet, la red de actores de cine, la World Wide Web y las redes de transporte.

Otras lecturas

"Comprender la ciencia de redes", https://web.archive.org/web/20110718151116/http://www.zangani.com/blog/2007-1030-networkingscience
"Enlazados: La Nueva Ciencia de las Redes", A.-L. Barabási Perseus Publishing, Cambridge.

Contenido relacionado

Más resultados...