« Cómo medir la Complej… « || Inicio || » Estructurando y consu… »

Redes Booleanas

Última modificación: 23 de Noviembre de 2018, y ha tenido 946 vistas

Etiquetas utilizadas: || || ||

La Teoría de Sistemas Complejos trabaja sobre sistemas dinámicos que tienen un gran número de variables, en los que el comportamiento puede ser arbitrariamente complejo. Por tanto, es importante disponer de una serie de ejemplos de sistemas dinámicos, a modo de modelos de control, que puedan ser investigados con mayor comodidad y en los que podamos controlar o predecir de alguna forma su comportamiento.

Las redes booleanas (aquellas que tienen únicamente variables binarias) constituyen este tipo de sistemas complejos dinámicos canónicos, y muestran de forma mucho más sencilla comportamientos observados en sistemas reales.

Introducción

Una variable booleana es aquella que puede tomar únicamente dos valores (\(0/1\), o \(-1/1\), los valores concretos son irrelevantes). Una red booleana es un conjunto de \(N\) variables booleanas que pueden interactuar entre si de acuerdo a ciertas reglas que llamaremos funciones de acoplamiento (una función de acoplamiento booleana es simplemente una función \(f:\{0,1\}^K \to \{0,1\}\)).

Sobre esta red consideraremos una dinámica discreta temporal (es decir, el tiempo \(t\in \mathbf{N}\)) en la que el valor de cada variable en la siguiente unidad de tiempo está determinado por el resultado de las funciones de acoplamiento actuando sobre las variables booleanas que interactúan con ella.

En consecuencia, toda red booleana puede ser representada por medio de un grafo dirigido que tiene en los nodos las variables booleanas involucradas.

El campo de las redes booleanas fue introducido a finales de 1960 por Kauffman con el fin de dar una explicación al proceso de diferenciación funcional que se podía observar entre las células de un organismo, de forma que esta diferenciación puede obtenerse como el atractor de la dinámica existente en la red. Su teoría ha ido confirmándose con resultados experimentales desde entonces, y la misma metodología se ha aplicado a un rango más amplio de problemas (como es el modelado de redes neuronales).

Veremos en las siguientes líneas que las redes booleanas, a pesar de simplificar el modelo informativo sobre el que trabajan los sistemas dinámicos (ya que muchas veces el mundo real trabaja sobre variables continuas, aunque otras muchas veces, como en el caso de las redes neuronales, la existencia de umbrales de disparo, hace que el proceso de discretización sea natural), presentan comportamientos generales que se esperan en sistemas complejos mucho más elaborados: comportamientos regulares y caóticos, auto-organización, transiciones de fase, etc.

El tipo más simple de redes booleanas son las conocidas como Redes \(N-K\) o redes de Kauffman. Tienen como soporte una red regular de \(N\) nodos y grado \(K\). Las funciones de acoplamiento se eligen aleatoriamente entre todas las posibles aplicaciones binarias \(K\)-arias.

No se corresponden con ningún proceso del mundo real, sino que constituyen un modelo abstracto, principalmente debido a que las redes reales usan funciones de acoplamiento específicas que vienen determinadas por la estructura física real y las interacciones biológicas del sistema considerado. Como a menudo tanto estas funciones como las interacciones (topología) son desconocidas, este tipo de redes abstractas pueden ser un buen punto de partida para analizar comportamientos generales.

A continuación presentamos la formalización general de la redes booleanas, no únicamente de las redes \(N-K\).

Para una definición completa de la red booleana hemos de especificar:

  1. La conectividad de cada elemento de la red, \(K_i\). De donde \(<K>=\frac{1}{N}\sum_{i=1}^N K_i\).
  2. El entorno entrante de cada nodo: \(N_{in}(i)=\{j_{i1},\dots,j_{iK_i}\}\), podría ocurrir que \(i\in N_{in}(i)\).
  3. Las reglas de evolución, o funciones de acoplamiento, de cada nodo, \(f_i\).

Denotaremos por \(\{\sigma_i\in \{0,1\}: i=1,2,\dots,N\}\) al conjunto de las \(N\) variables booleanas de la red, y por \(\sigma_i(t)\) el valor de dicha variable en el tiempo \(t\). De esta forma, el estado del sistema en \(t\) será denotado por el vector booleano \(\Sigma_t=(\sigma_1(t), \sigma_2(t),\dots,\sigma_N(t)) \in \Omega=2^N\).

Para un nodo \(1\leq i\leq N\) la dinámica evolutiva del nodo viene determinada por:

\[\sigma_i(t+1)=f_i(\sigma_{j_{i1} }(t),\dots,\sigma_{j_{iK_i} }(t)) \]

