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

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

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

Фон [ править ]

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

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

Принципиальная схема показывает управление направленной сетью. Для данной направленной сети (рис. А) вычисляется максимальное соответствие: наибольший набор ребер без общих головок или хвостов. Максимальное соответствие будет состоять из набора непересекающихся по вершинам направленных путей и направленных циклов (см. Красные края на рис. B). Если узел является головкой совпадающего ребра, то этот узел соответствует (зеленые узлы на рис. B). В противном случае он не совпадает (белые узлы на рис. B). Эти несогласованные узлы - это узлы, которыми нужно управлять, то есть узлы драйверов. Вводя сигналы в эти узлы драйвера, можно получить набор направленного пути, начальные точки которого являются входами (см. Рис. C). Эти пути называются «стеблями». Полученный орграф называется U-корневой факториальной связностью. «Прививая» направленные циклы к этим «стеблям», можно получить:бутоны ». Получившийся орграф называется кактусами (см. рис. d). Согласно теореме структурной управляемости,^[5], поскольку существует структура кактусов, охватывающая контролируемую сеть (см. Рис. E), система является управляемой. Структура кактусов (рис. D), лежащая в основе управляемой сети (рис. Е), является «скелетом» для поддержания управляемости.

Структурная управляемость [ править ]

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

Максимальное соответствие [ править ]

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

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

В то время как разреженные графики труднее контролировать, ^{[2] [4]} очевидно , было бы интересно узнать , является ли промежуточность сосредоточенность и близости сосредоточенность ^[4] или степень гетерогенности ^[2] играют более важную роль в решении контролируемости разреженных графов с почти аналогичное распределение степеней.

Управление составными квантовыми системами и алгебраическая теория графов [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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