Модель Барабаши Альберт БА алгоритм генерації випадкових безмасштабних мереж з використанням принципу переважного приєдн

Модель Барабаши-Альберт (БА) — алгоритм генерації випадкових безмасштабних мереж з використанням принципу переважного приєднання. Безмасштабні мережі широко зустрічаються як в природі (харчові ланцюжки), так і створені людиною — Інтернет, всесвітня павутина, мережі цитування, деякі соціальні мережі. Зазначені мережі є майже безмасштабними, однак, в них наявні декілька вузлів (їх звуть хабами) з надвисоким степенем у порівнянні з іншими вузлами мережі. Модель Барабаші-Альберт саме й намагається пояснити природу цих вузлів в реальних мережах. Алгоритм названий на честь дослідників ^[en] та ^[en] і є окремим випадком більш загальної моделі Прайса.

Концепції

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

зростання мережі
принцип переважного приєднання (ПП)

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

Принцип переважного приєднання полягає в тому, що чим більше зв'язків має вузол, тим більше ймовірність утворення нових зв'язків. Вузли з найбільшим ступенем мають більше можливостей забирати собі зв'язки, які додаються в мережу. Інтуїтивно, принцип переважного приєднання може бути зрозумілий, якщо ми думаємо в термінах соціальних мереж, які об'єднують людей. Тут зв'язок від А до B означає, що людина «знає» або «знайома» з людиною B. Сильно пов'язані вузли представлені відомими людьми з великою кількістю зв'язків. Коли новачок потрапляє в товариство, для нього/неї більш переважно зв'язатися з одним з відомих людей, ніж з відносно невідомих. Подібним чином у всесвітній мережі сторінки часто лінкуються з хабами, приміром, з добре відомими сайтами, як Гугл або Вікіпедія, на відміну від сайтів, які мало кому відомі. Якщо вибирати для зв'язку нову сторінку випадковим чином, то ймовірність вибору певної сторінки буде пропорційна її ступеню. Це пояснюється принципом переважного приєднання.

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

Алгоритм

Кроки зростання мережі у відповідності з моделлю БА

Мережа починається з початкової сітки з $m_{0}$ вузлами. $m_{0}>=2$ і степінь кожного вузла в початковій мережі повинна бути не менше 1, інакше вона завжди буде відокремлена від іншої частини мережі.

У кожен момент часу в мережу додається новий вузол. Кожен новий вузол з'єднується з наявними вузлами з ймовірністю, пропорційною числу зв'язків цих вузлів. Формально, ймовірністю того, що новий вузол з'єднається з вузлом i дорівнює:

p_{i}={k_{i} \over \sum _{j}k_{j}}

де $k_{i}$ —степінь i-го вузла, а в знаменнику підсумовуються степені всіх існуючих вузлів. Найбільш пов'язані вузли («хаби»), як правило, накопичують ще більше зв'язків, тоді як вузли з невеликим числом зв'язків навряд чи будуть обрані для приєднання нових вузлів. Нові вузли мають «перевагу» з'єднуватися з найбільш пов'язаними вузлами.

Мережа, побудована у відповідності з моделлю БА. Мережа побудована з 50 вершин з початковою ступенем m=1.

Властивості

Степеневий розподіл

Степеневий розподіл у моделі БА є безмасштабним, точніше підпорядковується степеневим законом

Розподіл степенів моделі БА, яке підпорядковується степеневим законом. У логарифмічному масштабі степенева функція являє собою пряму лінію.

P\left(k\right)\sim k^{-3}

Середня довжина шляху

Середня довжина шляху в моделі БА збільшується в середньому, як логарифм розміру мережі. Точна форма має подвійну логарифмічну поправку і виглядає, як:

\ell \sim {\frac {\ln N}{\ln \ln N}}.

Модель БА має систематично коротший середній шлях, ніж випадковий граф.

Кореляції степеня вузла

Кореляції степенів сполучених вузлів розвиваються випадковим чином в моделі БА, через особливості розвитку мережі. Ймовірність знаходження зв'язку між вузлами зі ступенями і в моделі БА представлена, як:

n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.

Звичайно ж, результат буде іншим, якщо розподіл був не корельованим , $n_{k\ell }=k^{-3}\ell ^{-3}$ .

Коефіцієнт кластеризації