En la literatura habitual sobre redes booleanas solemos encontrar dos topologias comunes: retículos regulares; y redes de Kauffman (que son casos particulares de redes aleatorias de Erdös-Rényi); aunque en general se pueden definir sobre cualquier topología posible.

Respecto a las funciones de acoplamiento, suele ser habitual hacer las siguientes elecciones:

  1. Distribución uniforme: (las originales de Kauffman) cada posible función de acoplamiento tiene la misma probabilidad de ser usada (hay \(2^{2^K}\) funciones de acomplamiento distintas para cada nodo de grado \(K\)).
  2. Desviación con probabilidad \(p\): la probabilidad de que una función de acoplamiento ocurra es proporcional a \(p\) si devuelve \(0\), y \((1-p)\) si devuelve \(1\).
  3. Canalizadas o forzadas: el valor de la función se determina por uno de sus argumentos (vecinos del nodo al que se aplica la función).
  4. Funciones aditivas: usadas para simular las propiedades aditivas de la sinapsis neuronal:

\[\sigma_i(t+1)=\Phi(h+\sum_{j=1}^N c_{ij}\sigma_j(t))\]

donde \(c_{ij}\in \{0,1\}\) refleja la existencia o no de una conexión entre el nodo \(i\) y el nodo \(j\), \(\Phi\) es una función moduladora y \(h\) es una constante.

Además, estas funciones pueden considerarse fijas (en cada nodo se ejecuta siempre la misma función de acoplamiento), aleatorias (en cada nodo, y en cada iteración, se cambia la función de acoplamiento al azar; incluso se puede llegar a cambiar la red subyacente manteniendo las características generales, como el grado), o usar algún tipo de algoritmo para determinar cómo ajustar las funciones de acomplamiento en cada paso (como podría ser un algoritmo genético).

Respecto a los modos de ejecución de la red, pueden contemplarse esencialmente dos elecciones:

  1. Actualización sincronizada: todas las variables se actualizan simultáneamente en función de los valores de la red en el paso anterior.
  2. Actualización asíncrona: se actualiza únicamente una variable en cada paso, que puede ser seleccionada al azar entre las variables existente, o por algún orden preestablecido.

La elección del modo de ejecución no afecta al comportamiento asintótico de la dinámica, pero sí que puede afectar a la existencia y propiedades de ciclos y atractores. Lo más habitual es trabajar con funciones de acoplamiento fijas, sobre una estructura fija, y con actualización sincronizada.

Las dinámicas booleanas que se consiguen por los procedimientos anteriores corresponden a trayectorias sobre \(\Omega\), que es un espacio finito y, por lo tanto, si trabajamos con una asignación fija de funciones de acoplamiento, el comportamiento es cíclico a partir de un tiempo. Este ciclo final actúa a modo de atractor. Los ciclos de longitud \(1\) son puntos fijos atractores.

La dinámica de las Redes Booleanas

A continuación vamos a analizar la dinámica de las redes booleanas generales, y haremos análisis concretos y más detallados de las redes \(N-K\). Veremos que aparecerán dos conceptos de central importancia: la relación entre robustez de la red y el flujo de información que se produce; y la caracterización de la dinámica global, que veremos que puede ser estable, crítica o caótica.

Flujo de información a través de la Redes

En general, en el caso de modelos aleatorios, el valor y evolución de un nodo concreto no tiene mucho sentido, pero sí puede ser interesante estudiar cómo reacciona este nodo frente a cambios, ya sea en las condiciones inicales o de alguna de las funciones de acoplamiento en las que interviene.

En las redes reales (por ejemplo, las redes biológicas), es importante que el sistema se comporte robustamente, de forma que una excesiva sensibilidad a pequeños daños o cambios en las condiciones no debe provocar un cambio cualitativo en el comportamiento asintótico. En este sentido, diremos que un sistema es robusto si dos condiciones iniciales similares producen comportamientos similares a largo plazo.

Para definir formalmente la similaridad de las condiciones iniciales y de la evolución, vamos a trabajar con la distancia de Hamming:

Dados \(\Sigma_0=(\sigma_1,\dots,\sigma_N)\) y \(\Sigma_1=(\sigma'_1,\dots,\sigma'_N)\) dos configuraciones de \(\Omega\), la distancia de Hamming entre ellas se define como:

