Формування мереж: Як переважне притягнення будує світ масштабно-незбагненних мереж

Два способи розширення мережі

Класичний випадковий граф, формалізований Палем Ердешем та Альфредом Реньї в 1959 році, з’єднує фіксований набір вузлів із ребрами, обраними рівномірно випадковим чином. Його розподіл ступенів є вузьким Посієчним горбком навколо середнього значення — майже кожен вузол має приблизно однакову кількість зв’язків, і хаби просто не з’являються. Реальні мережі нічого спільного з цим. Аеропорти, графіки цитування, Всесвіт Веб та соціальні платформи мають невелику кількість вузлів із величезною кількістю зв’язків і величезну кількість вузлів із дуже малою кількістю. Альберт-Ласло Барбаші та Рекка Альберт показали у 1999 році, що відсутній інгредієнт не був випадковістю, а зростанням у поєднанні з переважним притяганням.

Правило: з'єднуйтесь із добре зв’язаними вузлами

Модель Барабаші-Альберта (BA) починається зі невеликого зв’язаного ядра вузлів, яке поступово розширюється шляхом додавання нових вузлів. При кожному новому вузлі створюється m нових зв’язків, і — це основний механізм — ймовірність того, що новий зв’язок утворюється з існуючим вузлом i, пропорційна поточному ступеню цього вузла k_i, а не випадково:

P(зв’язатися з вузлом i) = k_i / Σ_j k_j При кожному новому вузлі створюється m зв’язків за цим правилом → вузли, які вже мають багато зв’язків, непропорційно ймовірно отримають наступний це буквальний процес «багатіють», де багаті стають багатшими Це моделює щоденну реальність: нову вебсторінку легше знайти та вона більш імовірно посилається на сторінку, яка вже широко посилається на неї; новий науковий документ більш імовірно цитує документ, який уже відомий, саме тому, що дослідники спочатку шукають літературу саме через ці документи; новій соціальній мережі більш ймовірно слідкувати за обліковими записами з великою кількістю підписників, оскільки видимість сама по собі зростає зі ступенем. Першопочатковий переважний вплив накопичується — вузли, які приєднуються першими, мають більше часу для накопичення зв’язків, що пояснює те, чому дуже ранні центри в мережі, яка росте, схильні залишатися найбільшими.

P(attach to node i) = k_i / Σ_j k_j

each new node adds m edges chosen by this rule
→ nodes that already have many links are disproportionately
  likely to gain the next one — a literal rich-get-richer process

Потужність закону, а не колоскова крива

Наслідок цього простого правила – розподіл ступенів, який слідує за законом потужності, P(k) ~ k^-γ, де оригінальна модель BA дає показник γ = 3. Розподіл за законом потужності не має характерного масштабу: немає «типового» ступеня вузла, як у популяції людського зросту, що є точною причиною того, що їх називають мережами без масштабу. Практично це означає, що невелика кількість хабів – іноді лише частка відсотка всіх вузлів – відповідає за значну частину усіх зв’язків у мережі, патерн, який підтверджено емпірично в гіперпосиланнях веб-сайтів, картах маршрутів авіакомпаній, мережах взаємодії білків та схемах цитування наукових робіт.

Стійкий до випадкових збоїв, вразливий до цілеспрямованої атаки

Ця структура виробляє знамениту та доволі неочевидну властивість стійкості, вивчену Рекою Альберт, Хавонгом Чонгом та Барабаші у 2000 році. Видаляючи випадково вузли з мережі типу scale-free, вона майже не помічає цього – тому що переважна більшість вузлів мають низький ступінь зв’язності, випадкове видалення дуже малоймовірно зачепить хетро (hub), і мережа залишається підключеною в широкому діапазоні показників відмов. Але якщо навмисно видалити невелику кількість вузлів з найвищим ступенем зв’язності, мережа розпадається після лише кількох видалень, оскільки ці вузли несели непропорційний обсяг усіх шляхів через мережу. Ця асиметрія – стійкість до випадкових аварій, вразливість до цілеспрямованої атаки – має пряме значення для стійкості інфраструктури Інтернету, контролю епідемій (вакцинація хетро першою набагато ефективніша, ніж вакцинація випадково) та кібербезпеки.

Поза базовою моделлю

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

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Network Formation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.