Математика
📅 22 червня 2026 ⏱ ≈ 8 хв читання · Останнє оновлення: 5 липня 2026 р.

Мережева наука — математика зв'язаних систем

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Теорія графів, мережі малого світу та безмасштабні мережі, кластеризація, виявлення спільнот і алгоритм PageRank.

Коротко: Мережева наука розглядає інтернет, соціальні зв'язки та біологічні системи як графи з вузлів і ребер, показуючи, що більшість реальних мереж не є ні випадковими, ні регулярними. Натомість вони мають властивості «малого світу» та безмасштабну структуру, де кілька високопов'язаних вузлів визначають стійкість мережі та швидкість поширення в ній.

1. Графи: вершини, ребра та властивості

Граф G = (V, E) складається з вершин (вузлів) V та ребер E, що їх з'єднують. Ця проста абстракція надзвичайно потужна: будь-яку систему попарних відносин можна подати у вигляді графа.

Графи бувають різних видів. Орієнтовані графи мають ребра з визначеним напрямком — мережі електронної пошти (відправник → отримувач) орієнтовані, тоді як мережі дружби зазвичай неорієнтовані. Зважені графи присвоюють числове значення кожному ребру (відстані доріг, сила взаємодії), тоді як незважені графи вважають усі зв'язки рівноцінними. Дводольні графи мають дві окремі множини вузлів, а ребра йдуть лише між множинами — класичний приклад: актори, пов'язані з фільмами.

Ключові структурні властивості:

Історичне походження теорії графів — задача про кенігсберзькі мости. У 1736 році Ейлер запитав, чи можна пройти Кенігсбергом, перетнувши всі 7 мостів рівно один раз. Він довів, що це неможливо — замкнений маршрут (ейлерів цикл) існує лише тоді, коли кожен вузол має парний ступінь. Це абстрактне спостереження заклало основи всієї теорії графів.

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

Масштаб реальних мереж: інтернет налічує приблизно 5 мільярдів вузлів (пристроїв). Попри такий величезний розмір, середня довжина шляху між двома випадковими веб-сторінками становить близько 19 кліків — значно менше, ніж очікує більшість людей. Це і є феномен малого світу в дії.

2. Мережі малого світу та безмасштабні мережі

У 1967 році знаменитий експеримент Стенлі Мілгрема попросив учасників передати листа цільовій особі в Бостоні, використовуючи лише особисті знайомства. Листи діставалися адресата приблизно за 6 кроків — звідси й вислів «шість рукостискань». Сучасний аналіз соціального графа Facebook (2016) виявив у середньому лише 3,57 ступеня розділення серед 1,6 мільярда користувачів.

Модель малого світу Воттса-Строгаца (1998) пояснює це математично. Почніть з регулярної решітки, де кожен вузол з'єднаний зі своїми k найближчими сусідами, а потім випадково перез'єднайте кожне ребро з імовірністю p. Навіть для дуже малого p (близько 1%) кілька довгих «коротких шляхів» різко скорочують середню довжину шляху, зберігаючи при цьому високу локальну кластеризацію початкової решітки — саме той «малий світ», якого шукають.

Однак більшість реальних мереж демонструють ще разючішу властивість: безмасштабні розподіли ступенів. Замість дзвоноподібного розподілу, де більшість вузлів мають подібні ступені, реальні мережі мають важкий хвіст — кілька «хабів» із набагато більшою кількістю зв'язків, ніж у середньому. Розподіл ступенів підпорядковується степеневому закону:

Безмасштабний розподіл ступенів: P(k) ~ k-γ (зазвичай γ ∈ [2, 3]) Воттс-Строгац: налаштування p від 0 (решітка) до 1 (випадковий граф) p ≈ 0.01 дає: короткий середній шлях + високу кластеризацію → режим «малого світу» Імовірність преференційного приєднання: Π(kᵢ) = kᵢ / Σⱼ kⱼ (вузол i приваблює нові зв'язки пропорційно до свого ступеня)

Модель преференційного приєднання Барабаші-Альберт природно генерує безмасштабні мережі: нові вузли, що приєднуються до мережі, з більшою ймовірністю зв'язуються з уже добре пов'язаними вузлами — «багатий стає багатшим». Це відображає те, як насправді ростуть веб, мережі цитувань і соціальні платформи.

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

3. Виявлення спільнот і кластеризація

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

Коефіцієнт кластеризації C(v) кількісно оцінює локальну згуртованість: це частка сусідів вузла, які самі пов'язані між собою. Якщо Аліса знає Боба і Керол, а Боб і Керол також дружать, локальний кластер Аліси тісно згуртований. Глобальний коефіцієнт кластеризації усереднює це значення по всіх вузлах. Реальні соціальні мережі мають коефіцієнти кластеризації на порядки вищі, ніж випадкові графи такого ж розміру та густини.

Тріадичне замикання рухає цю кластеризацію: якщо A знає B, а B знає C, існує сильна тенденція до того, що A і C познайомляться. Цей простий принцип у поєднанні з преференційним приєднанням пояснює значну частину еволюції соціальних мереж.

Формально виявлення спільнот шукає розбиття вузлів, яке максимізує кількість ребер усередині груп і мінімізує кількість ребер між групами. Стандартна міра якості — модулярність Q: частка ребер усередині спільнот мінус очікувана частка, якби ребра розміщувалися випадково.

Два провідні алгоритми:

Обчислювальна складність: виявлення спільнот у загальному випадку є NP-складною задачею. Алгоритм Лувена досягає майже оптимальної модулярності за час O(n log n), що робить його стандартним інструментом для великих мереж із мільйонами вузлів. Алгоритм зазвичай збігається за кілька проходів навіть на величезних графах.

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

4. PageRank, епідемії та каскади

У 1998 році Ларрі Пейдж і Сергій Брін представили PageRank як основу пошукової системи Google. Основна ідея: веб-сторінка важлива, якщо на неї посилаються інші важливі сторінки. Це рекурсивне визначення розв'язується шляхом знаходження стаціонарного розподілу випадкового блукання по графу вебу.

Формула PageRank: PR(A) = (1 - d)/N + d · ΣB→A PR(B) / L(B) d = коефіцієнт затухання (≈ 0.85) N = загальна кількість вузлів L(B) = кількість вихідних посилань із B Модель випадкового серфера: з імовірністю d перейти за посиланням, з імовірністю (1-d) перестрибнути на випадкову сторінку

Модель випадкового серфера дає інтуїтивне розуміння: уявіть користувача, який переходить за посиланнями з імовірністю d, але час від часу телепортується на випадкову сторінку з імовірністю (1-d). Частка часу, проведеного на кожній сторінці — стаціонарний розподіл — і є її PageRank. На практиці PageRank обчислюється ітеративно до збіжності або за допомогою методів розрідженого власного вектора.

Топологія мережі різко впливає на поширення епідемій. Модель SIR (Сприйнятливі → Інфіковані → Одужалі) на мережі показує, що хаби стають суперпоширювачами: патоген, потрапляючи в хаб, миттєво досягає багатьох його сусідів. Базове репродуктивне число R₀ на безмасштабній мережі залежить від співвідношення ⟨k²⟩/⟨k⟩ — оскільки хаби мають дуже високий k², епідемії можуть поширюватися навіть за дуже низької ймовірності передачі. Критично важливо, що вакцинація хабів (цільова імунізація) зупиняє епідемії значно ефективніше, ніж випадкова вакцинація.

Інформаційні каскади підпорядковуються пороговим моделям: вузол переймає поведінку, коли частка його сусідів, які вже це зробили, перевищує його особистий поріг. Прості порогові правила породжують складні колективні явища — вірусний контент, банківські паніки, політичні рухи та каскади технологічного впровадження підпорядковуються схожій динаміці. Топологія мережі визначає, чи каскад згасне, чи пошириться глобально.

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

Дослідіть мережеві симуляції

Візуалізуйте графові алгоритми, процеси поширення та формування мереж у реальному часі.

Дослідити мережеві симуляції →

Пов'язаний контент

Стаття Теорія ігор Стратегічна взаємодія та рівноваги Неша в багатоагентних системах Стаття Теорія інформації Ентропія та пропускна здатність каналу в системах зв'язку Категорія Мережі та теорія графів Графові алгоритми, задача комівояжера та процеси поширення

Часті запитання

Що таке моделі випадкових графів?

Моделі випадкових графів генерують мережі ймовірнісним способом для вивчення структурних властивостей. Модель Ердеша-Реньї G(n,p) створює n вузлів, де кожне ребро з'являється незалежно з імовірністю p — це дає розподіли ступенів Пуассона. Модель Барабаші-Альберт використовує преференційне приєднання — нові вузли з'єднуються з наявними пропорційно до їхнього ступеня — і дає степеневі розподіли ступенів, що відповідають реальним мережам. Модель Воттса-Строгаца інтерполює між регулярними решітками та випадковими графами, породжуючи мережі малого світу.

Що таке стійкість і вразливість мережі?

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

Що таке модель росту мережі Барабаші-Альберт?

Модель Барабаші-Альберт (BA) генерує безмасштабні мережі через два механізми: зростання (мережа безперервно отримує нові вузли) та преференційне приєднання (нові вузли з'єднуються з наявними з імовірністю, пропорційною їхньому поточному ступеню — «багатий стає багатшим»). Це породжує степеневий розподіл ступенів P(k) ~ k^(-γ) із γ=3, що відповідає багатьом реальним мережам, включно з вебом, цитуваннями та авіамаршрутами.

Що таке аналіз мережевих мотивів?

Мережеві мотиви — це невеликі підграфові патерни (зазвичай 3-4 вузли), які трапляються в реальних мережах значно частіше, ніж у випадкових мережах із такою самою послідовністю ступенів. Мілo та колеги (2002) виявили характерні мотиви в мережах транскрипційної регуляції, нейронних мережах, харчових ланцюгах і соціальних мережах. Прямі петлі зворотного зв'язку, патерни «бі-фан» та інші мотиви виконують специфічні обчислювальні функції в біологічних мережах і повторюються в різних типах систем.

Який зв'язок між мережевою наукою та епідеміологією?

Структура мережі критично визначає динаміку епідемії. У моделях SIR на неоднорідних мережах поріг епідемії залежить від ⟨k²⟩/⟨k⟩ — мережі з розбіжним другим моментом (безмасштабні) мають нульовий поріг, тобто будь-яка передавана хвороба може поширюватися. Хаби мережі стають суперпоширювачами. Стратегії втручання, спрямовані на хаби (відстеження контактів, вакцинація осіб із високим ступенем), значно ефективніші за випадкову вакцинацію. Реальні дані про епідемічні мережі надходять із відстеження контактів, даних про мобільність і соціальних мереж.

Що таке модель Воттса-Строгаца?

Модель Воттса-Строгаца генерує мережі малого світу, починаючи з регулярної кільцевої решітки (кожен вузол з'єднаний із k найближчими сусідами) і випадково перез'єднуючи кожне ребро з імовірністю p. При p=0: регулярна решітка (висока кластеризація, довгі шляхи). При p=1: випадковий граф (низька кластеризація, короткі шляхи). При проміжному p (0,01–0,1): режим малого світу (висока кластеризація ТА короткі шляхи), що відповідає спостережуваним соціальним, нейронним та інфраструктурним мережам.

Що таке спектральна теорія графів?

Спектральна теорія графів вивчає графи через власні значення та власні вектори графових матриць (матриця суміжності, матриця Лапласа). Друге за величиною найменше власне значення Лапласіана (алгебраїчна зв'язність, значення Фідлера) вимірює зв'язність графа — нуль означає незв'язність, більші значення означають більшу стійкість. Спектральна кластеризація використовує власні вектори Лапласіана для розбиття графів на спільноти. Графові нейронні мережі використовують спектральну структуру для завдань класифікації вузлів і графів.

Чим часові мережі відрізняються від статичних мереж?

Часові (змінні в часі) мережі змінюють топологію з часом — ребра з'являються і зникають. Контактні мережі в епідеміології за своєю природою часові (люди зустрічаються в певні моменти). Статичний аналіз мереж ігнорує часову складову, потенційно знаходячи шляхи, які ніколи не існували одночасно. Часово-впорядковані шляхи є підмножиною всіх шляхів у сукупній мережі. Аналіз часових мереж враховує причинність (причини передують наслідкам), нерівномірність (згруповані в часі контакти) і часо-шановану досяжність.

Що таке вбудовування мережі (network embedding)?

Вбудовування мережі (навчання представлень графа) відображає вузли або цілі графи у простори векторів низької розмірності, зберігаючи структурні властивості мережі. Node2Vec і DeepWalk використовують випадкові блукання для генерації послідовностей вузлів, а потім застосовують навчання у стилі word2vec. Графові нейронні мережі (GNN) навчають вбудовування через передавання повідомлень — кожен вузол агрегує інформацію від сусідів. Вбудовування дозволяють вирішувати задачі машинного навчання: передбачення зв'язків, класифікацію вузлів, класифікацію графів і рекомендаційні системи.

Який зв'язок між мережами та складними системами?

Мережева наука надає субстрат для складних систем — структуру, над якою розгортається динаміка. Каскадні збої в енергомережах, поширення інформації в соціальних мережах, синхронізовані коливання в мережах, зв'язаних за Курамото, та еволюційна динаміка в теоретико-ігрових графах — усе це критично залежить від топології мережі. Складні адаптивні системи — екосистеми, економіки, імунні системи — найкраще подавати як мережі, що еволюціонують, де структурні зміни впливають на динаміку за принципом зворотного зв'язку, породжуючи емерджентні явища, які неможливо передбачити лише на основі властивостей окремих вузлів.