Друзья!

В этот вторник (18.11.25) на учебном семинаре выступит Cергей Усанов

Прилагаем анонс его доклада:

Hodge Laplacian

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

(1) Hodge Laplacian

Спектральный анализ применяют как для непрерывных объектов, так и для дискретных: для гладких многообразий наименьшие собственные значения Лапласиана отвечают за общую форму многообразия, а для графов они говорят про связность (например, насколько легко разбить граф на несвязные компоненты удалением рёбер).
Лапласиан естественным образом обобщается на симплициальные комплексы L: C_n —> C_n, и в таком виде он разбивает пространство симлексов на сумму ядра, отвечающего за гомологии, и образа, часть которого приходит из старших симплексов C_{n+1}, а часть из младших C_{n-1}.

Авторы статьи (в комментариях), апеллируют к тому, что осмысленно смотреть не просто на собственные вектора Лапласиана, но также и на их положение относительно этих трёх компонент. Утверждается, что три компоненты C_1 = grad x curl x harmonic отвечают за "дырки", области с высокой кластеризацией (кучностью вершин и рёбер) и важные "мосты", удаление которых влияет на связность графа.

Это даёт возможность ввести трёхцветную раскраску на рёбрах графа, в соответствии с разложением каждого ребра по трём компонентам.

(2) Mapper

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

(3) Hodge Mapper

В рамках группового проекта на школе ЛИПС появилась идея объединить два подхода: получать естественное покрытие тремя множествами из разложения Ходж Лапласиана, и затем, применив кластеризацию, подавать результат на вход мепперу. Алгоритм преследует цель получить упрощённую визуализацию больших графов / сетей с сохранением некоторой топологической информации.

В статье, как и в алгоритме Hodge Mapper присутствует много свободы выбора и эвристик, поэтому после теоретической части доклада, я бы хотел поделиться идеями для экспериментов и, возможно, получить несколько советов :)

Ждем вас 18.11.25 в 16 20 в аудитории 108.


#нис_complex_networks