Переменные сети превзошли статичные в управляемости

Переменные сети гораздо быстрее достигают управляемости, а также требуют меньше энергии для ее поддержания, чем статичные сети. Этот факт показала группа ученых под руководством А.-Л. Барабаси (A.-L. Barabási), статья исследователей опубликована в Science.

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

Чтобы понять, почему так происходит, рассмотрим следующий простой пример. Возьмем социальную сеть, состоящую из трех подружек: Алисы, Василисы и Светы, и проследим за ее изменениями в течение недели. В понедельник все три подружки поссорились и разорвали друг с другом связи. Во вторник Алиса помирилась с Василисой, но все еще обижалась на Свету. В среду разорвала с Василисой, зато помирилась со Светой. В четверг Алиса поссорилась с обеими подружками так сильно, что они объединились против нее и весь вечер обсуждали модные тренды сезона. В пятницу повторились события вторника. Получается, что между девушками постоянно возникают и исчезают связи — их социальная сеть является переменной. Если бы подружки были более постоянны, их социальная сеть была бы статичной (например, она статична в течение одного дня). Состояния сети в различные периоды времени (их «мгновенные снимки») можно увидеть на поясняющих картинках A и B, на ней девушкам отвечает красный (Алиса), зеленый (Василиса) и синий (Света) цвета. Шагу по времени, равному одному дню, отвечает Δt = 40.

Теперь предположим, что в пятницу в магазине сумочек начнется распродажа. В понедельник Алиса услышала о ней и решила пойти за покупками с Василисой, а Свету она в этот день видеть не хочет (вот прям точно-точно). Тогда во вторник Алиса договорится с Василисой, а в среду скажет Свете, что в пятницу на противоположном конце города бесплатно раздают персидских котят. Получается, что в течение двух дней мы перевели социальную сеть в заданное состояние, то есть эта сеть является управляемой (картинка F). Заметим, что в течение одного дня сеть управляемой не является.

Но если мы рассмотрим статичную сеть, которая получается объединением сетей вторника и среды (картинка D), она управляемой не будет. В самом деле, в такой сети Алиса должна разговаривать с обеими подружками одновременно, и либо они пойдут на распродажу все вместе, либо Алиса купит сумочку одна. Однако в более сложной статичной сети, в которой существуют связи между каждой парой девушек (картинка E), добиться полной управляемости можно. Например, если сообщить Василисе и Свете о распродаже и заставить девушек поругаться.

Эти события можно описать более строго и обобщить на случай больших сетей. Для этого зададим состояние системы вектором x, состоящим из n компонент, в этом векторе i-ая компонента описывает состояние i-го узла. С одной стороны, скорость изменения будет зависеть от текущего состояния системы — такую зависимость мы зададим переменной матрицей n×n A(t). С другой стороны, мы можем управлять системой через p узлов — этот факт мы учтем с помощью матрицы p×n B(t). Будем считать, что состояние матриц остается постоянным в течение промежутка Δt, а затем дискретно меняется. В результате из этих переменных можно сконструировать специальным способом (подробности в научной статье) пространство управляемости Ω. Если размерность этого пространства совпадает с размерностью пространства состояний ℝⁿ, система будет управляемой, а если меньше, то не будет. В рассмотренной ситуации с подружками (картинка D) размерность Ω была равна двум, поэтому система была неуправляемой.

Так вот, в этой работе математики показали, что переменные сети достигают управляемости гораздо быстрее, чем статичные сети, которые получаются объединением «мгновенных снимков» сетей за тот же промежуток времени (как картинки D и E в примере с подружками). Для этого они рассмотрели четыре сети, взятые из реальной жизни: социальную сеть, построенную участниками во время трехдневной конференции ACM в 2009 году, экологическую сеть муравейника, биологическую сеть, описывающую взаимодействие белков, и наконец, мобильную сеть. Во всех эти случаях переменные сети достигали управляемости гораздо быстрее, чем статичные. Например, переменная социальная сеть конференции ACM достигла управляемости всего через двадцать часов, тогда как статичная — только к концу второго дня. В примере с тремя подружками управляемость наступила на второй (картинка F) и третий (E) день соответственно.

Кроме того, ученые оценили, сколько энергии требуется для поддержания управляемости статичной и переменной сети, состояние которой описывается двумя «мгновенными снимками». Оказалось, что при уменьшении временного промежутка между снимками затраты энергии растут степенным образом, причем для статичной сети гораздо быстрее. Например, в данной модели при Δt = 10⁻⁶ энергия, необходимая для подержания управляемости статичной сети, была на 130 порядков больше, чем для переменной.

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

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

Дмитрий Трунин