Семинары

Канал с трансляциями и видеозаписями семинаров

13 мая
Руслан Богатырев
Local-Global Competition Under Home Bias Effect in Consumer Preferences

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


5 мая 2025
Совместный семинар с BIMSA
Михаил Тужилин
Properties of real networks and centrality measures

One of the most important questions in the network science is which characteristics differentiate artificial networks from real ones based on real experimental data. Centrality measures or shortly centralities play important role in this question. There are two main invariants that distinguish real networks from random ones: degree centrality and local clustering coefficient. For real networks, degree centrality obeys a power law, unlike the distribution of random networks (the so-called scale-free property). For small-world networks, the threshold of the average clustering coefficient and the average shortest path length differ from random ones (the small-world property).
There are many mathematical models that simulate these two properties. For example, the Watts-Strogatz network was the first mathematical network that satisfied the small-world property. However, this network is not scale-free. The Barabasi-Albert network is a scale-free network, but the average clustering coefficient is not large enough. These problems were solved in the network proposed by Boccaletti, Hwang, and Latora, which is scale-free and has a large average clustering coefficient.
In the first part of our talk, we will present theorems on the relationships between various centralities and other network characteristics. More precisely, we will show the relationships between stress, betweenness, radiality, and other small-world characteristics. We will present simple network properties in terms of local clustering centrality, where the average clustering coefficient is greater than the global clustering coefficient and vice versa. We will also show the case for a geodesic network where there exists a relationship between the average clustering coefficient and the average shortest path.
In the second part of our talk, we will present a new invariant for real networks, called ksi-centrality. We will show that this ksi-centrality not only distinguishes random networks from real ones, but also prove that it is related to the local clustering coefficient, the algebraic connectivity of the network, and the Cheeger constant. Moreover, Watts-Strogatz, Barabasi-Albert and Boccaletti, Hwang, and Latora networks are generally classified as random or artificial networks by this centrality, but there is a narrow set of parameters for which Watts-Strogatz and Barabasi-Albert networks have the same properties as real networks by this centrality. In this case, Watts-Strogatz and Barabasi-Albert networks have a more tree-like structure, like real networks.

29 апреля
Степан Спирин
Игра с линейным лучшим ответом на графе

Мы рассмотрим игру, в которой полезность игрока линейно зависит от стратегий других агентов, и квадратично от его собственной. Несмотря на то, что такую игру вполне можно определить не используя графы, многие свойства этой модели формулируются в терминах сложных сетей. Коэффициенты в функции полезности игрока можно интерпретировать как веса рёбер, связывающих его с соседями. Равновесная по Нэшу стратегия игрока оказывается пропорциональной значению его центральности Бонасича в сети (Ballester et al., 2006). Также, эффективные сети для такой модели (то есть графы, максимизирующие общую полезность в равновесии) принадлежат классу Nested Split Graphs (Belhaj et al., 2016). Наконец, если рассматривать в такой модели ограниченно рациональных игроков, их уровень рациональности также будет иметь сетевую интерпретацию. В докладе я постараюсь описать эти результаты.


14 апреля
Совместный семинар с BIMSA
Fengling Li
Knot data analysis using multiscale Gauss link integral

In the past decade, topological data analysis has emerged as a powerful algebraic topology approach in data science. Although knot theory and related subjects are a focus of study in mathematics, their success in practical applications is quite limited due to the lack of localization and quantization. We address these challenges by introducing knot data analysis (KDA), a paradigm that incorporates curve segmentation and multiscale analysis into the Gauss link integral. The resulting multiscale Gauss link integral (mGLI) recovers the global topological properties of knots and links at an appropriate scale and offers a multiscale geometric topology approach to capture the local structures and connectivities in data. By integration with machine learning or deep learning, the proposed mGLI significantly outperforms other state-of-the-art methods across various benchmark problems in 13 intricately complex biological datasets, including protein flexibility analysis, protein–ligand interactions, human Ether-à-go-go-Related Gene potassium channel blockade screening, and quantitative toxicity assessment. Our KDA opens a research area—knot deep learning—in data science. This is a joint work with Li Shen, Hongsong Feng, Fengchun Lei, Jie Wu and Guo-Wei Wei.

15 апреля
Чернышев Кирилл

Задача сжатия с потерями в течение нескольких предыдущих десятилетий успешно решалась с помощью методов, построенных на дискретном преобразовании Фурье и немалом количестве эвристик. Они обладают, однако, рядом неустранимых особенностей, как, например, наличие блочных артефактов. Альтернативные подходы на основе нейронных сетей, используя парадигму глубокого обучения, куда более точно моделируют распределение данных (изображения/видео), что обеспечивает большую степень сжатия при том же визуальном качестве. Более того, они способны преодолеть ограничения классических методов, учитывая, например, семантику изображения. Качество моделей во многом зависит от соответствующего пространства латентных представлений, которое формируется в процессе обучения. На семинаре будут рассмотрены некоторые нейросетевые алгоритмы сжатия изображений и видео, а также выделены их ключевые особенности.


8 апреля
Артем Александров
Пределы больших графов

