Лаборатория топологии и сложных сетей/ НИС Complex Networks

Друзья!

В этот вторник (02.12.25) на научном семинаре выступит Константин Сорокин




О топологических структурах в динамике данных

Персистентные гомологии - всем известный стандартный мощный инструмент анализа внутренней структуры многомерных данных, однако, будучи довольно бедной и грубой, есть не так много подходов к обобщению этого метода для изучения динамически меняющихся данных при этом чтобы сохранялась достаточно тонкая внутренняя структура этих самых данных.
Мы поговорим про подходы к изучению динамически меняющихся структур данных (графов, симплициальных комплексов или облаков точек, как самого общего случая, из которых впоследствии фильтрацией Вьеториса-Рипса можно получить фильтрацию пары комплексов) с помощью построения определённого класса комплексов (фактора флаговых по компонентам связности), как эту структуру закодировать немного обобщив конструкцию симплекс-деревьев Бойссоната. Также поговорим о том, что нового интересного в предложенном мной новом подходе, который я, отчасти в шутку, назвал similarity/dissimilarity persistent cobordism, который, действительно, имеет некоторые похожие свойства на настоящие кобордизмы, впрочем не предполагая совпадение классов Штифеля-Уитни, по крайней мере в dissimilaruty случае (это скорее mapping cone).
Анализируя топологию получающихся «пространства изменений» между структурами, мой подход обеспечивает топологическую характеристику локальных геометрических искажений данных, как с точки зрения сходства, так и различия. Я сравню персистентные кобордизмы, с современными методологиями решения похожих задач и обсудим его практическую применимость для нескольких примеров задач топологического анализа данных. Буду рад дискуссии и критике.

Ждем вас 02.12.25 в 18 10 в аудитории 108.

#лаборатория_сложных_сетей

Друзья!

В этот вторник (25.11.25) на учебном семинаре выступит Александра Скрипченко.
Прилагаем анонс её доклада:

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

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


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


#нис_complex_networks

Друзья!

В этот вторник (25.11.25) на научном семинаре онлайн выступит Илья Каржиманов

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

Кубические эндоморфизмы плоскости и вычисления

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

Для тех, кто хочет собраться очно — как обычно ждем вас 25.10.25 в 18 10 в аудитории 108.

#лаборатория_сложных_сетей

Друзья!