Поки що немає аналітичних значень коефіцієнта кластеризації моделі БА. Коефіцієнти кластеризації, отримані емпіричним шляхом, в загальному випадку значно вище для моделі БА, ніж для випадкових мереж. Коефіцієнт кластеризації також залежить від розміру мережі згідно наближеному степеневим законом:

C\sim N^{-0.75}.

Це поведінка все ж відрізняється від поведінки малих мереж, де кластеризація не залежить від розміру мережі. У випадку ієрархічних мереж, кластеризація як функція ступеня вузла також підпорядковується степеневим законом:

C(k)=k^{-1}.

Дані результати були аналітично отримані Дороговцевим, і .

Спектральні якості

Форма спектральної щільності моделі БА відрізняється від напівкруглої спектральної щільності випадкового графу. Вона має трикутну форму з вершиною, що лежить значно вище півкола, а краї спадають за степеневим законом.

Граничні випадки

Модель А

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

Модель B

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

Провал моделей А і B при отриманні безмасштабного розподілу говорить про те, що зростання та ПП однаково необхідні для відтворення стаціонарного степеневого розподілу, досліджуваного в мережах реального світу

Історія

Принцип переважного приєднання вперше використано для пояснення степеневого розподілу, отриманого Юлем у 1925 році, хоча математичний аналіз Юля визнано туманним за сучасними стандартами через відсутність відповідних інструментів для аналізу випадкових процесів. Сучасний метод основного кінетичного рівняння, яке дає прозоріший висновок, застосував до проблеми Герберт Саймон 1955 року в ході дослідження розмірів міст і інших явищ. Вперше до зростання мереж його застосував 1976 року Дерек де Солла Прайс, який цікавився мережами цитування між науковими публікаціями. Назву «переважне приєднання» і сьогоднішню популярність моделей безмасштабних мереж пов'язують з роботами ^[en] і ^[en], які незалежно відкрили процес у 1999 році й застосували його до степеневого розподілу у всесвітній павутині.

Примітки

Albert, Réka; Barabási, Albert-László (2002). (PDF). Reviews of Modern Physics. 74 (1): 47—97. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47. ISSN 0034-6861. Архів оригіналу (PDF) за 24 серпня 2015. Процитовано 3 листопада 2016.
& (October 1999). (PDF). Science. 286 (5439): 509—512. doi:10.1126/science.286.5439.509. Архів оригіналу (PDF) за 17 квітня 2012. Процитовано 3 листопада 2016.
S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes, e-print cond-mat/0112143.
Udny Yule; Yule, G. Udny (1925). A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S. Journal of the Royal Statistical Society. 88 (3): 433—436. doi:10.2307/2341419. JSTOR 2341419.
Herbert A. Simon (December 1955). On a Class of Skew Distribution Functions. . 42 (3–4): 425—440. doi:10.1093/biomet/42.3-4.425.
D.J. de Solla Price (1976). A general theory of bibliometric and other cumulative advantage processes. . 27: 292—306. doi:10.1002/asi.4630270505.

Посилання

Складні мережі

[AlbertBarabási2002-1] Albert, Réka; Barabási, Albert-László (2002). (PDF). Reviews of Modern Physics. 74 (1): 47—97. Bibcode:2002RvMP...74...47A. doi:10.1103/RevModPhys.74.47. ISSN 0034-6861. Архів оригіналу (PDF) за 24 серпня 2015. Процитовано 3 листопада 2016.

[Barabasi1999-2] & (October 1999). (PDF). Science. 286 (5439): 509—512. doi:10.1126/science.286.5439.509. Архів оригіналу (PDF) за 17 квітня 2012. Процитовано 3 листопада 2016.

[3] S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes, e-print cond-mat/0112143.

[4] Udny Yule; Yule, G. Udny (1925). A Mathematical Theory of Evolution Based on the Conclusions of Dr. J. C. Willis, F.R.S. Journal of the Royal Statistical Society. 88 (3): 433—436. doi:10.2307/2341419. JSTOR 2341419.

[5] Herbert A. Simon (December 1955). On a Class of Skew Distribution Functions. . 42 (3–4): 425—440. doi:10.1093/biomet/42.3-4.425.

[6] D.J. de Solla Price (1976). A general theory of bibliometric and other cumulative advantage processes. . 27: 292—306. doi:10.1002/asi.4630270505.