Курс лекцій є коротким вступом до науки про складні мережі – напрямку досліджень, що став особливо актуальним у зв’язку із можливістю зберігання та аналізу великих масивів інформації. Формалізм складних мереж використовується для опису складних систем взаємодіючих агентів, ставлячи у відповідність кожному із агентів вершину, а кожній із взаємодій – ребро. На сьогодні в мережевому формалізмі прийнято описувати взаємодії, що змінюються з часом, стохастичні взаємодії, взаємодії, що виникають на декількох рівнях і не вбудовані в евклідовий простір. У наших лекціях основні поняття і методи науки про складні мережі будуть проілюстровані на прикладах реальних мереж. Зокрема, будуть розглянуті соціальні, транспортні мережі, мережі зв’язку, співавторства та ін. У серії семінарів та практичних занять слухачі курсу матимуть змогу набути навичок у аналізі складних мереж різної природи.
Загальна тривалість курсу – 20 занять.
Кількість ECTS – 5 кредитів.
Детальна структура курсу
1. Вступ. Складні системи і складні мережі.
Виникнення науки про складні системи. Характерні риси складних систем: самоорганізація, емерджентність, чутливість, степенева статистика, адаптивні взаємодії. Приклади складних систем. Універсальність і генераційні механізми степеневих розподілів. Наука про складні мережі як lingua franca науки про складні системи.2. Мережі і графи.
Теорія графів як розділ дискретної математики. Задача про сім мостів в Кеніґсберзі, історія науки про графи. Випадковий граф, повний граф, спрямовані/неспрямовані, зважені/незважені, багатосортні графи. Мережі реального світу. Основні характеристики мереж: ступінь вузла (середнє і розподіл за ступенем); відстані на мережі (найкоротший шлях і його розподіл); матриця суміжності; зв’язність, коефіцієнт кластерності.3. Моделі складних мереж.
Випадковий граф Ердоша-Рені. Коефіцієнт кластерності. Гігантська зв’язна компонента. Модель тісного світу Ваттса-Строгаца. Розподіл ступенів вузлів і середній ступінь вузла. Габи. Принцип переважного приєднання і модель Альберта-Боробаші. Випадковий граф із заданим розподілом ступенів вузлів. Конфігураційна модель. Коефіцієнт кластерності. Твірна функція для розподілу ступенів вузлів. Граф із степеневим розподілом ступенів вузлів. (поки як опційний блок, ПС)4. Стійкість мереж.
Перколяція (явище і його кількісний опис). Виникнення гігантської зв’язної компоненти (GCC) на мережі. Критерій Моллоя-Ріда. Стійкість мереж до випадкових збоїв і спрямованих атак. Каскадні збої на мережах.5. Спільноти на мережах.
Структура графів/мереж. Поняття спільноти (community), розбиття та інші означення. Класифікація алгоритмів виявлення спільнот. Функції якості поділу та концепція модулярності. Підходи до виявлення спільнот, що перекриваються. Динаміка мережевої структури та структури temporal networks. Приклади: інтерпретація community structure для реальних мереж та її роль. Найпростіші способи розбиття мереж на дві групи: алгоритм Кернігана-Ліна і його спектральне узагальнення.6. Поширення (spreading) на мережах.
Приклади явища поширення на мережах. Моделювання епідемій. Моделі SI, SIS, SIR. Кількісний аналіз явища поширення на мережах, поведінка на випадкових та безмасштабних мережах. Імунізація. Стратегії імунізації на мережах різного типу.7. Візуалізація складних мереж.
Різні аспекти даних – різні способи представлення мережі. Мережі на площині та у просторі. Карти знань та атласи науки. Огляд програмного забезпечення для візуалізації мереж.8. Мережі наративів.
Наратив як складна мережа: персонажі і зв’язки між ними. Основні мережеві характеристики: ступінь вузла, розподіл ступенів вузлів, коефіцієнт кластерності, центральність близькості, центральність посередництва, асортативність. Асортативність за категоріями. Порівняння мереж наративів із випадковими графами і між собою, класифікація. Пошук спільнот. Стійкість мереж наративів до усунення вузлів.9. Мережі віртуального світу.
Цифрова соціальна лабораторія. Кількісне тестування соціальних гіпотез. Багатошарові мережі. Темпоральні мережі. Інтерпретації класичних мережевих понять для нових узагальнень.10. Моделювання транспортних мереж.
Просторові (spatial) мережі. Узагальнення поняття вимірності, фрактали. Фрактальні вимірності транспортних мереж та їх інтерпретація. Різні зображення (“простори”) для просторової мережі. Стійкість.11. Мережі мобільного зв’язку.
Мережа мобільного зв’язку як джерело для дослідження суспільних явищ. Питання приватності та чутливості даних. Шуми та способи їх усунення. Мережа спілкування та переміщення абонентів мобільного зв’язку.12. Впорядкування на складних мережах.
Впорядкування в системі багатьох агентів. Вступ до теорії фазових переходів. Феноменологічний та мікроскопічний підходи. Статистична сума і вільна енергія. Спінові моделі в статистичній фізиці (моделі Ізінга та Поттса) та їх застосування для опису соціальних мереж. Методи статистичної фізики: теорія Ландау, метод середнього поля, метод перевалу. Теорія Ландау впорядкування на безмасштабній мережі. Досліджень спінових систем на різних типах графів (повний граф, відпалена безмасштабна мережа) із використанням низки методів статистичної фізики.Теми для семінарських, практичних занять та самостійної роботи
Кожен студент курсу вибере реальну систему, що складається із багатьох частин (агентів) різної природи. Для вибраної системи треба виконати такі завдання: 1. Зображення структури складної системи у вигляді складної мережі. Обчислення основних характеристик (індексів) мережі (N, M, <k>, k_max, <l>, l_max, GCC, C, centralities) та порівняння їх із відповідними характеристиками класичного випадкового графу Ердоша-Реньї. 2. Знаходжння розподілів індексів P(k), P(l), P(C) та їх апроксимація у вигляді показникової та степеневої функцій. Оцінка якості апроксимації. 3, 4. Дослідження: (i) кореляцій між різними індексами (обчислення узагальнених асортативностей, знаходження залежностей С(k), Centrality(k), etc); (ii) виникнення структур (аналіз спільнот); (iii) процесів (стійкість до випадкових і спрямованих атак). 5. Захист виконаних робіт (з візуалізацією мереж).Вимоги до попередніх знань учасників курсу
– математичний аналіз; – лінійна алгебра; – програмування; – теорія ймовірності. Учасники курсу повинні мати власний комп’ютер (ноутбук) з собою.Дати проведення курсу
Навчання на курсі розпочинається 6 травня (понеділок). Заняття будуть проводитися у будні з 18:00 до 21:00, у суботи з 14:00 в Українському Католицькому Університеті. Дати курсу:- 6 травня
- 15 травня
- 22 травня
- 25 травня
- 29 травня
- 5 червня
- 8 червня
- 10 червня
- 20 червня
- 22 червня
- 24 червня
- 26 червня