Энтропия иерархии сети для количественной оценки различий графов

Почему крошечные различия в сетях важны

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

Рассмотрение сети по слоям

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

Дать слово связям: сжатие пар узлов

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

Измерение потери информации с помощью энтропии

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

Улавливание более тонкой структуры и изменений во времени

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

Реальные применения: мобильность и белки

Чтобы показать практическую ценность, авторы применили свою меру расстояния к ежедневным сетям мобильности между сотнями китайских городов в первые месяцы COVID-19. Используя начало января как базу, энтропия иерархии показала, как шаблоны перемещений менялись во время массовых поездок на Китайский Новый год, введения строгих карантинных мер и последующего постепенного восстановления, хорошо соотнесённо с известными изменениями в политике и закономерностями сообществ мобильности. В другой области применения они трактуют структуры белков как сети аминокислот, связанных при близком пространственном расположении. Без обучения или вручную создаваемых признаков кластеризация белков по новой метрике достигает порядка 75% точности в разделении ферментов и неферментов — сопоставимо с современными контролируемыми нейросетевыми подходами.

Что это значит простыми словами

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

Цитирование: Mou, J., Wang, L., Zhang, C. et al. Network hierarchy entropy for quantifying graph dissimilarity. Commun Phys 9, 83 (2026). https://doi.org/10.1038/s42005-026-02523-9

Ключевые слова: сходство сетей, сложные сети, меры энтропии, распространение эпидемий, сети структуры белка