Весная 2023

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

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

Видео

Аннотация: Рассматривается однородный марковский процесс с непрерывным временем на фазовом пространстве Z_+ = {0, 1, 2, ...}, который мы интерпретируем как движение частицы. Процесс предполагается непрерывным в том смысле, что частица не может «перескакивать» через точки Z_+, то есть при каждой смене положения частицы ее координата изменяется на единицу. Процесс снабжен механизмом ветвления. Источники ветвления могут находиться в каждой точке Z_+. В момент ветвления новые частицы появляются в точке ветвления и дальше начинают эволюционировать независимо друг от друга (и от остальных частиц) по тем же законам, что и начальная частица. Такому ветвящемуся марковскому процессу соответствует матрица Якоби. В терминах ортогональных многочленов, отвечающих этой матрице, получены формулы для среднего числа частиц в произвольной фиксированной точке Z_+ в момент времени t > 0. Результаты применены к некоторым конкретным моделям, получено точное значение для среднего числа частиц в терминах специальных функций и найдено его асимптотическое поведение при больших временах.

Видео

Аннотация: Классическая задача кластеризации графа состоит в разбиении вершин графа на плотные кластеры. В настоящее время эту проблему часто называют «проблемой обнаружения сообществ» из-за ее многочисленных приложений в различных областях, таких как социология, нейронаука, библиография и рекомендательные системы. Эталонной моделью для проблемы кластеризации графов является стохастическая блочная модель (SBM), которая представляет собой неоднородную версию случайного графа Эрдоша-Реньи. В этом докладе я обсуждаю несколько обобщений SBM, выходящих за рамки бинарных взаимодействий, моделируемых простыми графами. В частности, я рассматриваю сеть, в которой наблюдаемые взаимодействия принадлежат некоторому измеримому пространству взаимодействия. Это могут быть категориальные и векторнозначные взаимодействия, в том числе временные ряды. Будут представлены теоретико-информационные критерии сильного восстановления кластеров в терминах разреженности данных, статистического сходства между внутри- и меж-блочными распределениями взаимодействия, а также формы и размера пространства взаимодействия. Эта общая структура позволяет изучать темпоральные сети, в которых и количество узлов, и временной горизонт стремятся к бесконечности, и в которых временные паттерны взаимодействия коррелируют во времени. Будет представлен эффективный спектральный алгоритм для восстановления кластеров, который будет продемонстрирован на реальных и синтетических примерах сети. В некоторых приложениях структура гиперграфов более уместна, чем структура простых графов или даже графов со взвешенными ребрами. Условия восстановления кластеров для кластеризации гиперграфа также доступны и будут обсуждаться, если позволит время. Доклад основан на серии совместных работ с M. Dreveton (EPFL), K. Alaluusua и L. Leskela (Aalto University), V. Kumar (Inria).

Видео

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

Видео

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

Видео, Слайды

Аннотация: Рассмотрим авторегрессионную цепь Маркова X_n порядка 1 с параметром 0<a<1. Предположим, что н.о.р. инновации цепи принимают лишь два значения +1 and -1, а для параметра выполняется a<=2/3. Мы найдем точную асимптотику вероятности положительности X_n на длительном временном интервале, а так же слабый предел соответствующих условных распределений. Это предельное распределение квази-стационарно и не имеет атомов. Оно сингулярно относительно меры Лебега при 1/2<a<2/3, а при a=2/3 и симметрично распределенных инновациях равномерно на отрезке [0,3]. Схожими свойствами обладают свертки Бернулли.

Оказывается, что для инноваций со значениями +1 and -1 существует тесная связь между цепью X_n, жизнь которой сокращена до момента выхода из положительной полуоси, и классической динамической системой, задаваемой отображением x -> x/a + 1/2 (mod 1). Эта связь подсказывает способ построения банахова пространства, на котором переходный оператор цепи с сокращенной жизнью обладает свойствами компактности, необходимыми для применения стандартного подхода типа Перрона—Фробениуса. Сложность нахождения такого пространства вызвана дискретностью инноваций.

Видео

Аннотация: Широко известно, что СДУ dX_t = b(X_t)dt + dW_t может иметь уникальное решение даже если соответствующее ОДУ dX_t = b(X_t)dt без шума либо не имеет решений, либо имеет бесконечно большое их количество. В таких случаях говорят о регуляризации шумом. Хотя это явление достаточно хорошо изучено в броуновском случае, гораздо меньше о нём известно в не марковских (например, дробное броуновское движение) или бесконечномерных случаях (например, пространственно-временной белый шум). Это происходит не потому, что регуляризация шумом уникальна для броуновского случая, а скорее потому, что у нас не хватает инструментов для исследования этой проблемы в других постановках. Речь будет идти о новой технике, stochastic sewing, и её новейших модификациях, оказавшейся эффективной при решении этой проблемы в не броуновской постановке.

Видео, Слайды