\[ D(\Sigma_0, \Sigma_1)=\sum_{i=1}^N (\sigma_i - \sigma'_i)^2\]

Como, en general, la configuración depende del tiempo, cuando no haya posibilidad de confusión notaremos:

\[ D(t)=D(\Sigma_0(t), \Sigma_1(t))=\sum_{i=1}^N (\sigma_i(t) - \sigma'_i(t))^2\]

Paralelamente, definimos la superposición normalizada de dos configuraciones como:

\[a(t)=1-\frac{D(t)}{N}=1-\frac{1}{N} \sum_{i=1}^N (\sigma^2_i(t)-2\sigma_i(t)\sigma'_i(t)+\sigma'^2_i(t))\]

En el caso en que no haya desviación, y los valores \(0/1\) sean igualmente probables, se tiene que \(\frac{1}{N} \sum_i \sigma_i^2(t) \approx \frac{1}{N} \sum_i \sigma'^2_i(t) \approx \frac{1}{2}\), por lo que \(a(t)\approx 1-\frac{2}{N} \sum_{i=1}^N \sigma_i(t)\sigma'_i(t)\).

En media, dos configuraciones aleatorias tienen una distancia de Hamming de \(N/2\), por lo que la superposición normalizada es en media \(1/2\).

La diferencia entre dos estados iniciales puede ser vista como información, por lo que podríamos analizar cómo evoluciona la información a medida que las trayectorias de ambos estados se desarrolla en el tiempo. De esta forma:

  1. Si \(\lim_{t\to \infty} a(t) = 1\), significa que ambas trayectorias terminan confundiéndose asintóticamente, por lo que se habla de que ha habido una pérdida de información en el sistema (ha perdido la capacidad de diferenciar ambos estados).
  2. Si \(\lim_{t\to \infty} a(t) = a^*<1\), significa que el sistema es capaz de recordar que ambas configuraciones eran distintas.

El sistema es robusto cuando la información se pierde de forma generalizada. Este concepto de robustez depende del valor de \(a^*\), si este valor es positivo, entonces dos trayectorias que comienzan desde configuraciones similares mantendrán cierta similitud a lo largo del tiempo.

Junto al análisis de la evolución de la información a largo plazo, podemos estar interesados también en cómo se procesa ésta en periodos temporales más cortos. Para ello, supongamos que podemos escribir la distancia de Hamming entre dos configuraciones como:

\[D(t)\equiv D(0) e^{\lambda t}\]

donde \(0<D(0)\ll N\) y se supone que esta aproximación únicamente es válida para valores de \(t\) relativamente pequeños (ya que en algunos casos la exponencial podría superar el valor máximo de \(D\) en muy poco tiempo). En este caso, podemos distinguir varios comportamientos en función del parámetro \(\lambda\):

  1. Fase Caótica (\(\lambda > 0\)). En este caso, la distancia de Hamming crece exponencialmente, lo que significa que dos órbitas inicialmente cercanas serán rápidamente muy distintas. Se ha comprobado que este comportamiento se da en redes de Kauffman con valores de \(K\) muy altos, pero no en sistemas biológicos reales.
  2. Fase de Estabilización (\(\lambda <0\)). Dos trayectorias cercanas convergen al mismo atractor. Este comportamiento se ha encontrado para valores de \(K\) bajos. El sistemas es localmente robusto.
  3. Fase Crítica (\(\lambda =0\)). En este caso la distancia de Hamming no es exponencial, sino que seguirá un comportamiento polinomial, por lo que no es predecible a priori qué pasará con la información.

Se puede observar que los tres comportamientos posibles anteriores se encuentran en las redes de Kauffman cuando el tamaño de variables se hace suficientemente grande. Veamos cómo ocurre esto haciendo uso de la teoría del campo medio.

Una Teoría del Campo Medio es, simplemente, un tratamiento del modelo a nivel micro que establece que la influencia de los elementos del sistema sobre el resto se hace de forma agrupada, como una media de todas las interacciones posibles.

Apliquemos la teoría del campo medio al modelo de Kauffman \(N-K\), donde toda función de acoplamiento es igual de probable, y cada variable está, por media, interviniendo en la evolución de otras \(K\) variables. Por tanto, si consideramos la evolución de dos trayectorias, \(\Sigma_t\) y \(\Sigma'_t\), las variables en que se diferencian, \(D(t)\), afectarán a una media de \(KD(t)\) funciones de acoplamiento. En media, cada función de acoplamiento cambia un valor con probabilidad \(\frac{1}{2}\), por lo que el número de diferencias entre \(\Sigma_{t+1}\) y \(\Sigma'_{t+1}\) será:

\[D(t+1)=\frac{K}{2}D(t)\]

De donde podemos deducir que \(D(t)\) sigue una ley similar a la expuesta anteriormente:

\[D(t)=\left(\frac{K}{2}\right)^t D(0)=D(0) e^{t\ln(K/2)}\]

Por lo que, en función de \(K\) se concluye que: si \(K>2\) el sistema es caótico; si \(K<2\) el sistema es estable; y si \(K=2\) el sistema es crítico. En este último caso, el método no puede discernir qué pasa con dos trayectorias puntuales, ya que la regla de evolución solo sucede en media (en general, será menos preciso cuanto más cerca estemos de \(K=2\)).

Se puede comprobar que la teoría del campo medio funciona bien en retículos físicos regulares en espacios de dimensión alta, y sin embargo falla en dimensiones bajas. Las redes de Kauffman no tienen dimensión predefinida, pero la conectividad, \(K\), parece jugar un papel análogo.

El Diagrama de Fase

En el desarrollo anterior hemos supuesto que las funciones de acoplamiento toman los valores \(0/1\) con igual probabilidad. Podemos considerar un caso más general en el que se tome cada valor con probabilidades respectivas \(p/(1-p)\). En este caso, podríamos decir que la conectividad crítica, en la que el comportamiento del sistema cambia, sería \(K_c(p)\), o si dejamos fija la conectividad, obtendríamos que la probabilidad crítica en la que se produce este cambio es \(p_c(K)\). De esta forma, para \(K<K_c\) el sistema es estable, y para \(K>K_c\) el sistema es caótico.

Debemos observar que la superposición entre dos estados, \(a(t)=1-D(t)/N\), puede interpretarse como la probabilidad de que dos vértices tengan el mismo valor en los estados comparados. Por tanto, la probabilidad de que todos los vértices que intervienen en una función de acoplamiento sean iguales para ambos estados será:

\[\rho_K=[a(t)]^K\]

En caso de que los argumentos de entrada de la función de acoplamiento sean iguales, la probabilidad de que los resultados lo sean es \(2p(1-p)\). Si unimos esto al hecho de que la probabilidad de que al menos un elemento de esa función tenga valores distintos en ambos estados es \(1-\rho_K\), obtenemos que la probabilidad de que los estados sean distintos en el siguiente paso es \((1-\rho_K)2p(1-p)\). Por tanto:

\[a(t+1)=1- (1-\rho_K)2p(1-p)=1-\frac{1-[a(t)]^K}{K_c}\]

donde

\[K_c=\frac{1}{2p(1-p)},\ p_c=\frac{1}{2}\pm \sqrt{\frac{1}{4}-\frac{1}{2K} }\]

Por lo que el punto fijo verifica:

\[a^*=1-\frac{1-[a^*]^K}{K_c}\]

que tiene como una de las soluciones \(a^*=1\). Si analizamos el comportamiento de la superposición en un entorno de este punto fijo, tomando una pequeña desviación \(\delta a_t\):

\[1-\delta a_{t+1} = 1- \frac{1-[1-\delta a_t]^K}{K_c}\]

obtenemos que \(\delta a_{t+1}\equiv \frac{K\delta a_t}{K_c}\), por lo que el punto fijo \(a^*=1\) se vuelve inestable cuando \(K/K_c>1\), es decir, cuando \(K>K_c\).

Para valores de \(K >K_c\) obtenemos además un segundo punto fijo, \(a*<1\), que es estable. Es lo que se denomina una bifurcación.

Obsérvese que cuando \(p=1/2\) obtenemos \(K_c=2\), que es el mismo resultado que se obtenía con la teoría del campo medio vista anteriormente, y que para este punto fijo:

\[\lim_{K\to \infty}a^*=\lim_{K\to\infty}(1-\frac{1-[a^*]^K}{K_c})=1-\frac{1}{K_c}=1-2p(1-p)\]

ya que a partir de \(K/K_c\) tenemos que \(a^*<1\). Nótese que si \(p=1/2\) entonces \(a^*\to 1/2\), por lo que si \(K\to \infty\), cualesquiera dos estados iniciales similares acabarán completamente descorrelacionados.

Para el caso de las redes de Kauffman podemos prever cuál es la robustez del sistema, dependiendo del valor de \(K):

  1. En la fase caótica (\(K>K_c\)), \(a^*\) es asintóticamente menor que \(1\), por lo que dos trayectorias, aunque comiencen muy cerca una de la otra, terminan distanciándose. Sin embargo, \(a^*>0\), por lo que no llegan a estar completamente descorrelacionadas. Es como si entraran en diferentes atractores, pero no excesivamente separados, manteniendo una distancia constante.
  2. En la fase estable (\(K<K_c\)), \(a^*\) es asintóticamente \(1\), por lo que todas las trayectorias se aproximan esencialmente a la misma configuración, independientemente del punto de inicio.

Sin embargo, para los retículos no se produce esta pérdida total de la información inicial, ya que en estos casos, para cualquier \(K>0\) tenemos que \(a^*<1\).

« Cómo medir la Complej… « || Inicio || » Estructurando y consu… »