Новое доказательство показывает, что графики «расширителя» синхронизируются | Журнал Кванта

Шесть лет назад Афонсу Бандейра и Шуян Линг пытались придумать лучший способ различения кластеров в огромных наборах данных, когда они наткнулись на сюрреалистический мир. Линг понял, что уравнения, которые они придумали, неожиданно идеально подошли к математической модели спонтанной синхронизации. Спонтанная синхронизация — это явление, при котором осцилляторы, которые могут принимать форму маятников, пружин, клеток человеческого сердца или светлячков, в конечном итоге движутся синхронно без какого-либо центрального координационного механизма.

Бандейра, математик из Швейцарский федеральный технологический институт Цюрихаи Линг, специалист по данным в Нью-Йоркском университете, углубился в исследование синхронизации, получив ряд примечательных результатов о силе и структуре, которые должны иметь связи между осцилляторами, чтобы заставить осцилляторы синхронизироваться. Кульминацией этой работы стала октябрьская статья, в которой Бандейра доказал (вместе с пятью соавторами), что синхронизация неизбежна в специальных типах сетей, называемых расширительными графами, которые разрежены, но также хорошо связаны.

Экспандерные графы находят множество применений не только в математике, но и в информатике и физике. Их можно использовать для создания кодов, исправляющих ошибки, и для выяснения того, когда симуляции, основанные на случайных числах, сходятся к реальности, которую они пытаются смоделировать. Нейроны можно смоделировать в виде графа, который, по мнению некоторых исследователей, образует расширитель из-за ограниченного пространства для соединений внутри мозга. Графики также полезны для геометров, которые пытаются понять как проходить сложные поверхности, среди других проблем.

Новый результат «действительно дает глубокое понимание того, какие типы графовых структур гарантируют синхронизацию», — сказал он. Ли ДеВиль, математик из Университета Иллинойса, не участвовавший в работе.

Горько-сладкая синхронность         

«Синхронизация — это действительно одно из фундаментальных явлений природы, — сказал Виктор Соуза, математик из Кембриджского университета, который работал с Бандейрой над статьей. Рассмотрим клетки кардиостимулятора в вашем сердце, которые синхронизируют свои пульсации с помощью электрических сигналов. В лабораторных экспериментах «вы можете получить сотни или тысячи этих эмбриональных клеток кардиостимулятора, пульсирующих в унисон», — сказал он. Стивен Строгац, математик из Корнельского университета и еще один соавтор. «Это немного жутко, потому что это не целое сердце; это только на уровне клеток».

В 1975 году японский физик Йошики Курамото представил математическую модель, описывающую такого рода систему. Его модель работает в сети, называемой графом, где узлы соединены линиями, называемыми ребрами. Узлы называются соседями, если они связаны ребром. Каждому ребру можно присвоить число, называемое весом, которое кодирует силу соединения между узлами, которые оно соединяет.

В модели синхронизации Курамото каждый узел содержит осциллятор, который представлен точкой, вращающейся по окружности. Эта точка показывает, скажем, где находится сердечная клетка в своем цикле пульсации. Каждый осциллятор вращается со своей предпочтительной скоростью. Но осцилляторы также хотят совпадать с соседями, которые могут вращаться с другой частотой или в другой момент своего цикла. (Вес ребра, соединяющего два осциллятора, измеряет силу связи между ними.) Отклонение от этих предпочтений увеличивает расход энергии осциллятором. Система пытается сбалансировать все конкурирующие желания, сводя к минимуму свою общую энергию. Вклад Курамото заключался в том, чтобы упростить эти математические ограничения настолько, чтобы математики могли продвинуться в изучении системы. В большинстве случаев такие большие системы связанных дифференциальных уравнений практически невозможно решить.

По его словам, несмотря на свою простоту, модель Курамото оказалась полезной для моделирования синхронизации в сетях от мозга до электросетей. Джинестра Бьянкони, прикладной математик Лондонского университета королевы Марии. «В отношении мозга это не особенно точно, но считается очень эффективным», — сказала она.

«Здесь очень тонкий танец между математикой и физикой, потому что модель, которая фиксирует явление, но которую очень трудно анализировать, не очень полезна», — сказал Соуза.

