Разрушение сложных сетей на основе графовой нейронной сети высшего порядка

Почему разрушение сетей может нас защитить

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

От реальной жизни к сетям связей

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

Почему простые связи упускают скрытых влиятельных лиц

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

Видеть роли издалека и вблизи

Авторы предлагают фреймворк под названием SPR — Structural and Processual Role aware Network Dismantling (учитывающий структурные и процессуальные роли при разрушении сети), построенный на более общей графовой нейронной сети высшего порядка (HoGNN). Сначала они переводят реальную систему в сеть и вычисляют набор базовых признаков для каждого узла, отражающих как локальные характеристики, такие как число соседей, так и глобальные, такие как близость к другим. С широкого ракурса SPR обучается распознавать структурную роль каждого узла в общей архитектуре: например, хабы, мосты между сообществами или пограничные узлы. Узлы, играющие похожие роли, даже если они удалены друг от друга, группируются в связи высшего порядка, называемые гиперребрами. С ближнего плана SPR отслеживает, как узел участвует во множестве перекрывающихся небольших групп разных размеров, раскрывая его процессуальную роль — то есть как меняется его влияние в треугольниках и более больших объединениях.

Позволяя сети самостоятельно узнать, что важно

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

Насколько хорошо метод работает на практике

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

Что это означает для управления сложными системами

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

Цитирование: Zhou, W., Tan, S., Fang, Y. et al. Dismantling complex networks based on higher-order graph neural network. Commun Phys 9, 181 (2026). https://doi.org/10.1038/s42005-026-02601-y

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