Выборочная энтропия для графовых сигналов: измерение хаоса в сетях

Что такое нерегулярность и зачем её измерять

Что такое «нерегулярность» и зачем её измерять

Представьте, что вы слушаете сердцебиение. Врач не просто считает удары в минуту – он обращает внимание на ритм: насколько равномерны промежутки между ударами, есть ли в них скрытый порядок или, напротив, хаос. Именно для этого в 2000 году Ричман и Мурман разработали метод под названием выборочная энтропия (Sample Entropy, или SampEn) – инструмент, позволяющий формально описать, насколько «непредсказуем» сигнал во времени.

Принцип работает так: берётся временной ряд, из него вырезаются короткие «шаблоны» заданной длины m, а затем подсчитывается, как часто два похожих шаблона остаются похожими при увеличении их длины до m+1. Если такое «продолжение сходства» случается редко – сигнал хаотичен, его энтропия высока. Если похожие шаблоны регулярно повторяются – сигнал упорядочен, энтропия низка. Метод элегантен, хорошо изучен и применяется в кардиологии, нейрофизиологии, климатологии – везде, где нужно понять степень «организованности» данных.

Но у него есть принципиальное ограничение: он работает только с линейными последовательностями. Одна точка следует за другой, как вагоны в поезде. Что если данные устроены иначе – не в виде цепочки, а в виде сети?

Графы как основа для анализа данных

Когда данные живут на графах

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

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

Область обработки графовых сигналов (Graph Signal Processing, GSP) занимается именно такими данными. Она заимствует идеи из классической теории сигналов – фильтрацию, преобразования, частотный анализ – и адаптирует их к нерегулярной структуре графов. Ключевой элемент здесь – так называемый оператор сдвига графа (Graph Shift Operator, GSO). По аналогии с тем, как сдвиг во времени позволяет «передвигаться» по временному ряду, оператор сдвига графа позволяет «передвигаться» по сети: переходить от узла к его соседям, агрегировать информацию из окружения.

Именно здесь и возникает вопрос, который поставили перед собой авторы рассматриваемого исследования: можно ли измерить «хаотичность» или «нерегулярность» графового сигнала так же, как выборочная энтропия измеряет её для временного ряда?

Как адаптировать выборочную энтропию к графам

Идея: заменить время на соседей

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

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

В SampEn_G вместо «соседей во времени» используются соседи в графе. Для каждого узла i строится шаблон следующим образом:

• Нулевой элемент шаблона – это само значение сигнала в узле i.
• Первый элемент – это среднее значение сигнала по непосредственным соседям узла i (то есть то, что «видит» узел на расстоянии одного шага по графу).
• Второй элемент – среднее по соседям соседей (два шага по графу).
• И так далее, до m−1 шагов.

Технически это реализуется через последовательное применение оператора сдвига графа к исходному сигналу. Если обозначить оператор как S_G, то значение на k-м шаге вычисляется как S_G^kx, где x – исходный сигнал. Таким образом, для каждого узла формируется вектор из m чисел, описывающий, как сигнал распределён в его локальном окружении на разных «расстояниях» по сети.

После того как такие шаблоны построены для всех узлов, дальнейшие вычисления полностью повторяют логику классического SampEn: считаем, как часто два шаблона длины m «похожи» (отличаются друг от друга не более чем на порог r), и проверяем, сохраняется ли это сходство при добавлении ещё одного элемента. Результат – логарифм отношения этих двух количеств, взятый с отрицательным знаком.

Проверка работы SampEnG на простом случае

Проверка: работает ли это на простом случае?

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

Применение SampEn_G к такому графу даёт в точности тот же результат, что и классический SampEn для соответствующего временного ряда. Это не случайность: если каждый узел «смотрит» только на следующий по цепочке, то «соседи в графе» – это именно «соседи во времени». Формальное доказательство этого факта показывает, что SampEn_G является корректным обобщением: он не «изобретает новый метод», а расширяет существующий на более широкий класс структур.

Тестирование чувствительности SampEnG к хаосу

