Дмитрий Крюков в Nature: как растут сети

Дмитрий Крюков: «Если мы знаем закон, описывающий динамику сложной   системы (сети), то мы не только можем предсказать её поведение, но также   найти способ лучше её контролировать»

Учёный из Университета Калифорнии, в прошлом выпускник Санкт-Петербургского государственного университета, Дмитрий Крюков выдвинул теорию, согласно которой можно рассчитать и предсказать особенности построения различных сетей: технологических (интернет), социальных (Facebook, Instagram) и биологических (метаболическая сеть кишечной палочки). Вместе с коллегами из Технологического университета Кипра, Университета Калифорнии в Сан-Диего и Университета Барселоны он построил расчётную модель, подтверждающую теорию, и сам удивился результату: настолько точно его геометрический метод анализа просчитывал формирование связей в разных системах. С его помощью можно предсказать, как будут эволюционировать взаимодействия белковых молекул, террористическая сеть, сложные искусственные системы рекомендаций, такие как сеть Netflix или Амазон, и так далее. Работу отклонил Science, но опубликовал Nature.

Дмитрий Крюков: «Если мы знаем закон, описывающий динамику сложной системы (сети), то мы не только можем предсказать её поведение, но также найти способ лучше её контролировать»

Идея создать такую расчётную модель пришла в голову Дмитрию Крюкову летом 2009 года. Он зафиксировал её в рабочих планах и благополучно «похоронил» почти на год, пока один из его коллег по другим научным проектам – Фрагкискос Пападопулус из Технологического университета Кипра – не уговорил автора найти время для того, чтобы всерьёз взяться за это дело. Реализация идеи заняла ещё около года.

В результате была создана модель, основанная на рассмотрении компромисса между популярностью и схожестью. Суть, на первый взгляд, нехитрая: узел, который присоединяется к сети, старается первоначально связаться с достаточно популярными и в то же время схожими с ним самим узлами, то есть простейшими структурными единицами (например, в сети Facebook узел – это страничка пользователя, в сети популяции кишечной палочки – сам единичный бактериальный организм). Популярны те узлы сети, которые имеют большое количество соединений с другими, как, допустим, страница какого-нибудь известного блогера в ЖЖ. На схеме, разработанной коллективом, эти две размерности (популярность и схожесть) могут быть скомбинированы в одном пространстве, образуя карту, которая позволит предсказать потенциальные соединения в растущей сети с большой точностью.

«В общем, если мы знаем закон, описывающий динамику сложной системы (сети), то мы не только можем предсказать её поведение, но также найти способ лучше её контролировать», – пояснил Дмитрий Крюков в переписке с корреспондентом STRF.ru.

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

В этом исследовании авторы впервые доказали, что популярность – лишь один аспект при установлении «предпочтительного соединения». Существует ещё и второй – схожесть. Узлы, которые похожи, имеют больший шанс к соединению, даже если они не популярны. В социальных науках такой эффект называется гомофилией, то есть тенденцией к общению с индивидуумами со сходными интересами, одинаковым возрастом и прочими равными или близкими критериями. Например, индивид, создавший собственную домашнюю страницу, будет связываться не только с такими популярными сайтами, как Facebook или Google, но и с непопулярными, но близкими его интересам: допустим, сайты, посвящённые творчеству группы The Orb или свободному одиночному альпинизму.

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

Вдохновлённые результатами работы, учёные направили статью об этом исследовании в Science, один из самых авторитетных журналов в научном мире. Однако в этом издании, как рассказывает Дмитрий Крюков, работа рецензировалась почти год, «беспредельно улучшаясь и углубляясь, и в конце концов всё-таки пала жертвой высокоэнтропийного рецензента, так и не сумевшего до конца разобраться в деталях». После уже доведённая до полной зрелости версия статьи была послана в Nature, где не встретила серьёзного сопротивления рецензентов. Сами авторы объясняют это тем, что за год действительно настолько улучшили работу, что она уже не могла вызвать никаких проволочек при публикации.

Следующим шагом команды будет доказательство связи модели растущих сетей с динамикой каузальной структуры пространства – времени в нашей ускоряющейся Вселенной. Статья об этом скоро появится в Nature Scientific Reports. В ней исследователи обнаруживают, что при определённом рассмотрении структура Вселенной, интернета, социальных сетей и мозга человека удивительно похожи, что является следствием асимптотической эквивалентности динамики эволюции этих на первый взгляд совершенно разных сложных систем. Объяснение такого невероятного совпадения между теорией гравитации Эйнштейна и геометрической теорией сетей Дмитрия Крюкова – одна из задач будущих исследований коллектива.

Σ Шабельский Алексей

Источник информации:
F. Papadopoulos, M. Kitsak, M.A. Serrano, M. Boguna, D. Krioukov, Popularity versus similarity in growing networks. Nature, № 489.