Controlabilidad de la red

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

La controlabilidad de la red se refiere a la controlabilidad estructural de una red. La controlabilidad describe nuestra capacidad para guiar un sistema dinámico desde cualquier estado inicial hasta cualquier estado final deseado en un tiempo finito, con una selección adecuada de entradas. Esta definición concuerda bien con nuestra noción intuitiva de control. La capacidad de control de redes complejas dirigidas y ponderadas en general ha sido recientemente objeto de intenso estudio por parte de varios grupos en una amplia variedad de redes en todo el mundo. Estudios recientes de Sharma et al. en redes biológicas multitipo (gen-gen, miARN-gen, redes de interacción proteína-proteína) identificaron objetivos de control en osteosarcoma fenotípicamente caracterizados que muestran un papel importante de genes y proteínas responsables de mantener el microambiente tumoral.

Fondo

Considere la dinámica canónica lineal invariante en el tiempo en una red compleja ${displaystyle {dot {mathbf{X}}}(t)=mathbf{A}cdotmathbf{X}(t)+mathbf{B}cdotmathbf{u}(t)}$ donde el vector ${displaystyle mathbf {X} (t)=(x_{1}(t),cdots,x_{N}(t))^{mathrm {T} }}$ captura el estado de un sistema de $norte$ nodos en el tiempo $t$ . La $Nveces N$ matriz $matemáticas {A}$ describe el diagrama de cableado del sistema y la fuerza de interacción entre los componentes. La ${ estilo de visualización N veces M}$ matriz $matemáticas {B}$ identifica los nodos controlados por un controlador externo. El sistema se controla a través del vector de entrada dependiente del tiempo ${displaystyle mathbf {u} (t)=(u_{1}(t),cdots,u_{M}(t))^{mathrm {T} }}$ que el controlador impone al sistema. Para identificar el número mínimo de nodos controladores, indicados por ${displaystyle N_{mathrm {D} }}$ , cuyo control es suficiente para controlar completamente la dinámica del sistema, Liu et al.intentó combinar las herramientas de la teoría del control estructural, la teoría de grafos y la física estadística. Demostraron que la cantidad mínima de entradas o nodos controladores necesarios para mantener el control total de la red está determinada por la "coincidencia máxima" en la red, es decir, el conjunto máximo de enlaces que no comparten nodos de inicio o fin. A partir de este resultado, se desarrolló un marco analítico, basado en la distribución de grados de entrada y salida, para predecir ${displaystyle n_{mathrm {D} }=N_{mathrm {D} }/N}$ gráficos sin escala y Erdős-Rényi. Sin embargo, más recientemente se ha demostrado que la controlabilidad de la red (y otros métodos de solo estructura que usan exclusivamente la conectividad de un gráfico, $matemáticas {A}$ , para simplificar la dinámica subyacente), tanto por debajo como por encima del número y qué conjuntos de nodos controladores controlan mejor la dinámica de la red, destacando la importancia de la redundancia (por ejemplo, canalización) y la dinámica no lineal para determinar el control.

También es notable que Liu's et al. la formulación predeciría los mismos valores de ${displaystyle {n_{mathrm {D} }}}$ para un gráfico de cadena y para un gráfico débil densamente conectado. Obviamente, ambos gráficos tienen distribuciones de grado de entrada y salida muy diferentes. Un trabajo reciente no publicado cuestiona si el grado, que es una medida puramente local en las redes, describiría completamente la controlabilidad y si incluso los nodos ligeramente distantes no tendrían ningún papel en decidir la controlabilidad de la red. De hecho, para muchas redes de palabras reales, a saber, redes alimentarias, redes neuronales y metabólicas, la falta de coincidencia en los valores de Liu et al ${displaystyle {n_{mathrm {D} }}^{real}}$ . no es capaz. Si la controlabilidad se decide principalmente por grado, ¿por qué son tan diferentes para muchas redes del mundo real? discutieron ${displaystyle {n_{mathrm {D} }}^{mathrm {rand_degree} }}$ ${displaystyle {n_{mathrm {D} }}^{real}}$ ${displaystyle {n_{mathrm {D} }}^{mathrm {rand_degree} }}$ (arXiv:1203.5161v1), que esto podría deberse al efecto de las correlaciones de grado. Sin embargo, se ha demostrado que la controlabilidad de la red puede alterarse solo mediante el uso de centralidad de intermediación y centralidad de proximidad, sin utilizar grado (teoría de grafos) o correlaciones de grado en absoluto.

