графы

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

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

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

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

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

Обычная дорожная карта с данными о трафике — это колоссальный массив чисел. Передавать их в исходном виде слишком накладно. Но объём можно радикально сократить, не теряя значимой информации. Исследователи предложили изящный подход: сначала выполняется преобразование графа — улицы становятся вершинами (точками), а перекрёстки — рёбрами (перемычками) между ними.

Ребёнок, осваивая незнакомую квартиру, ползает от предмета к предмету и запоминает, что видно из каждого угла. Так мозг строит мысленную карту — внутреннюю модель пространства. Алгоритм gradCSCG действует по тому же принципу: он получает видеопоток с камеры и самостоятельно рисует схему помещения, опираясь лишь на смену картинок.

Анализ данных в интернете или сенсорных системах долго напоминал попытку дирижировать оркестром, где каждый музыкант заперт в своей будке, а дирижёр не может покинуть пульт.

Семейное древо превращается в клубок, если учесть приёмных детей и повторные браки. Эволюция часто похожа на такой клубок: хотя стандартная модель — традиционное представление о дивергентной эволюции, где виды ветвятся подобно дереву — рисует аккуратное древо видов, на деле гены кочуют не только по наследству, но и напрямую между неродственными организмами — этот…

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

7 278 601 292 779 396 715. Ровно столько разных хордальных графов (графов без индуцированных циклов длины четыре и больше) можно построить на двадцати вершинах, если считать структуры без имён. Это число — не головоломка для суперкомпьютера, а точный результат нового алгоритма, который смотрит на симметрию как на инструмент, а не помеху.

В зале суда — строка, поданная на вход. Двенадцать присяжных (вычислительных путей) изучают её символ за символом. Каждый может вынести «виновен» (принять) или «невиновен». Для обычного недетерминированного автомата (НКА) достаточно одного голоса «за». Но в суде с симметрической разностью (XNFA) вердикт выносится по нечётности: если число голосов «виновен» нечётно — слово принято.

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

Внутри кристалла разворачивается незримый балет: магнитные моменты атомов, словно танцоры, то выстраиваются в унисон, то рассыпаются в противофазе. Хореографию диктует квантовый обмен — музыка, чуткая к геометрии связей. Согласно правилам Гуденафа–Канамори–Андерсона, угол M–X–M между магнитным ионом, лигандом и соседним магнитным ионом определяет, смотрят ли спины в одну сторону или врассыпную.

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

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

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

Кухонная губка, пропитанная сиропом: в одних местах сиропа больше, и палец прилипает сразу, в других — едва касается. Примерно так устроена поверхность катализатора. Молекулы реагируют не везде, а в особо липких точках — активных центрах. Десятилетиями химики искали их по расположению атомов, как кладоискатели с картой. Но карта врёт.

Проектирование машин сродни кулинарии: необходимо точно знать, где «тесто» порвётся. Классические численные методы, например, анализ методом конечных элементов, проверяют каждую точку детали часами — это как обмерять всю кастрюлю, чтобы ручка не отвалилась.

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

Социальная сеть похожа на город: есть районы-гиганты и крошечные переулки. Когда алгоритм ищет в ней сплочённые компании, он часто выделяет пару огромных групп и много мелких осколков. Но заказчику — например, муниципалитету — нужны районы примерно одного размера, чтобы равномерно распределить поликлиники или школы.

Город — это живая система: он потребляет ресурсы, выделяет отходы, а его «кровеносная система» — дорожная сеть — доставляет людей и товары к местам назначения. Но пока инженеры проектируют транспортные артерии как жёсткую геометрию прямых линий, природа миллионы лет оттачивает идеальные распределительные сети.

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

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

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

Изучение рождения галактик — гигантских звёздных систем — требует моделирования миллиардов лет роста тёмной материи и процессов звездообразования. Даже суперкомпьютеры справляются с этой задачей медленно, ведь нужно просчитать гравитационное взаимодействие невидимой материи и превращение газа в звёзды.

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

Представьте карту города: перекрёстки — это узлы, улицы — связи между ними. Чтобы алгоритм мог анализировать такую структуру, каждому узлу необходимо присвоить метку. Классический подход, основанный на стандартной модели, действует прямолинейно — присваивает узлам простые ярлыки, подобно номерам домов.

Родинка на коже похожа на мозаику из цветных кусочков. Каждый кусочек — это маленький участок снимка, где цвет и текстура почти не меняются. Такие кусочки называют суперпикселями. Если соединить их линиями, получится сеть, похожая на карту метро: станции — кусочки, а линии — связи между ними. Вес каждой линии показывает, насколько сильно связаны два кусочка.

Ударьте по камертону — и он зазвучит одной чистой нотой. Но если камертон дрожит, а рядом шумят люди, звук уже не будет идеальным. Так и молекулы: каждая поглощает свет определённого цвета, но из-за собственной дрожи и толкотни соседей этот цвет слегка размывается. Авторы статьи придумали, как показать это студентам без сложных формул.

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

Частицы в ускорителе могут колебаться сразу в двух поперечных направлениях, и эти колебания не всегда независимы. Если толкнуть маятник в одну сторону, а он начнёт качаться ещё и вбок — это и есть связанные колебания. В ускорителях такое случается из-за несовершенства магнитов или специальных вставок, и тогда движение частиц становится сложным.

Болезнь Альцгеймера похожа на запутанный клубок ниток: тысячи генов переплетаются, и трудно понять, какие из них рвутся первыми. Раньше учёные искали важные гены, просто подсчитывая, сколько связей у каждого узла в сети. Но такой подход похож на оценку человека по числу знакомых — не всегда самый общительный оказывается самым влиятельным.

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

Город можно изучать по-разному: один наносит на карту улицы, другой — потоки машин, третий — плотность населения. Карты не совпадают, но описывают одно и то же место. Похожая задача встаёт, когда биологи смотрят на клетку через разные приборы: один показывает её форму, другой — распределение белков внутри. Нужно понять, как эти данные связаны. Новый метод UnSyncOT делает именно это.

Плодовая мушка дрозофила — крошечное существо с мозгом размером с маковое зёрнышко. В нём около ста тысяч нервных клеток, и учёные уже составили полную карту их соединений — как схему городского метро, где станции — нейроны, а линии — связи между ними. Эта схема называется коннектомом.

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

Карта города, где вместо улиц — скорости машин, а вместо домов — содержание металлов в звёздах. По такой карте можно понять, где центр, где окраины, даже не зная точных расстояний. Именно такой подход применили астрономы к нашей Галактике, используя диаграммы «долгота–скорость» (ℓ–v).

Кора головного мозга похожа на смятый лист бумаги: у неё есть толщина, изгибы и глубина складок. С возрастом этот лист меняется неравномерно — где-то истончается, где-то теряет чёткость изгибов. Раньше врачи оценивали возраст мозга целиком, как будто смотрели на лист издалека.

Графы считаются изоморфными — структурно тождественными, — если у них совпадает «рельеф». Представьте две топографические карты с горами и долинами: даже при разной художественной прорисовке высоты и крутизна склонов могут быть геометрически теми же.