В этот вторник (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

Друзья!

В этот вторник (18.11.25) на научном семинаре выступит Левон Минасян.
Прилагаем анонс его доклада:

Сверхбыстрый поиск кратчайшего пути в графах дорог: Contraction Hierarchies, Transit Node Routing

На докладе мы обсудим все современные подходы поиска кратчайших путей в графе.
Сначала мы сфокусируемся на непосредственном ускорении алгоритма Дейкстры, посмотрим на множество
существующих на данных момент эвристик: A*, ALT, Arc Flags, Reach, Reach Flags, REAL.
Во второй части мы детально обсудим рок-звезду в поиске кратчайших путей: алгоритм Contraction Hierarchies. Закончим обзором SOTA-подхода: спайки Contraction Hierarchies с фреймворком Transit Node Routing.

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

Ждем вас 18.10.25 в 18 10 в аудитории 108.

#лаборатория_сложных_сетей

Друзья!

В этот вторник (11.11.25) на учебном семинаре выступит Кирилл Решин.

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

Топологический подход к выбору пороговых значений в сетях

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

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

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


#нис_complex_networks

Друзья!

В этот вторник (11.11.25) на научном семинаре выступит Георгий Мороз.


Корпусные исследования вариативности в русском языке билингвов

В Международной лаборатории языковой конвергенции давно собираются и аннотируются устные корпуса диалектной и билингвальной речи (https://lingconlab.ru/ru/). Аннотированный материал служит богатым материалом для исследования вариативности в современном русском языке (примером такой вариативности может быть распределение  форм яблоко упало нА голову или на гОлову). В рамках доклада мы рассмотрим

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


Ждем вас 11.10.25 в 18 10 в аудитории 108.

#лаборатория_сложных_сетей

Друзья!

В этот вторник (28.10.25) на научном семинаре выступит Шахир Сафи.

Название: Networks and Signals

Аннотация:
In the pioneering works of Granovetter (1973, 1995), he found that a large proportion of jobs are found through weak rather than strong ties. However, subsequent studies have also found the frequent use of strong ties, and overall, the empirical evidence on the relative returns to weak versus strong ties is mixed. My analysis shows that a model of referrals with strategic recommendations by employees and tie selections by job seeking workers (applicants) can help reconcile Granovetter’s “strength of weak ties” theory with the opposing empirical findings.

Ждем вас 28.10.25 в 18 00 в аудитории 108.

P.S.
Учебного семинара в этот вторник НЕ будет

#лаборатория_сложных_сетей

Друзья, (для тех кто не проверяет чат, но читает канал) семинар в сегодня 16:20 тоже будет

Федор Ожегов расскажет про случайные блуждания на графах

Друзья!

В этот вторник (21.10.25) на научном семинаре выступит Сергей Юдин с рассказом про тензорные поезда.

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

- Краткий интро: что такое TT, зачем нужен и какие операции с ним делают
- Эвристики для приближения тензора в TT
- Ну и самый сочный кусок – обзор результатов. Прошло 15 лет с момента, как вышла фундаментальная статья И. Оселедеца по тензорным поездам, и появилось очень много приложений, в которых Tensor Train эффективно работает, или, предлагает некий потенциал для эффективной работы:
• Моделирование систем с низкими корреляциями
• Black-Box оптимизация
• Молекулярный докинг
• Сжатие нейронных сетей и LLM
• Оптимизация с ограничениями (например, портфельная оптимизация)
• Численное дифференцирование и интегрирование


Ждем вас 21.10.25 в 18 00 в аудитории 108.

*ссылка на зум лежит в чате лаборатории, а трансляция идет по ссылке - https://www.youtube.com/watch?v=dPN8rfXHg4k (к сожалению название сбилось, на него можно не обращать внимание)

На следующей за этим докладом паре выступит Олег Рустумович Мусин (University of Texas Rio Grande Valley).

Topic: Гипотеза Борсука, задачи о справедливом дележе, быстрые алгоритмы и приложения комбинаторной топологии.

В рамках доклада будут даны не только сведения о уже полученных результатах но и даны необходимые preliminaries для двух задач, про которые предлагается подумать о возможности получения решений через AI. (В духе того, что будет показано на первой паре)

Анонс от автора доклада:

Знаменитая гипотеза Борсука неверна для n ⩾ 64, вопрос остаётся открытым для 4 ⩽ n ⩽ 63. Пример для n=64 был построен для множества с двумя расстояниями. Я опишу метод построения таких множеств из произвольного графа и обсужу возможность построения контрпримеров с помощью нейронных сетей.
Задача о справедливом дележе стара и известна, имеет множество форм и встречается во многих реальных ситуациях. В этом докладе я рассмотрю теоремы существования для задач о гармонии арендной платы и разрезании торта, а также их обобщения. 
Третья часть доклада была вдохновлена ​​статьей в New York Times “To Divide the Rent, Start With a Triangle” by Albert Sun (April 28, 2014), которая содержит калькулятор справедливой арендной платы, основанный на работе Фрэнсиса Су. Мы рассматриваем алгоритмическую сложность задач о справедливом дележе, уделяя особое внимание минимизации количества запросов, необходимых для нахождения приближенного решения с желаемой точностью. Для нескольких классов задач о справедливом дележе показано, что при определенных естественных условиях на множествах предпочтений логарифмическое количество запросов относительно точности достаточно. 
Недавние исследования показали, что сложность нейронной сети тесно связана с топологической сложностью её входных данных. В связи с этим, мы предлагаем новый, основанный на топологии подход «разделяй и властвуй», основанный на разложении входных данных на топологически более простые подмножества. Наш метод разбивает набор данных на сбалансированные области, используя теорему о сэндвиче с ветчиной, и направлен на минимизацию топологической сложности. 
Я также рассмотрю некоторые другие проблемы, связанные с применением комбинаторной топологии

Это будет на паре 14.10.25 в 18 00 также в аудитории 108 и также, по очевидным причинам, докладчик будет присутствовать онлайн, однако, всех кто придет на матфак будем очень рады видеть

Друзья, в этот вторник нас ожидает большая (и в полном смысле этого слова глобальная) программа связанная с комбинаторикой и AI4Science.

Начнем мы с доклада выпускника матфака, ныне PhD студента CUHK, Shenzhen Дмитрия Рыбина. Topic: AlphaEvolve и Машинное Обучение для Математики.

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

Мы разберем примеры использования машинного обучения для поиска математических объектов, в частности, расскажем про наш результат об ускорении матричного умножения XX^t. А также детально обсудим использование LLM/AlphaEvolve для чисто математических вопросов - постановки задач и дешевые эксперименты доступные всем. 

Это нас ожидает на паре 14.10.25 в 16 20 в аудитории 108 (и, конечно, онлайн)

Товарищи,

На учебном семинаре в этот вторник (07.10.25) выступит Иван Самойленко. Анонс доклада:

"Гиперграфы - метаобзор области".

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

Что точно планируется:
* Пробежаться по недавней обзорной статье "A Survey on Hypergraph Mining: Patterns, Tools, and Generators"
* Показать несколько хороших (интересных и состоятельных с точки зрения автора доклада) результатов в области, а также показать разные способы получать из данных взаимодействия высокого порядка
* Обсудить несколько сомнительных (с точки зрения автора доклада) результатов (в частности как минимум одну статью с A* конференции) и с какими проблемами сталкиваются исследователи гиперграфов
* Рассказать про результаты научной группы автора доклада (по крайней мере по этому вопросу у автора есть заготовленный и рассказанный больше 1 раза кусок презентации)
* Обсудить какие есть открытые вопросы и задачи связанные с гиперграфами

Точно будет на паре 07.10.25 в 16 20 в аудитории 108. (и может быть залезем на следующую пару, при наличии такого желания и необходимости)

Друзья!

В этот вторник (30.09.25) на учебном семинаре выступит Михаил Тужилин.

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

'Инварианты реальных сетей и порождающие их процессы формирования сетей.'

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

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


#нис_complex_networks

Друзья, завтра наша Лаборатория сложных сетей совместно с ИРГ "Экономика информации" проведет междисциплинарный воркшоп специалистов в теории игр, теории сетей и смежных областях.
Приглашаем всех заинтересованных в ауд. 108


Program.

10:00 Reception, open words

Session 1 (RUS/ENG)
10:10 – 10:40 Alexander Karpov (HSE) Большие домены Кондорсе.
10:40 – 11:10 Daniil Tkachev (HSE) Centrality indices taking into account parameters of vertices and group influence.

Coffee break (10 min)

11:20 – 11:50 Anna Semenova (HSE) Новые индексы центральности в сетевых структурах: обзор, приложения, устойчивость.
11:50 – 12:20 Ruslan Bogatyrev (HSE) Market Dynamics on Complex Networks.

12:20 – 13:10 Lunch

Session 2 (ENG)
13:10 – 13:40 Emre Dogan (HSE) Lawyer Assignment with Congestion: Redesigning the Comal County Pilot Program.
13:40 – 14:10 Anastasia Antsygina (HSE) Support Link Formation in Contests: Theory and an Experiment.

Coffee break (10 min)

14:20 – 14:50 Kivanc Akoz (HSE) Inclusive Networks
14:50 – 15:20 Mikhail Bludov (MIPT) Scarf’s theorem and homotopy invariants.

Друзья, у нас немного спонтанно получилось расширить сегодняшнюю культурную программу по AI в математике засчет лекции Algorithm Design Automation профессора Zhi-Quan Luo (https://scholar.google.com/citations?user=dW3gcXoAAAAJ&hl=en)


Анонс лекции:

 Abstract: This talk addresses the challenge of designing and optimizing algorithms under strict computational and memory constraints, with applications spanning massive MIMO systems, wireless communication, and large-scale AI training. Beginning with a finite-horizon optimization perspective, we review classical gradient descent, its limitations with constant step sizes, and optimal finite-step schemes derived from Chebyshev minimax polynomials. We then present recent advances in matrix multiplication, including AI-discovered state-of-the-art algorithms for structured products such as XX^T, achieving notable speedups and energy savings over recursive Strassen methods in both CPU and GPU settings. The discussion extends to assessing large language models’ (LLMs) capabilities in mathematical reasoning and novel problem solving, highlighting cases where LLM-assisted approaches led to breakthroughs. Finally, we introduce AlphaEvolve, a code-space search framework for automated algorithm discovery, demonstrating its success in improving long-standing algorithmic bounds and generating efficient CUDA kernels. The talk concludes with potential future directions, including new algorithms for causal attention, constrained SVD, and advanced GPU kernels.

Prof. Luo’s talk will also include a part where he will introduce CUHK-Shenzhen University and postgraduate study opportunities there. 

*как упомянуто в конце анонса, после лекции также расскажут об академических возможностях и возможностях коллаборации с университетом Shenzhen


Время: 18:30
Аудитория: 427

Ребят, всем привет!

23 сентября на матфак приезжает Андрей Окуньков - математик, лауреат Филдсовской премии.
На лекции он расскажет про влияние искусственного интеллекта на природу математического открытия, после чего выступят два докладчика про использование ИИ в математике.

Вся информация о мероприятии и описание докладов на странице

А для очного посещения нужно заполнить форму

Друзья, завтра семинаров не будет.

Однако, на факультете пройдет мероприятие с участием сотрудников нашей лаборатории.

Друзья!

В этот вторник (16.09.25) на учебном семинаре выступит Михаил Добрицын.

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

'Обобщение задачи о двух альпинистах на произвольные графы.'

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


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


#нис_complex_networks