Математики предложили новую меру близости в сетях в присутствии коллективных связей

❋ 5.2

Группа ученых из МФТИ и их иностранных коллег нашла способ измерить «расстояние» в сети, где каждая связь может объединять произвольное число элементов.

ФизТех

# математика

# моделирование

# связи

# сети

# теория графов

# физика

Пример структуры гиперграфа: одно гиперребро (выделенная область) охватывает сразу несколько узлов, что невозможно корректно описать обычным графом / © Cambridge University Press

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

В реальной жизни научная статья касается сразу нескольких областей знания, а одна деловая сделка может объединять целый консорциум компаний.

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

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

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

Авторы предложили общую меру расстояния для взвешенных гиперграфов, которая одновременно учитывает и структуру гиперребер (сколько вершин они объединяют, как они пересекаются), и вес каждой связи. Их решение опубликовал журнал Communications Physics.

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

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

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

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

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

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl + Enter.

Московский физико-технический институт (национальный исследовательский университет), известен также как Физтех — ведущий российский вуз по подготовке специалистов в области теоретической, экспериментальной и прикладной физики, математики, информатики, химии, биологии и смежных дисциплин. Расположен в городе Долгопрудном Московской области, отдельные корпуса и факультеты находятся в Жуковском и в Москве.