Керованість мережі стосується структурної керованості мережі. Керованість описує нашу здатність керувати динамічною системою з будь-якого початкового стану до будь-якого бажаного кінцевого стану за скінченний час, з відповідним вибором вхідних даних. Це визначення добре узгоджується з нашим інтуїтивним поняттям керування. Керованість загальних спрямованих та зважених складних мереж нещодавно стала предметом інтенсивного вивчення низкою груп у широкому спектрі мереж по всьому світу.

Нещодавні дослідження Шарми та ін. щодо багатотипних біологічних мереж (мережі взаємодії ген-ген, мікроРНК-ген та білок-білок) виявили цілі керування в фенотипово охарактеризованій остеосаркомі, що показує важливу роль генів та білків, відповідальних за підтримку мікрооточення пухлини.

Передісторія Розглянемо канонічну лінійну незмінну в часі динаміку на складній мережі де вектор фіксує стан системи вузли в момент часу .

Матриця описує структуру з’єднань системи та силу взаємодії між її компонентами.

Матриця визначає вузли, на які подаються керуючі сигнали від зовнішнього контролера. Керування системою здійснюється за допомогою залежного від часу вхідного вектора , який накладається на систему.

Для визначення мінімальної кількості вузлів-драйверів, позначеної як ​, керування якими є достатнім для повного контролю динаміки системи, Лю та ін. поєднали інструменти теорії структурного керування, теорії графів і статистичної фізики. Вони показали, що мінімальна кількість керуючих входів, або вузлів-драйверів, необхідна для забезпечення повного контролю над мережею, визначається максимальним паросполученням у графі. На основі цього результату було розроблено аналітичний підхід, заснований на розподілі вхідних і вихідних ступенів, який дозволяє прогнозувати величину для безмасштабних мереж і випадкових графів Ердеша—Реньї.

Водночас у подальших дослідженнях було показано, що оцінювання керованості мережі лише на основі її структури зв’язків, описаної матрицею , може як недооцінювати, так і переоцінювати кількість необхідних вузлів-драйверів, а також неправильно визначати їхній оптимальний набір. Це підкреслює важливість урахування надмірності мережі (зокрема каналізування) та нелінійної динаміки під час аналізу її керованості.

Також варто зазначити, що формулювання Лю та ін. передбачало б ті самі значення для ланцюгового графа та для слабкого щільнозв'язаного графа. Очевидно, що обидва ці графи мають дуже різні розподіли ступенів вхідних та вихідних. Нещодавня неопублікована робота ставить під сумнів, чи ступінь, який є чисто локальною мірою в мережах, повністю описуватиме керованість, і чи навіть трохи віддалені вузли не відіграватимуть жодної ролі у визначенні керованості мережі.

Дійсно, для багатьох реальних мереж, а саме: харчових мереж, нейронних та метаболічних мереж, невідповідність значень і розраховані Лю та ін. є примітними. Якщо керованість визначається головним чином ступенем, чому і настільки різні для багатьох реальних мереж? Вони стверджували, що це може бути пов'язано з впливом кореляцій ступенів. Однак було показано, що керованість мережі можна змінити лише за допомогою центральності між ними та центральності близькості, без використання ступеня (теорії графів) або кореляцій ступенів взагалі.

Структурна керованість Концепцію структурних властивостей вперше запровадив Лін (1974), потім розширили Шилдс та Пірсон (1976)R. W. Shields and J. B. Pearson, IEEE Trans. Auto. Contr. 21 (1976). та вивели Гловер та Сільверман (1976)K. Glover and L. M. Silverman, IEEE Trans. Auto. Contr. 21 (1976).. Основне питання полягає в тому, чи є втрата керованості або спостережуваності типовою властивістю системи за зміни її параметрів. У теорії структурного керування параметри системи розглядаються як незалежні вільні змінні або як фіксовані нульові значення. Такий підхід є узгодженим із моделями фізичних систем, оскільки числові значення параметрів зазвичай не відомі точно, тоді як нульові значення однозначно відображають відсутність взаємодії або зв’язку між елементами системи.

Максимальне збігання У теорії графів, паросполучення – це набір ребер без спільних вершин. Лю та ін. розширили це визначення на орієнтований граф, де паросполучення – це набір орієнтованих ребер, які не мають спільних початкових або кінцевих вершин. Легко перевірити, що паросполучення орієнтованого графа складається з набору простих шляхів та циклів, що не перетинаються за вершинами. Максимальне паросполучення орієнтованої мережі можна ефективно обчислити, працюючи в двочастинковому представленні, використовуючи класичний алгоритм Хопкрофта-Карпа, який у найгіршому випадку виконується за час O(E). Для неорієнтованого графа аналітичні розв'язки розміру та кількості максимальних паросполучень були досліджені за допомогою методу порожнини, розробленого в статистичній фізиціL. Zdeborová and M. Mezard, J. Stat. Mech. 05 (2006)..

Лю та ін. розширили розрахунки для орієнтованого графа.

Розраховуючи максимальні збіги широкого діапазону реальних мереж, Лю та ін. стверджували, що кількість вузлів драйвера визначається головним чином розподілом ступенів мережі. Вони також розрахували середню кількість вузлів драйвера для мережевого ансамблю з довільним розподілом ступенів, використовуючи метод порожнини . Цікаво, що для ланцюгового графа та слабко щільнозв'язаного графа, які мають дуже різні розподіли ступенів входу та виходу, формулювання Лю та ін. передбачало б однакові значення

Також, для багатьох реальних мереж, а саме: харчових мереж, нейронних та метаболічних мереж, невідповідність значень і розраховані Лю та ін. є примітними.

Якщо керованість визначається виключно ступенем, чому і настільки різні для багатьох реальних мереж?

Залишається відкритим для вивчення питання, чи впливає на «стійкість керування» в мережах більше використання центральності проміжності та центральності близькості ніж метрик на основі ступеня .

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

Керування складеними квантовими системами та алгебраїчна теорія графів Теорію керування мережами також було розроблено в контексті універсального керування для складних квантових систем, де підсистеми та їх взаємодії пов'язані з вузлами та зв'язками відповідно. Ця структура дозволяє сформулювати критерій Калмана за допомогою інструментів алгебраїчної теорії графів через мінімальний ранг графа та пов'язані з ним поняттяS. O'Rourke, B. Touri, https://arxiv.org/abs/1511.05080 ..

Посилання

Зовнішні посилання

Відео, що демонструє керованість мережі