В своей статье 1975 года Курамото предположил, что каждый узел связан с каждым другим узлом в так называемом полном графе. Отсюда он показал, что для бесконечного числа осцилляторов, если связь между ними достаточно сильна, он может выяснить их долгосрочное поведение. Сделав дополнительное предположение, что все осцилляторы имеют одинаковую частоту (что сделало бы их нечто, называемое однородной моделью), он нашел решение, в котором все осцилляторы будут вращаться одновременно, каждый из которых будет вращаться вокруг одной и той же точки на своей окружности в одно и то же время. Хотя большинство реальных графиков далеки от завершения, успех Курамото заставил математиков задаться вопросом, что произойдет, если они ослабят его требования.

Мелодия и тишина

В начале 1990-х вместе со своим учеником Шинья Ватанабэ, Строгац показал, что решение Курамото было не только возможным, но и почти неизбежным даже для конечного числа осцилляторов. В 2011, Ричард Тейлор из Австралийской организации оборонной науки и техники отказались от требования Курамото о том, чтобы график был полным. Он доказанный что однородные графы, в которых каждый узел соединен как минимум с 94% других, обязательно будут глобально синхронизированы. Преимущество результата Тейлора заключалось в том, что он применялся к графам с произвольной структурой связности, если каждый узел имел большое количество соседей.

В 2018 году Бандейра, Линг и Руиту Сюй, аспирант Йельского университета, снижено требование Тейлора чтобы каждый узел был подключен к 94%, остальные — к 79.3%. В 2020 году конкурирующая группа набрала 78.89%; в 2021 году, Строгац, Алекс Таунсенд и Мартин Кассабов установленный текущая запись когда показали что 75% достаточно.

Тем временем исследователи подошли к проблеме и с противоположной стороны, пытаясь найти графы, которые были бы сильно связаны, но не синхронизировались бы глобально. В серии статей от 2006 в 2022, они обнаружили график за графиком, которые могли избежать глобальной синхронизации, даже несмотря на то, что каждый узел был связан более чем с 68% других. Многие из этих графиков напоминают круг людей, держащихся за руки, где каждый человек обращается к 10 или даже 100 ближайшим соседям. Эти графики, называемые кольцевыми графиками, могут переходить в состояние, в котором каждый осциллятор немного смещен относительно следующего.

Очевидно, что структура графа сильно влияет на синхронизацию. Итак, Линг, Сюй и Бандейра заинтересовались свойствами синхронизации случайно сгенерированных графов. Чтобы сделать свою работу более точной, они использовали два распространенных метода случайного построения графика.

Первый назван в честь Пола Эрдёша и Альфреда Реньи, двух выдающихся теоретиков графов, проделавших основополагающую работу над моделью. Чтобы построить граф с использованием модели Эрдёша-Реньи, вы начинаете с набора несвязанных узлов. Затем для каждой пары узлов вы случайным образом связываете их вместе с некоторой вероятностью. p. Если p составляет 1%, вы связываете ребра в 1% случаев; если это 50%, каждый узел будет подключаться в среднем к половине других.

If p незначительно превышает пороговое значение, которое зависит от количества узлов в графе, граф, с большой вероятностью, сформирует одну взаимосвязанную сеть (в отличие от кластеров, которые не связаны между собой). По мере роста размера графа этот порог становится крошечным, так что для достаточно больших графов, даже если p мало, поэтому общее количество ребер также мало, графы Эрдёша-Реньи будут связными.

Второй тип графа, который они рассмотрели, называется d-регулярный граф. В таких графах каждый узел имеет одинаковое количество ребер, d. (Таким образом, в 3-регулярном графе каждый узел соединен с 3 другими узлами, в 7-регулярном графе каждый узел соединен с 7 другими и так далее.)

Графы, которые хорошо связаны, несмотря на то, что они разрежены (имеют лишь небольшое количество ребер), известны как графы-расширители. Они важны во многих областях математики, физики и информатики, но если вы хотите построить граф-расширитель с определенным набором свойств, вы обнаружите, что это «на удивление нетривиальная задача». по данным выдающийся математик Терри Тао. Графы Эрдеша-Реньи, хотя и не всегда являются расширителями, имеют много общих важных черт. И яОднако оказывается, что если построить d-регулярный граф и соедините ребра случайным образом, у вас будет расширительный граф.

Свести концы с концами