Доклад посвящен описанию способов построению предельных объектов графов. Будут рассмотрены три случая: построение пределов разреженных графов с помощью сходимости Бенжамини-Шрамма, построение пределов плотных графов с помощью графонов Ловаша и наконец попытки построить предельные объекты для графов промежуточной плотности.


1 апреля
Григорий Челноков
On continualization approach to problems of online coloring of hypergraphs.

During the last two decades the algorithmic aspect of classical graph coloring problems have received new attention. In particular due to applied tasks, in which data is getting piece-by-piece and respond is required without delay. Another motivation relates to the case when data is too large to hold in memory. To simulate these kind of real-world tasks were introduced a new variation of classical coloring problems, called on-line coloring.This area of research yielded some nice results but still contains more open problems then solved ones, see, for example [1], [3], [2], [4], [5], [6]. In this talk I'll formulate a de nition of online-coloring twist and the notion of chip-game the main tool with which most of the results regarding online coloring have been obtained. Then I'll apply continualization to chip game, which provides a serial method of achieving upper bounds in chip-game problems (my joint result with I.I.Bogdanov (MIPT, Moscow)). In the second part of my talk we will discuss what are the possibilities to obtain lower bounds using the described method



25 марта
Людмила Прохоренкова
Challenges of measuring diversity and generating structurally diverse graphs

For many graph-related problems, it can be essential to have a set of graphs that are structurally diverse. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, generating such a set is challenging.
First, we discuss how to define diversity for a set of graphs, why this task is non-trivial, and how one can choose a proper diversity measure. The problem of defining diversity is interesting in itself: there is a list of three simple desirable properties of a good diversity measure that are hard to simultaneously satisfy. 
For a given diversity measure, we propose and compare several algorithms optimizing it: we consider approaches based on standard random graph models, local graph optimization, genetic algorithms, and neural generative models. We show that it is possible to significantly improve diversity over basic random graph generators. Additionally, our analysis of generated graphs allows us to better understand the properties of graph distances: depending on which diversity measure is used for optimization, the obtained graphs may possess very different structural properties which gives a better understanding of the graph distance underlying the diversity measure.


18 марта
Михаил Тужилин
Новая центральность: кси-центральность

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




11 марта
Василий Горбунов
Анализ данных и топологический анализ данных.

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





4 марта
Федор Носков
Optimal Noise Reduction in Dense Mixed-Membership Stochastic Block Models under Diverging Spiked Eigenvalues Condition

Community detection is one of the most critical problems in modern network science. Its applications can be found in various fields, from protein modeling to social network analysis. Recently, many papers appeared studying the problem of overlapping community detection, where each node of a network may belong to several communities. In this work, we consider Mixed-Membership Stochastic Block Model (MMSB) first proposed by Airoldi et al. MMSB provides quite a general setting for modeling overlapping community structure in graphs. The central question of this paper is to reconstruct relations between communities given an observed network. We compare different approaches and establish the minimax lower bound on the estimation error. Then, we propose a new estimator that matches this lower bound. Theoretical results are proved under fairly general conditions on the considered model. Finally, we illustrate the theory in a series of experiments.


3 марта
Совместный семинар с BIMSA
Rongling Wu
Statistics at a crossroads: How it can revolutionize artificial intelligence

Artificial intelligence (AI) is profoundly impacting science and society by applying algorithms and machine learning to enable machines to perform humanlike tasks. Statistics as a branch of mathematics, lying at the core of AI and data science, is facing an unprecedented challenge with the surge of complex, heterogenous data across a variety of platforms. In a real sense, statistics is at a crossroads to leverage its central role in revolutionizing the foundational and fundamental framework of AI. In this talk, I will present several state-of-the-art statistical methods that have been widely used in AI across various fields. I will focus on how to develop statistically principled reasoning and theory to validate the application of AI and enhance its interpretability and sustainability. Our approach builds on statistical mechanics theory and methodology derived from interdisciplinary integration.

25 февраля
Артем Александров
Универсальность в сетях и на сетях

Понятие универсальности изначально возникло в теории динамических систем в работах Митчелла Фейгенбаума. Идеи математиков впечатлили физиков-теоретиков и про универсальность заговорили в контексте статистической физики. Бок о бок со статистической физикой, универсальность живо обсуждалась физиками-ядерщиками и специалистами по эргодической теории. В каждом из упомянутых примеров под универсальностью понимают слегка разные вещи, однако общая идея всегда заключается в том, что свойства некоторых наблюдаемых величин могут быть одинаковыми для различных на "микроскопическом уровне" систем. В первой части доклада я расскажу о том что именно понимают под универсальностью физики и математики, а во второй части доклада мы обсудим как увидеть универсальность в теории сетей и динамике на сетях. Доклад основан на статье "Universality in network dynamics", B. Barzel & A.-L. Barabasi.



18 февраля
Максим Клименко

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



11 февраля
Максим Бекетов
Кривизна графов

