Друзья!

В этот вторник (04.03.25) на учебном семинаре выступит Селиванова Ксения.

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

Доклад основан на статье A Tutorial on Spectral Clustering . В последние годы спектральная кластеризация стала одним из самых популярных современных алгоритмов кластеризации. Она проста в реализации, может быть эффективно реализована с помощью стандартного программного обеспечения для линейной алгебры и часто превосходит традиционные алгоритмы кластеризации, такие как алгоритм k-средних. На первый взгляд спектральная кластеризация выглядит немного загадочной, и не очевидно, почему и как она вообще работает и что она на самом деле делает. Цель этого руководства — дать некоторое интуитивное понимание этих вопросов.


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

#нис_complex_networks

Друзья!

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

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

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


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

#нис_complex_networks

Друзья!

В этот вторник (11.03.25) на научном семинаре выступит Василий Геннадьевич Горбунов.

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

Анализ данных и топологический анализ данных.

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


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

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

Друзья!

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

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

Новая центральность: кси-центральность

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

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


Доклад основан на следующем тексте ArXiv:2503.02488

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


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

Друзья!

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

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


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

В работе "Mutant knots and intersection graphs" Ландо и Чмутов идут дальше, и показывают, что для большого семейства инвариантов их подсчёт можно свести к изучению графов пересечений хордовых диаграмм (что является более простым и понятным объектом). Авторы показывают, что инварианты Васильева, не различающие узлы-мутанты (к таким, например, относятся многочлены Александера и Джонса) на самом деле зависят только от вышеупомянутых графов, а не от хордовых диаграмм. И, более того, только такие инварианты могут быть восстановлены по весовым системам, зависящим только от графов пересечений, с помощью композиции с инвариантом Концевича.

В своём докладе я разберу основную теорему, её доказательство, а также связь с весовыми системами, ассоциированными с некоторыми алгебрами Ли, в частности, с SL2.

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

#нис_complex_networks

Друзья!

В этот вторник (25.03.25) на учебном семинаре выступит Амина Каракотова.

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


Весовые системы играют ключевую роль в изучении инвариантов узлов. Одним из важных источников весовых систем являются алгебры Ли, в частности алгебра Ли sl-2. Весовая система, порожденная sl-2, принимает значения в цетре ZU(sl-2) универсальной обертывающей алгебры U(sl-2), которая изоморфна кольцу многочленов от элемента Казимира c. Подсчет коэффициентов при некоторых c^n остается открытой проблемой.

В статье "On a weight system conjecturally related to sl-2" рассматривается специальная весовая система R_k, определяемая как разность между количеством четных и нечетных циклов длины 2k в графе пересечений ориентированной хордовой диаграммы. В докладе будут представлены основные свойства этой весовой системы и описана ее связь с коэффициентом c^k в значении весовой системы sl-2, примененной к хордовой диаграмме порядка 2k.

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

#нис_complex_networks

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

C докладом в этот раз выступит Людмила Прохоренкова, Senior Researcher из Yandex Research. Аннотация доклада:

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.

Сам доклад будет основан на статьях https://arxiv.org/abs/2409.18859 (была на NeurIPS в этом году) и https://arxiv.org/abs/2410.14556. Для удаленных слушателей в этот раз должно быть особенно удобно слушать, так что кто не сможет прийти 25.03.25 в 18:00 в аудиторию 108 — ждем вас в зуме

Друзья!

В этот вторник (01.04.25) на научном семинаре выступит Григорий Челноков.

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


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


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

Друзья!
В этот вторник (01.04.25) на учебном семинаре выступят Каракотова Амина и Усанов Сергей.

Сначала Амина закончит свой рассказ с прошлой недели. Затем выступит Сергей — анонс его доклада прилагаем:




Две недели назад (18.03) я начал рассказывать про работу Ландо и Чмутова "Mutant knots and intersection graphs". Тогда я успел разобрать формулировку и доказательство основной теоремы, которая позволяла свести вычисление инвариантов конечного типа, не различающих мутации узлов, от хордовых диаграмм к графам пересечений.

Одной из самых простых и потому популярных для изучения весовых систем, ассоциированных с алгебрами Ли (про них рассказывала Амина на семинаре 25.03), является весовая система, построенная на основе SL2. Известно, что её значения совпадают со значением окрашенных многочленов Джонса, а они, в свою очередь, действительно, не различают мутации. Однако, показать это соответствие непросто, поэтому авторы работы предлагают частное доказательство для весовой SL2 системы, показывающее, что она зависит даже не от графа пересечений, а от от его матроида.

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

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


#нис_complex_networks

Друзья!

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

Тема: Пределы больших графов

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

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

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

Друзья!
В этот вторник (08.04.25) на учебном семинаре выступит Романеева Нина.
Прилагаем анонс ее доклада:

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