В 2018 году Линг, Сюй и Бандейра предположили, что порог подключения может также измерять появление глобальной синхронизации: если вы создадите граф Эрдёша-Реньи с p чуть больше порога, график должен глобально синхронизироваться. Они добились частичного прогресса в этой гипотезе, а Строгац, Кассабов и Таунсенд позже улучшили свой результат. Но значительный разрыв между их количеством и порогом подключения оставался.

В марте 2022 года Таунсенд посетил Бандейру в Цюрихе. Они поняли, что у них есть шанс достичь порога подключения, и внесли Педро Абдалла, аспирант Бандейры, который, в свою очередь, заручился поддержкой своего друга Виктора Соуза. Абдалла и Соуза начали прорабатывать детали, но быстро столкнулись с препятствиями.

Казалось, случайность сопряжена с неизбежными проблемами. Пока не p был значительно больше, чем порог подключения, вероятно, были резкие колебания количества ребер, которые имел каждый узел. Один может быть привязан к 100 ребрам; другой может быть прикреплен ни к одному. «Как и любая хорошая проблема, она дает отпор», — сказал Соуза. Абдалла и Соуза поняли, что подход к проблеме с точки зрения случайных графов не сработает. Вместо этого они будут использовать тот факт, что большинство графов Эрдёша-Реньи являются расширителями. «После этого невинного изменения многие части головоломки стали вставать на свои места», — сказал Соуза. «В конце концов, мы получили результат намного сильнее, чем мы рассчитывали». Графики имеют число, называемое расширением, которое измеряет, насколько сложно разрезать их на две части, нормализованные к размеру графика. Чем больше это число, тем сложнее разделить его на два, удалив узлы.

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

Вниз по единственной дороге

Одна из самых больших остающихся загадок в математическом изучении синхронизации требует лишь небольшой корректировки модели в новой статье: что произойдет, если некоторые пары осцилляторов притягивают друг друга к синхронности, а другие выталкивают друг друга из нее? В этой ситуации «почти все наши инструменты немедленно исчезли», — сказал Соуза. Если исследователи смогут добиться прогресса в решении этой версии проблемы, методы, скорее всего, помогут Бандейре решить проблемы кластеризации данных, которые он намеревался решить, прежде чем приступить к синхронизации.

Кроме того, существуют классы графов помимо расширителей, шаблоны более сложные, чем глобальная синхронизация, и модели синхронизации, которые не предполагают, что все узлы и ребра одинаковы. В 2018 году Сабер Джафарпур и Франческо Булло из Калифорнийского университета в Санта-Барбаре предложил тест для глобальной синхронизации, которая работает, когда ротаторы не имеют одинаковых весов и предпочтительных частот. команда Бьянкони и другие исследователи работали с сетями, соединения которых включают три, четыре или более узлов, а не только пары.

Бандейра и Абдалла уже пытаются выйти за пределы Эрдёш-Реньи и d-регулярные модели в другие, более реалистичные модели случайного графа. В августе прошлого года они поделился бумагой, в соавторстве с Кларой Инверницци, о синхронизации в случайных геометрических графах. В случайных геометрических графах, которые были созданы в 1961 году, узлы случайным образом разбросаны в пространстве, возможно, на поверхности, такой как сфера или плоскость. Ребра размещаются между парами узлов, если они находятся на определенном расстоянии друг от друга. Их изобретатель Эдгар Гилберт надеялся смоделировать коммуникационные сети, в которых сообщения могут передаваться только на короткие расстояния, или распространение инфекционных патогенов, для передачи которых требуется тесный контакт. По словам Бандейры, случайные геометрические модели также лучше фиксируют связи между светлячками в рое, которые синхронизируются, наблюдая за своими соседями.

Конечно, связать математические результаты с реальным миром сложно. «Я думаю, что было бы немного выдумкой утверждать, что это обусловлено приложениями», — сказал Строгац, который также отметил, что однородная модель Курамото никогда не может отразить присущие биологическим системам вариации. Соуза добавил: «Есть много фундаментальных вопросов, которые мы до сих пор не знаем, как решить. Это больше похоже на исследование джунглей».

Примечание редактора: Стивен Строгац ведет подкаст «Joy of Why» для Quanta и бывший член научно-консультативного совета журнала. У него взяли интервью для этой статьи, но он не участвовал в ее подготовке.