Controlabilidad estructural

El concepto de propiedades estructurales fue introducido por primera vez por Lin (1974) y luego ampliado por Shields y Pearson (1976) y derivado alternativamente por Glover y Silverman (1976). La pregunta principal es si la falta de controlabilidad o la observabilidad son genéricas con respecto a los parámetros variables del sistema. En el marco del control estructural, los parámetros del sistema son variables libres independientes o ceros fijos. Esto es consistente para los modelos de sistemas físicos ya que los valores de los parámetros nunca se conocen con exactitud, con la excepción de los valores cero que expresan la ausencia de interacciones o conexiones.

Coincidencia máxima

En teoría de grafos, una coincidencia es un conjunto de aristas sin vértices comunes. Liu et al. extendió esta definición al gráfico dirigido, donde una coincidencia es un conjunto de bordes dirigidos que no comparten vértices iniciales o finales. Es fácil comprobar que una coincidencia de un gráfico dirigido se compone de un conjunto de caminos y ciclos simples disjuntos de vértice. La coincidencia máxima de una red dirigida se puede calcular de manera eficiente trabajando en la representación bipartita utilizando el algoritmo clásico de Hopcroft-Karp, que se ejecuta en el tiempo O (E √ N) en el peor de los casos. Para grafos no dirigidos, se han estudiado soluciones analíticas del tamaño y número de coincidencias máximas utilizando el método de cavidades desarrollado en física estadística. Liu et al. amplió los cálculos para gráfico dirigido.

Al calcular las coincidencias máximas de una amplia gama de redes reales, Liu et al. afirmó que el número de nodos de controlador está determinado principalmente por la distribución del grado de redes ${displaystyle P(k_{mathrm {entrada}},k_{mathrm {salida}})}$ . También calcularon la cantidad promedio de nodos de controlador para un conjunto de red con distribución de grado arbitraria utilizando el método de cavidad. Es interesante que para un gráfico de cadena y un gráfico débil densamente conectado, ambos tienen distribuciones de grado de entrada y salida muy diferentes; la formulación de Liu et al. predeciría los mismos valores de ${displaystyle {n_{mathrm {D} }}}$ . Además, para muchas redes de palabras reales, a saber, redes alimentarias, redes neuronales y metabólicas, la falta de coincidencia en los valores de Liu et al ${displaystyle {n_{mathrm {D} }}^{real}}$ . no es capaz. Si la controlabilidad se decide puramente por grado, ¿por qué ${displaystyle {n_{mathrm {D} }}^{mathrm {rand_degree} }}$ ${displaystyle {n_{mathrm {D} }}^{real}}$ y ${displaystyle {n_{mathrm {D} }}^{mathrm {rand_degree} }}$ tan diferente para muchas redes del mundo real? Queda abierto al escrutinio si la robustez del control en las redes se ve más influenciada por el uso de centralidad de intermediación y centralidad de cercanía sobre métricas basadas en grados (teoría de grafos).

Si bien los gráficos más dispersos son más difíciles de controlar, obviamente sería interesante averiguar si la centralidad de intermediación y la centralidad de cercanía o la heterogeneidad de grado juegan un papel más importante para decidir la controlabilidad de los gráficos dispersos con distribuciones de grado casi similares.

Control de sistemas cuánticos compuestos y teoría de grafos algebraicos

También se ha desarrollado una teoría de control de redes en el contexto del control universal para sistemas cuánticos compuestos, donde los subsistemas y sus interacciones están asociados a nodos y enlaces, respectivamente. Este marco permite formular el criterio de Kalman con herramientas de la teoría algebraica de grafos a través del rango mínimo de un grafo y nociones relacionadas.

Contenido relacionado

Más resultados...