🕸️ Формування мережі — Преференційне приєднання

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

Симуляція починається з невеликого кільця з п'яти з'єднаних вузлів і автоматично додає нові вузли зі швидкістю, заданою повзунком «Швидкість зростання». Використовуйте повзунок «m», щоб керувати кількістю зв'язків, які формує кожен новий вузол — вищі значення швидше ущільнюють мережу. Вузли з оранжевими кільцями — поточні хаби. Призупиніть зростання, щоб оглянути структуру чи гістограму, і скиньте, щоб почати заново з новим початковим станом.

Оскільки ймовірність приєднання пропорційна ступеню, вузли, яким пощастило рано отримати перевагу у зв'язках, з більшою ймовірністю отримають ще більше зв'язків пізніше, посилюючи свою перевагу з часом. Цей цикл позитивного зворотного зв'язку, математично ідентичний процесу Юла чи урні Пойї, означає, що найперші й найудачливіші вузли, як правило, стають найбільшими хабами, хоча кожен вузол підпорядковувався однаковому ймовірнісному правилу. Малі ранні відмінності посилюються, а не усереднюються.

Модель запропонували 1999 року Альберт-Ласло Барабаші та Река Альберт у статті «Emergence of Scaling in Random Networks» (Science, том 286). Вони відобразили частину гіперпосилальної структури Всесвітньої павутини і виявили, що розподіл ступенів підпорядковується степеневому закону, чого не могла пояснити класична теорія випадкових графів Ердеша-Реньї. Вони запропонували, що двох складників — постійного зростання мережі та преференційного приєднання — разом достатньо для утворення безмасштабної структури, результат, що започаткував сучасну галузь мережевої науки.

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

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

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

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