Управляемость сети

Управление простой сетью.

сети касается структурной управляемости сети Управляемость . Управляемость описывает нашу способность направлять динамическую систему из любого начального состояния в любое желаемое конечное состояние за конечное время с подходящим выбором входных данных. Это определение хорошо согласуется с нашим интуитивным представлением о контроле. Управляемость общенаправленных и взвешенных сложных сетей в последнее время стала предметом интенсивного изучения рядом групп, работающих в самых разных сетях по всему миру. Недавние исследования Sharma et al. на мультитипических биологических сетях (сети ген-ген, микроРНК-ген и белок-белковое взаимодействие) идентифицировали контрольные мишени при фенотипически охарактеризованной остеосаркоме, показывая важную роль генов и белков, ответственных за поддержание микроокружения опухоли.

Предыстория

Рассмотрим каноническую линейную нестационарную динамику в сложной сети ${\dot {\mathbf {X} }}(t)=\mathbf {A} \cdot \mathbf {X} (t)+\mathbf {B} \cdot \mathbf {u} (t)$где вектор $\mathbf {X} (t)=(x_{1}(t),\cdots ,x_{N}(t))^{\mathrm {T} }$ фиксирует состояние системы $N$ узлы во времени $t$. $N\times N$матрица $\mathbf {A}$ описывает схему подключения системы и силу взаимодействия между компонентами. $N\times M$ матрица $\mathbf {B}$ идентифицирует узлы, управляемые внешним контроллером. Система управляется через зависящий от времени входной вектор. $\mathbf {u} (t)=(u_{1}(t),\cdots ,u_{M}(t))^{\mathrm {T} }$ которые контроллер налагает на систему. Чтобы определить минимальное количество узлов драйвера, обозначаемое $N_{\mathrm {D} }$, чей контроль достаточен для полного контроля динамики системы, Лю и др. попытался объединить инструменты теории структурного управления, теории графов и статистической физики. Они показали что минимальное количество входов или узлов драйверов, необходимое для поддержания полного контроля над сетью, определяется соответствием максимальной мощности в сети. На основе этого результата была разработана аналитическая основа, основанная на распределении степеней «вход-выход» для прогнозирования. $n_{\mathrm {D} }=N_{\mathrm {D} }/N$ для безмасштабных и случайных графов Эрдеша–Реньи . Однако совсем недавно было продемонстрировано, что управляемость сети (и другие методы, основанные только на структуре, которые используют исключительно связность графа, $\mathbf {A}$, чтобы упростить основную динамику), как недостигать, так и превышать количество, а также какие наборы узлов драйвера лучше всего контролируют динамику сети, подчеркивая важность избыточности (например, канализации) и нелинейной динамики при определении управления.

Также примечательно, что Liu's et al. формулировка предсказал бы те же значения ${n_{\mathrm {D} }}$ для цепного графа и для слабого плотносвязного графа. Очевидно, что оба этих графика имеют очень разные распределения степеней. Недавняя неопубликованная работа возникает вопрос, будет ли степень , которая является чисто локальной мерой в сетях, полностью описывать управляемость и будут ли даже немного удаленные узлы не играть никакой роли в определении управляемости сети. Действительно, для многих реальных сетей, а именно пищевых сетей, нейронных и метаболических сетей, несоответствие значений ${n_{\mathrm {D} }}^{real}$ и ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ рассчитано Лю и др. примечательно. Если управляемость определяется главным образом степенью, то почему ${n_{\mathrm {D} }}^{real}$ и ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ настолько разные для многих реальных сетей? Они спорили (arXiv:1203.5161v1), что это может быть связано с эффектом корреляции степеней. Однако было показано что управляемость сети можно изменить, только используя центральность по посредничеству и центральность по близости , без использования степени (теории графов) вообще или корреляций степеней.

