Управление в сетевых структурах

Преподаватели: 
Маркович Н. М. (ИПУ РАН, Лаборатория 38)
Программа курса: 

Перечень контрольных вопросов

№

п/п

Разделы и темы лекционных занятий

Содержание

Осенний семестр

1

Многоагентные системы с информационными связями: базовые понятия и модели (протоколы), условия достижения консенсуса. Математические основы МАС: локализация собственных значений лапласовских матриц.

Основные аспекты многоагентных систем. Области применений МАС с информационными связями. Понятия консенсуса и согласования характеристик для различных моделей. Задачи консенсуса и проблемы согласования характеристик в МАС. Базовые протоколы для непрерывных и дискретных моделей. 

2

Условия достижимости консенсуса в базовой дискретной модели; неотрицательные матрицы; цепи Маркова. Консенсус в базовой дифференциальной модели. Алгебраические свойства орграфа влияний.

Необходимые и достаточные условия достижения консенсуса. О собственном проекторе лапласовской матрицы и ее роли в согласовании характеристик.   Неотрицательные матрицы дискретных моделей. Связь между протоколами МАС и неоднородными и однородными цепями Маркова. 

3

Модели консенсуса второго порядка. 

МАС второго порядка с протоколами достижения консенсуса. Условия достижения консенсуса. Модели Рена-Эткинс. Действительность спектра в МАС второго порядка - достаточное условие при простоте нулевого собственного значения.  

4

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

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

5

Модели МАС с переменной структурой (с переключающейся топологией).

МАС с переменной структурой первого порядка. Дискретные и непрерывные модели с переменной структурой. Условия сходимости для системы с переменной структурой. Связь между дискретными моделями первого порядка и неоднородными цепями Маркова

6

Модели МАС с несвязным орграфом коммуникаций.

МАС с орграфом влияний, не содержащим остовного исходящего дерева. Протоколы регуляризацией для дискретных и непрерывных моделей. Методы ортогональной проекции и фоновых связей. О связи между регуляризацией в МАС и задачей PageRank. Имеют ли негативные последствия превентивные регуляризации? 

7

Многоагентные системы с запаздыванием.

Основные протоколы с временной задержкой. Условия консенсуса и согласования характеристик. Модели с двойным интегратором.

8

Определения и базовые свойства классов распределений с тяжелыми хвостами.

 Введение: определения и базовые свойства классов распределений с тяжелыми хвостами. Классы распределений с тяжелыми хвостами.  Оценивание хвостового индекса непараметрическими методами. Методы оценивания числа наибольших порядковых статистик в оценке Хилла. Доказательство оценки Хилла методом максимума правдоподобия. Теоретические свойства оценки Хилла: состоятельность и асимптотическая нормальность. Введение в метод бутстреп для оценки числа наибольших порядковых статистик в оценке Хилла.

9

Грубые методы распознавания тяжелых хвостов и числа первых конечных моментов распределения.

Оценивание хвостового индекса, функции среднего превышения уровня, отношения максимума к сумме, графиков квантиль-квантиль.

10

Распознавание зависимостей в одномерных и двумерных данных

Условия перемешивания, автокорреляционная функция, тесты портмоне для одномерных данных. Для двумерных данных классические меры зависимости Кендалла и Спирмена, а также более новые - функция Пикандса и копулы. 

11

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

 Характеристики влиятельности узлов и их распределения с тяжелыми хвостами. Эволюция случайных сетей: предпочтительное и кластерное присоединения и соответствующие распределения входящих и выходящих связей узлов.

 

Весенний семестр

1

Введение в проблематику социальных сетей.

Базовые понятия, способы представления социальных сетей, структурные характеристики социальных сетей и экспериментальные наблюдения.

2

Кластеризация и сообщества в социальных сетях, эхо-камеры.

Понятие сообществ в социальных сетях, модулярность сети, методы кластеризации, понятие информационных сообществ, эхо-камеры, примеры.

