Курс «Network Science», літо 2019

Курс лекцій є коротким вступом до науки про складні мережі – напрямку досліджень, що  став особливо актуальним у зв’язку із можливістю зберігання та аналізу великих масивів інформації. Формалізм складних мереж використовується для опису складних систем взаємодіючих агентів, ставлячи у відповідність кожному із агентів вершину, а кожній із взаємодій – ребро. На сьогодні в мережевому формалізмі прийнято описувати взаємодії, що змінюються з часом, стохастичні взаємодії, взаємодії, що виникають на декількох рівнях і не вбудовані в евклідовий простір. У наших лекціях основні поняття і методи науки про складні мережі будуть проілюстровані на прикладах реальних мереж. Зокрема, будуть розглянуті соціальні, транспортні мережі, мережі зв’язку, співавторства та ін. У серії семінарів та практичних занять слухачі курсу матимуть змогу набути навичок у аналізі складних мереж різної природи.

Загальна тривалість курсу – 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 червня

Зарахування на курс

Зарахування на курс відбувається на конкурсній основі. Апліканти заповнюють реєстраційну форму: https://goo.gl/forms/5ulG7qo4gGcS3wO92.

При відборі учасників береться до уваги персональна мотивація, попередній досвід в аналітиці даних (Data Science). Кінцевий термін прийому заявок на курс — 25 квітня (включно). Оголошення результатів відбору — до 30 квітня.

Увага! Організатори залишають за собою право закрити реєстрацію на курс раніше в разі наявності достатньої кількості заявок для заповнення вакантних місць в класі. У разі необхідності організатори також можуть попросити провести онлайн співбесіду з кандидатами на участь задля уточнення питань реєстраційної форми, а також перевірки рівня необхідних знань.

Вартість навчання

Загальна вартість курсу «Network Science» становить 15 000 грн. Ми пропонуємо знижку 40% при реєстрації до 15 квітня (у такому випадку вартість курсу – 9000 грн).

Реквізити для оплати учасникам будуть надані через електронну пошту. В разі не проведення оплати організатори лишають за собою право скасувати реєстрацію учасника та звільнити місце для іншого кандидата. В разі виникнення фінансових питань, просимо звертатися якомога швидше (контактна інформація наведена нижче).

Сертифікати

По завершенню курсу учасники в разі отримання позитивної оцінки (виконання мінімум 60% завдань) отримають сертифікат учасника курсу. Сертифікат учасника може бути використаний для зарахування навчальний кредитів за аналогічний курс в університетах в разі наявності такої можливості.

Викладачі

Курс проводитимуть викладачі Інституту фізики конденсованих систем:

Юрій Головач, Мар’яна Красницька, Олеся Мриглод, Василь Пальчиков, Петро Сарканич

Контактна інформація

E-mail: [email protected]
Facebook: www.facebook.com/ucucsds/