Принципиальная схема показывает управление направленной сетью. Для заданной ориентированной сети (рис. а) вычисляется ее максимальное паросочетание: наибольший набор ребер без общих голов и хвостов. Максимальное паросочетание будет состоять из набора вершинно-непересекающихся направленных путей и направленных циклов (см. красные ребра на рис.б). Если узел является головой совпадающего ребра, то этот узел совмещен (зеленые узлы на рис.б). В противном случае он не имеет соответствия (белые узлы на рис.б). Эти несовпадающие узлы — это узлы, которыми необходимо управлять, то есть узлы-драйверы. Подавая сигналы в эти узлы драйвера, можно получить набор направленных путей, начальные точки которых являются входами (см. рис. c). Эти пути называются «стебли». Полученный орграф называется U-корневой факториальной связностью. «Прививая» к этим «стеблям» направленные циклы, получают «почки». Полученный орграф называется кактусами (см. рис.г). По теореме структурной управляемости поскольку существует структура кактусов, охватывающая управляемую сеть (см. рис. д), система управляема. Структура кактусов (рис.г), лежащая в основе управляемой сети (рис.д), является «скелетом» поддержания управляемости.

управляемость

Понятие структурных свойств было впервые введено Лином (1974). а затем расширен Шилдсом и Пирсоном (1976). и, альтернативно, получено Гловером и Сильверманом (1976). Главный вопрос заключается в том, является ли отсутствие управляемости или наблюдаемости характерным для переменных параметров системы. В рамках структурного управления параметрами системы являются либо независимые свободные переменные, либо фиксированные нули. Это справедливо для моделей физических систем, поскольку значения параметров никогда не известны точно, за исключением нулевых значений, которые выражают отсутствие взаимодействий или связей.

Максимальное соответствие

В теории графов паросочетание — это набор ребер, не имеющих общих вершин. Лю и др. распространил это определение на ориентированный граф, где паросочетание представляет собой набор направленных ребер, которые не имеют общих начальных или конечных вершин. Легко проверить, что паросочетание ориентированного графа представляет собой набор вершинно-непересекающихся простых путей и циклов. Максимальное сопоставление направленной сети можно эффективно вычислить, работая в двудольном представлении с использованием классического алгоритма Хопкрофта – Карпа выполняется за время O( E √ N , который в худшем случае ). Для неориентированного графа аналитические решения размера и количества максимальных паросочетаний были изучены с использованием метода полости, разработанного в статистической физике. Лю и др. расширил вычисления для ориентированного графа.

Рассчитывая максимальные совпадения широкого спектра реальных сетей, Лю и др. утверждал, что количество узлов-драйверов определяется главным образом распределением степени сети $P(k_{\mathrm {in} },k_{\mathrm {out} })$. Они также рассчитали среднее количество узлов-драйверов для ансамбля сети с произвольным распределением степеней, используя метод полости . Интересно, что для цепного графа и слабого плотносвязного графа, оба из которых имеют очень разные распределения степеней по входу и выходу; формулировка Liu et al. предсказал бы те же значения ${n_{\mathrm {D} }}$. Кроме того, для многих сетей реального мира, а именно пищевых сетей, нейронных и метаболических сетей, несоответствие значений ${n_{\mathrm {D} }}^{real}$ и ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ рассчитано Лю и др. примечательно. Если управляемость определяется исключительно степенью, то почему ${n_{\mathrm {D} }}^{real}$ и ${n_{\mathrm {D} }}^{\mathrm {rand\_degree} }$ настолько разные для многих реальных сетей? Остается открытым вопрос о том, влияет ли «устойчивость управления» в сетях в большей степени при использовании централизации по промежуточности и централизации по близости. над метриками, основанными на степени .

Хотя более разреженные графики труднее контролировать, очевидно, было бы интересно выяснить, являются ли центральность по посредничеству и центральность по близости или степень неоднородности играет более важную роль в определении управляемости разреженных графов с почти подобными распределениями степеней.

составными квантовыми системами и алгебраическая

Теория управления сетями также была разработана в контексте универсального управления составными квантовыми системами, где подсистемы и их взаимодействия связаны с узлами и связями соответственно. Эта структура позволяет сформулировать критерий Калмана с помощью инструментов алгебраической теории графов через минимальный ранг графа и связанные с ним понятия.

См. также

• Управляемость Грамиан

Внешние ссылки

• Сайт проекта управляемости сети
• Видео, демонстрирующее управляемость сети