Чувствительность к хаосу: тест с логистическим отображением

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

Это простая формула: x_t+1 = R · x_t · (1 − x_t). При разных значениях параметра R она генерирует принципиально разные режимы поведения:

• При малых значениях R система быстро приходит к устойчивому состоянию – все значения стремятся к одной точке. Это максимально «скучный» сигнал.
• При значениях R около 3 система начинает колебаться между двумя точками, затем между четырьмя, восьмью – это так называемые «бифуркации».
• При значениях R близких к 4 система переходит в хаотический режим: значения скачут непредсказуемо, и никакой закономерности не прослеживается.

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

Эксперименты с SampEnG на случайных сетевых структурах

Эксперименты на случайных сетях

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

На таких графах авторы генерировали сигналы с помощью логистического отображения и исследовали, как SampEn_G реагирует на изменения параметров. Наблюдения оказались содержательными:

1. Влияние параметра R логистического отображения. Поведение SampEn_G полностью повторяло ожидаемую картину: высокая энтропия для хаотических режимов, низкая – для регулярных. Это хороший знак: метод «видит» динамику сигнала даже на нерегулярной сетевой структуре.
2. Влияние плотности связей. Здесь проявился интересный эффект: чем выше вероятность p (то есть чем больше у каждого узла соседей), тем ниже значение SampEn_G. Объяснение интуитивно понятно: когда у узла много соседей, его локальный шаблон усредняет сигналы по большому числу связей, и разнообразие шаблонов снижается – как если бы вы смотрели не на отдельные пиксели, а на сильно размытое изображение. Высокосвязная сеть как бы «сглаживает» хаос.
3. Влияние длины шаблона m. Как и в классическом SampEn, увеличение длины шаблона снижает итоговое значение энтропии – длинные шаблоны встречаются реже и реже совпадают. Авторы рекомендуют придерживаться стандартных значений m равных 2 или 3, что согласуется с практикой применения классической выборочной энтропии.

Практичность и вычислительная скорость метода SampEnG

Вопрос скорости: насколько это практично

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

Итоговая сложность: O(m(N+E) + N²). На практике для графов с несколькими тысячами узлов вычисления укладываются в приемлемое время. Это делает метод реально применимым для задач умеренного масштаба – анализа нейронных сетей на основе данных МРТ, мониторинга небольших коммуникационных сетей, изучения региональных климатических данных.

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

Применение выборочной энтропии для графовых сигналов

Где это может пригодиться

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

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

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

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

Социальные сети и информационные каскады. Распространение информации в социальных сетях следует сетевой логике: одна публикация может быть переадресована сотнями узлов одновременно. Измерение «хаотичности» этого распространения с учётом топологии сети – задача, для которой SampEn_G выглядит как естественный инструмент.

Дальнейшие шаги в развитии метода SampEnG

Что ещё предстоит сделать

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

• Теоретический анализ устойчивости метода: как он ведёт себя при малых возмущениях структуры графа или сигнала.
• Сравнение с другими подходами к измерению нерегулярности на графах, в том числе с методами, основанными на символьной динамике.
• Исследование влияния выбора оператора сдвига: разные GSO дают разные результаты, и пока нет систематического понимания того, как выбирать оператор под конкретную задачу.
• Расширение на динамические графы, где структура сети меняется со временем – это особенно актуально для задач мониторинга в реальном времени.
• Тестирование на реальных наборах данных из нейронаук, климатологии и инфраструктурного мониторинга.

Каждый из этих пунктов – не просто академический интерес. Это конкретные шаги, без которых метод останется лабораторным прототипом, а не рабочим инструментом.

Преимущества учета структуры данных в анализе

Почему это важно – если говорить прямо

Большинство инструментов для анализа временных рядов создавались в эпоху, когда «данные» означали «одна последовательность чисел». Физиологический сигнал, биржевой курс, показания датчика – всё это укладывалось в одномерную цепочку. Выборочная энтропия была создана именно для этой парадигмы, и она прекрасно в ней работает.

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

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

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