В работе "The distribution of the number of cycles in directed and undirected random 2-regular graphs" представлены новые аналитические результаты для распределения числа циклов в ориентированных и неориентированных 2-RRG, состоящих из N узлов. В своём докладе расскажу, как средняя длина циклов масштабируется с ln⁡N и N, и покажу точные формулы для распределения числа циклов, выраженные через числа Стирлинга первого рода. Вы узнаете, как распределения сходятся к Пуассоновским при больших N, а также о новых статистических свойствах неориентированных 2-RRG, которые ранее не были исследованы.

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


#нис_complex_networks

Друзья!
Уже завтра (14.04.25) на совместном семинаре с BIMSA в 15 00 выступит 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.


Сслыка на зум

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

Друзья!
В этот вторник (15.04.25) на учебном семинаре выступит Минасян Левон.

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

Мы обсудим одну из красивейших в CS конструкций - суффиксное дерево.
До появления этой структуры(1973) Дональд Кнут выдвигал гипотезы о том, что некоторые задачи в теории алгоритмов строк являются неразрешимыми за линейное время. Ее появление в 1973 и оптимальный алгоритм ее построения, оба созданные П. Винером опровергли гипотезы Кнута. Суффиксное дерево позволяет оптимально решать огромное число различных задач на строках. Его преимущество в том, что им удобно пользоваться, однако его построение нетривиально, и оно станет центральным объектом моего рассказа. Мы обсудим алгоритм, предложенный Э. Укконеном в 1995 - он является самым простым для понимания из всех, и при этом оптимален. В конце, если останется время, мы поговорим про связанные задачи и про альтернативные структуры.

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


#нис_complex_networks

Друзья!

В этот вторник (15.04.25) на научном семинаре выступит Чернышев Кирилл (Сбер, ДРИИМО).

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


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

Прилагаем ссылку на зум.

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

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

Друзья!
Сегодня, к сожалению, семинаров не будет.

Друзья!

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

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

"Игра с линейным лучшим ответом на графе"

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

Большая часть доклада будет основана на следующих статьях
1) https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1468-0262.2006.00709.x
2) https://econtheory.org/ojs/index.php/te/article/viewFile/20160357/14668/443


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

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

Друзья!
В этот вторник (29.04.25) на учебном семинаре выступит Алексей Зайцев.

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


"Позитроиды и непересекающиеся разбиения"

В данном докладе я напомню определение специального класса матроидов, называемых позитроидами. Данное определение было введено Постниковым для изучения положительной части Грассманиана. Мы обсудим биекции класса позитроидов с различными комбинаторными объектами, среди которых ожерелья Грассмана, украшенные перестановки, Le-диаграммы и plabic графы. Я также расскажу, как позитроиды связаны с непересекающимися разбиениями (non-crossing partitions), и, если успеем, расскажу о приложениях данного результата.

Доклад основан на статье https://arxiv.org/abs/1308.2698v2

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


#нис_complex_networks

Друзья!
Уже завтра (05.05.25) на совместном семинаре с BIMSA в 15 00 выступит Михаил Тужилин.

Прилагаем анонс его доклада, а так же ссылку на зум:

"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.


Сслыка на зум

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

Друзья!
В этот вторник (13.05.25) на учебном семинаре продолжит свой рассказ Алексей Зайцев.

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


"Позитроиды и непересекающиеся разбиения"

В данном докладе я напомню определение специального класса матроидов, называемых позитроидами. Данное определение было введено Постниковым для изучения положительной части Грассманиана. Мы обсудим биекции класса позитроидов с различными комбинаторными объектами, среди которых ожерелья Грассмана, украшенные перестановки, Le-диаграммы и plabic графы. Я также расскажу, как позитроиды связаны с непересекающимися разбиениями (non-crossing partitions), и, если успеем, расскажу о приложениях данного результата.

Доклад основан на статье https://arxiv.org/abs/1308.2698v2

Ждем вас 13.05.25 в 16 20 в аудитории 108 (давайте попробуем начать вовремя)


#нис_complex_networks

Друзья!

В этот вторник (13.05.25) на научном семинаре выступит Руслан Богатырев.

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

''Local-Global Competition Under Home Bias Effect in Consumer Preferences''

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

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

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

Друзья!
В этот вторник (20.05.25) на учебном семинаре продолжит свой рассказ Алексей Зайцев.

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


"Позитроиды и непересекающиеся разбиения"

В данном докладе я напомню определение специального класса матроидов, называемых позитроидами. Данное определение было введено Постниковым для изучения положительной части Грассманиана. Мы обсудим биекции класса позитроидов с различными комбинаторными объектами, среди которых ожерелья Грассмана, украшенные перестановки, Le-диаграммы и plabic графы. Я также расскажу, как позитроиды связаны с непересекающимися разбиениями (non-crossing partitions), и, если успеем, расскажу о приложениях данного результата.

Доклад основан на статье https://arxiv.org/abs/1308.2698v2

Ждем вас 20.05.25 в 16 20 в аудитории 108 (давайте попробуем начать вовремя)


#нис_complex_networks