3

Меры центральности в социальных сетях.

Определения различных мер центральности. Примеры: центральность по степени, центральность по собственному вектору, PageRank. Подходы к выбору мер центральности.

4

Модели случайных графов. Граф Эрдеша-Реньи.

Описание модели. Вывод основных свойств (распределение степеней вершин, кластеризация, размер гигантской компоненты).

5

 Граф Уоттса-Строгатца, граф Барабаши-Альберт.

Описание моделей, основные свойства (без вывода).

6

Процессы на сетях. Эпидемиологические модели (SIR-модель).

Описание SIR-модели, анализ поведения решений, возможные модификации.

7

Методы сбора и анализа социальных сетей. Пример эмпирического анализа фрагмента социальной сети ВКонтакте.

 Основные методы и подходы для сбора и анализа данных онлайновых социальных сетей. Анализ темпоральных сетей. Коррелированность сетей и гипотеза о независимости наблюдений. Пример анализа фрагмента социальной сети ВКонтакте.

8

 Модели социального влияния. Модель ДеГроота.

История модели ДеГроота. Описание модели, основные свойства. Эмпирические подтверждения.

9

Проблема Абельсона. Поляризация мнений в обществе. Модели ограниченного доверия и репульсивного влияния.

Проблема Абельсона: отсутствие консенсуса в социальных системах. Понятие поляризации мнений, методы измерения поляризации, эмпирические примеры поляризации взглядов. Модели ограниченного доверия и репульсивного влияния как способ объяснения отсутствия консенсуса и поляризации мнений.

10

Модели аргументных взаимодействий.

Понятие когнитивной структуры “кортеж аргументов - мнение.” Простейшая модель аргументных взаимодействий. Объяснения поляризации мнений без использования механизма репульсивного влияния.

11

SCARDO-модель. Построение приближения среднего поля.

Описание SCARDO-модели, мотивировки ее создания. Понятия “азбука мнений” и “таблица переходов”. Гибкость модели, вопросы калибровки. Приближение среднего поля, построение фазовых портретов.

12

Эмпирические исследования влияния в социальных сетях.

Обзор эмпирических исследований механизмов социального влияния.  

13

Модели и методы оценки информационного влияния в социальных сетях.

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

14

. Модели совместной динамики мнений и действий в социальных сетях.

Компоненты внутренней структуры индивида, понятие «мнение» и «действие» в социальных сетях. Описание моделей совместной динамики мнений и действий. Идентификация мнений и действий в онлайновых социальных сетях. Пример анализа факторов, действующих на мнения и действия пользователей онлайновых социальных сетей на примере ВКонтакте.

15

Модели информационного управления в социальных сетях.

Классификация задач управления. Способы информационного управления. Модели информационного влияния, управления и противоборства. Постановка и решение задачи информационного управления на примере модели Де Гроота. 

 

Перечень контрольных вопросов

(Часть 1. Теория многоагентных систем)

1.        Перечислить основные области применений многоагентных систем с информационными связями.

2.        Привести условия сходимости базовой дискретной модели консенсуса и охарактеризовать такую модель с точки зрения однородных цепей Маркова.

3.        Вывести выражение для базовой непрерывной модели первого порядка и представить такой протокол с помощью модели Де-Гроота.

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

5.        Связать спектр Лапласовской матрицы с помощью спектра стохастической матрицы и привести область локализации для системы с пятью агентами и невзвешенным орграфом связей. 

6.        Описать протокол консенсуса второго порядка.

7.        Описать протокол сходимости к заданной конфигурации для линейного протокола.

8.        Вывести выражение для протокола второго порядка с двумя лидерами.

9.        Привести нелинейный протокол второго порядка для поворота группы агентов. 

10.     Описать некоторые модели достижения консенсуса при несвязном орграфе коммуникаций. 

11.     О достижении консенсуса для МАС второго порядка с переменной структурой.