Широко известно, что на графы (и более широкий класс объектов – в частности, симплициальные и вообще клеточные комплексы) можно смотреть не только комбинаторно, но и геометрически – как на дискретизацию чего-то непрерывного, снабженного метрикой. Мы постараемся на базовом уровне разобраться с таким инвариантом графов, как кривизна, в разных ее вариантах: скалярная, секционная, кривизна Риччи. Эти сюжеты крайне актуальны в современных науках о данных, о чем я также постараюсь сказать несколько слов.



4 февраля 2025
Кияко Елизавета
"Plug-and-Play'' метод для постобучающей обрезки LLM

На семинаре будет представлен новый эффективный метод постобучающей обрезки (pruning) для больших языковых моделей под названием "Plug-and-Play". Смысл данного метода заключается в облегчении инференса моделей глубинного обучения без существенной потери производительности

21 января 2025
Раиса Сафронова

Hyekyoung Lee и соавторы предложили оценивать не только повсеместно распространенные числа Бетти для топологического сравнения коннектомов мозга, но и сравнивать сами представители классов группы гомологий, введя новое расстояние для оценки похожести разных коннектомов. У них с помощью этого анализа получилось разделить здоровых и больных Альцгеймером. Они проводили свое исследования на данных позийтронно-эмиссионой компьютерной томографии. 
Я пытаюсь повторить это исследование, но уже на данных фМРТ и с использованием персистентного лапласиана. Я расскажу, что сделано на данный момент времени и какие трудности не дают пока двигаться вперед.

19 ноября 2024
Андрей Шутов
Гиперболическая геометрия в сложных сетях

Топология безмасштабных сетей находится в тесной связи с гиперболической геометрией. Например, если для сети предположить, что она обладает гиперболической метрикой, то для данной сети выполняется степенной закон. Более того, любой безмасштабной сети с некоторой метрикой можно поставить в соответствие безмасштабную сеть, вложенную в диск Пуанкаре, с теми же статистическими параметрами. На семинаре разберем доказательства этих двух утверждений. Если успеем, поговорим о кластеризации и навигации в таких сетях.

12 ноября 2024
Алиса Баринова

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

Любовь Тупкина

Будет рассказано о некотором иерархическом подходе к поиску кратчайшего пути в графах и анализе его производителности. Данный метод использует кластеризацию для ускорения поиска пути. Подход основан на традиционных алгоритмах, таких как алгоритм Дейкстры, и применяет иерархические методы для сужения зоны поиска пути. Тестирование на реальных графах городов показало высокую производительность метода при минимальных потерях точности.

Дмитрий Федоров

Мы поговорим про несколько Шанхайских задач по гиперграфам.
Они были предложены коллегами из Шанхайского университета и являются обобщением задач про robustness of coupled hypergraphs, higher order dynamical systems.
Также, если успеем, кратко разберём задачи по гиперграфовым изоморфизмам и один алгебраический метод представлений гиперграфов.

29 октября 2024
Василий Горбунов
Обратная задача в теории сетей

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

22 октября 2024
Дмитрий Васильев

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

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

15 октября 2024
Кирилл Решин
Метод кластеризации, вдохновленный идеей гиппокмпа в мозгу

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

Василий Горбунов
Путевые гомологии 

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

— Вторая тема — это относительно недавная статья Ричарда Хепворфа, который и придумал магнитудные гомологии. Интересно посмотреть на передний край этой науки.

24 сенятбря 2024
Александр Нестеров

Доклад посвящён централизованным системам найма на госслужбу в разных странах в разные исторические периоды: Китай, Индия, Великобритания, Франция, Бразилия. Цель доклада в том, чтобы представить и обсудить возможность создания подобной системы в России.

17 сентября 2024
Борис Гавриш
Задача транспортной маршрутизации

Задача транспортной маршрутизации является обобщением задачи коммивояжера: теперь требуется создать маршруты для нескольких грузовиков таким образом, чтобы спрос потребителей был удовлетворен. Транспортная маршрутизация - область активного применения методов дискретной оптимизации на графах. Нами будут рассмотрен метод branch and price, часто используемый для нахождения точного решения, а также эвристический подход memetic computing, являющийся в концептуальном смысле комбинацией вероятностных и жадных методов оптимизации, позволяющей часто получать хорошие приближенные решения в задачах большой размерности

10 сентября 2024 
Антон Зудин
Модификация модели Bala & Goyal

На семинаре будет рассказано о модификации классической модели образования сетей Bala & Goyal (2000), учитывающей устойчивость сети. Изначально будет рассказано про оригинальную модель и некоторые базовые результаты, полученные в рамках этой модели. Затем будет показано, как можно ввести в модель желание каждого агента иметь соединение устойчивое к падениям некоторых элементов сети и показаны текущие результаты, полученные в такой модификации


16 мая 2024
Олег Мартанов
Sanctions in networks: The Most Unkindest Cut of All

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

Виталий Кузнецов
Topological GNN
Улучшение GNN при помощи добавления слоя, учитывающего топологию сети

23 апреля 2024
Абубакарова Лейла
Алгебры Хопфа в комбинаторике


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

9 апреля 2024
Радушев Даниил
Спайковая нейронная сеть как метрическое пространство: эвристики введения расстояния