12.     Описать дискретные модели первого порядка с переключающейся топологией с помощью неоднородных цепей Маркова.

13.     Описать протокол с запаздыванием первого и второго порядка.

14.     Вывести выражение для асимптотического значения согласованных характеристик для модели с запаздыванием.

15.     Вывести выражение для критического значения запаздывания для модели первого порядка с помощью критерия Я. Цыпкина.

16.     Связать проблему «Page-Rank» с протоколами регуляризаций.

17.     Описать непрерывную модель достижения консенсуса с переключающейся топологией.

18.     Докажите, что протокол усредненного консенсуса всегда описывается сбалансированным орграфом связей.

 

(Часть 2. Методы анализа экстремальных событий)

             1.      Распределения с тяжелыми хвостами: определения, классы таких распределений (с регулярно меняющимися хвостами,                               субэкспоненциальные, с супертяжелыми хвостами), примеры, свойства.

             2.      Хвостовой индекс: его определение, роль и методы оценивания. Вывод оценки Хилла методом максимума правдоподобия.

             3.      Методы оценивания числа наибольших статистик как параметра в оценках хвостового индекса: график Хилла, бутстреп-метод.

             4.      Грубые методы распознавания тяжелых хвостов в статистических данных.

             5.      Определение независимых случайных величин. Методы распознавания зависимостей в одномерных данных (временных рядах):               корреляции, ковариации, автокорреляционная функция и ее оценка, интервал Бартлетта для автокорреляционной функции, тесты-                       портмоне Ljung-Box и Runde.

             6.      Определение зависимости временного ряда на больших шагах (LRD) и методы ее тестирования с помощью параметра Херста                   (Hurst).

             7.      Детекция зависимости между двумя случайными величинами. Определение функции Пикандса и ее оценивание.

             8.      Меры влиятельности узлов случайной сети.

             9.      Типы присоединения узлов и ребер к случайной сети в ходе ее эволюции.

 

(Часть 3. Социальные сети: моделирование и управление)

1.        Дайте определение социальной сети, опишите способы представления социальных графов.

2.        Перечислите основные структурные свойства социальных сетей.

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

4.        Сформулируйте структурные меры центральности (не менее трех). Опишите основные подходы к выбору подходящей меры центральности.

5.        Сформулируйте определение графа Эрдеша-Реньи, выведите основные свойства (распределение степеней вершин, кластеризация, размер гигантской компоненты связности).

6.        Опишите модели Уоттса-Строгатца, Барабаши-Альберт, приведите их основные свойства (без вывода).

7.        Опишите модель ДеГроота и свойства этой модели.

8.        Сформулируйте проблему Абельсона.

9.        Сформулируйте модели Деффуанта и Хегсельмана-Краузе. Опишите их феноменологию и мотивировки разработки.

10.     Дайте определение поляризации общественного мнения, приведите и опишите метрики поляризации.

11.     Опишите модель Альтафини (в том числе феноменологию и мотивировки разработки).

12.     Опишите модель Мааса-Флаше аргументных взаимодействий (в том числе феноменология и мотивировки разработки).

13.     Опишите SCARDO модель, понятия азбуки мнений и таблицы переходов.

14.     Выведите приближение среднего поля в SCARDO модели.

15.     Дайте определение социальной власти, объясните, как ее измерить при помощи модели Френча-ДеГроота.

16.     Определите понятие «информационное влияние». Перечислите и опишите подходы к оценке влияния и влиятельности в социальных сетях

17.     Опишите подходы к идентификации мнений и действий в онлайновых социальных сетях.

18.     Приведите классификацию задач управления в сетевых структурах. Опишите возможные механизмы информационного управления.

Список литературы: 

Основная литература

(Часть 1. Теория многоагентных систем)

  1. Wooldridge M. An introduction to multiagent systems. – John Wiley & Sons, 2009.
  2. Olfati-Saber R., Fax J. A., Murray R. M. Consensus and cooperation in networked multi-agent systems //Proceedings of the IEEE. – 2007. – Т. 95. – №. 1. – С. 215-233.
  3. Jadbabaie A., Lin J., Morse A. S. Coordination of groups of mobile autonomous agents using nearest neighbor rules //IEEE Transactions on automatic control. – 2003. – Т. 48. – №. 6. – С. 988-1001.
  4. Mesbahi M., Egerstedt M. Graph theoretic methods in multiagent networks. – Princeton University Press, 2010.
  5. Ren W., Cao Y. Distributed coordination of multi-agent networks: emergent problems, models, and issues. – Springer Science & Business Media, 2010.
  6. Wu C.W. Synchronization in Complex Networks of Nonlinear Dynamical Systems. Singapore: World Scientific, 2007.
  7. Shamma J.S. (ed.). Cooperative Control of Distributed Multi-agent Systems. Chichester, UK: Wiley, 2007.
  8. Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Социальные сети: модели информационного влияния, управления и противоборства. – 2010.
  9. Чеботарев П. Ю., Агаев Р. П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов //Автоматика и телемеханика. – 2009. – №. 3. – С. 136–151.
  10. Агаев Р. П., Чеботарев П. Ю. Модели латентного консенсуса //Автоматика и телемеханика. – 2017. – №. 1. – С. 106-120.
  11. Langville A. N., Meyer C. D. Google's PageRank and beyond: The science of search engine rankings. – Princeton University Press, 2011.
  12. Wei Ren, Ella Atkins. Second-order Consensus Protocols in Multiple Vehicle Systems with Local Interactions
  13. Veerman J. J. P. et al. Flocks and formations //Journal of Statistical Physics. – 2005. – Т. 121. – №. 5-6. – С. 901-936.
  14. Jack K. Hale Sjoerd M. Verduyn Lunel. Introduction to Functional Differential Equations.1993. Springer Science+Business Media, LLC

(Часть 2. Методы анализа экстремальных событий)

  1. Чистяков В. П. Курс теории вероятностей
  2. Ширяев А. Н. Вероятность 
  3. Гнеденко Б. В. Курс теории вероятностей
  4. Markovich N.M. Nonparametric Analysis of Univariate Heavy-Tailed data: Research and Practice, Wiley 2007

(Часть 3. Социальные сети: моделирование и управление)

  1. Newman M. Networks. – Oxford university press, 2018.
  2. DeGroot, M. H. (1974). Reaching a consensus. Journal of the American Statistical association, 69(345), 118-121.
  3. Flache, A., Mäs, M., Feliciani, T., Chattoe-Brown, E., Deffuant, G., Huet, S., & Lorenz, J. (2017). Models of social influence: Towards the next frontiers. Journal of Artificial Societies and Social Simulation, 20(4).
  4. Mäs, M., & Flache, A. (2013). Differentiation without distancing. Explaining bi-polarization of opinions without negative influence. PloS one, 8(11), e74516.
  5. Altafini, C. (2012). Consensus problems on networks with antagonistic interactions. IEEE transactions on automatic control, 58(4), 935-946.
  6. Kozitsin, I. V. (2023). Opinion dynamics of online social network users: a micro-level analysis. The Journal of Mathematical Sociology, 47(1), 1-41.
  7. Kozitsin, I. V. (2022). A general framework to link theory and empirics in opinion formation models. Scientific reports, 12(1), 1-18.
  8. Jackson M. Social and Economic Networks. Princeton: Princeton University Press, 2008
  9. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. 3-е изд., перераб. и дополн. М.: МЦНМО, 2018. – 224 с.
  10. Губанов Д. А., Новиков Д. А. Модели совместной динамики мнений и действий в онлайновых социальных сетях (в трех частях). Проблемы управления, 2023.

Дополнительная литература:

(Часть 1. Теория многоагентных систем)

  1. Гантмахер Ф. Теория матриц. – Litres, 2018.
  2. Кемени Д. Снелл Дж. Конечные цепи Маркова. – 1970.
  3. Эльсгольц, Лев Эрнестович. Дифференциальные уравнения и вариационное исчисление. Vol. 3. наука, 1969.
  4. Барабанов И. Н. и др. Динамические модели информационного управления в социальных сетях //Автоматика и телемеханика. – 2010. – №. 11. – С. 172-182.
  5. G. Lafferriere, A. Williams, J. Caughman, and J. J. P. Veerman. Decentralized control of vehicle formations. System and Control Letters, 54: 899–910, 2005.
  6. Li, H., Liao, X., Huang, T., Wang, Y., Han, Q., & Dong, T. (2014). Algebraic criteria for second-order global consensus in multi-agent networks with intrinsic nonlinear dynamics and directed topologies. Information Sciences, 259, 25-35.
  7. Ren W., Cao Y. Convergence of sampled-data consensus algorithms for double-integrator dynamics //2008 47th IEEE Conference on Decision and Control. – IEEE, 2008. – С. 3965-3970.
  8. Агаев Р. П., Чеботарев П. Ю. Лапласовские спектры орграфов и их приложения //Автоматика и телемеханика. – 2005. – №. 5. – С. 47-62.
  9. Gu K., Chen J., Kharitonov V. L. Stability of time-delay systems. – Springer Science & Business Media, 2003.

 

(Часть 2. Методы анализа экстремальных событий)

  1.             Newman, M. E. J. Networks: an introduction.  Oxford University Press: Oxford, New York, 2010
  2. van der Hofstad, R.  Random Graphs and Complex Networks. Vol. 1. Cambridge Series in Statistical and Probabilistic Mathematics, 2017

 

(Часть 3. Социальные сети: моделирование и управление)

  1. Бреер В. В., Новиков Д. А., Рогаткин А. Д. Управление толпой: математические модели порогового коллективного поведения. М.: Ленанд, 2016.
  2. Губанов Д. А. Влияние в социальных сетях: варианты формализации // Управление большими системами. 2020. № 85. С. 51–71.
  3. Губанов Д. А., Петров И. В. Информационные сообщества в социальных сетевых структурах (в трех частях). Проблемы управления, 2021.
  4. Губанов Д. А., Петров И. В., Чхартишвили А. Г. Многомерная модель динамики мнений в социальных сетях: индексы поляризации // Проблемы управления. 2020. № 3. С. 26–33.
  5. Новиков Д. А. Управление, деятельность, личность. М.: ИПУ РАН, 2020. – 80 с.
  6. Новиков Д. А. Модели динамики психических и поведенческих компонент деятельности в коллективном принятии решений // Управление большими системами. 2020. Вып. 85. С. 206–237.

 

Информационные ресурсы

Периодическая литература по теории управления:

1.         Журнал «Автоматика и телемеханика»

2.         Журнал «Проблемы управления»

3.         Управление большими системами.

4.         Linear Algebra and its Application.

5.         IEEE Transactions on Control Systems Technology.

6.         IEEE Transactions on automatic control.

 

Перечень ресурсов информационно-телекоммуникационной сети "Интернет", необходимых для освоения дисциплины (модуля)

(Часть 1. Теория многоагентных систем)

  1. https://link.springer.com/content/pdf/10.1007/s10955-005-6999-9.pdf
  2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.700.8700&rep=re...
  3. http://www.et.byu.edu/~beard/papers/reprints/RenBeard05a.pdf.
  4. https://deepblue.lib.umich.edu/bitstream/handle/2027.42/56082/1147_ftp.p...

(Часть 2. методы анализа экстремальных событий)

       5. https://cloud.mail.ru/public/mRXU/QordTfAn6

       6. https://cloud.mail.ru/public/dvR6/NqmtFj4pj

       7. https://cloud.mail.ru/public/Qa72/YTQHf77Ps