Модель Барабаши-Альберт (БА) — алгоритм генерації випадкових безмасштабних мереж з використанням принципу переважного приєднання. Безмасштабні мережі широко зустрічаються як в природі (харчові ланцюжки), так і створені людиною — Інтернет, всесвітня павутина, мережі цитування, деякі соціальні мережі. Зазначені мережі є майже безмасштабними, однак, в них наявні декілька вузлів (їх звуть хабами) з надвисоким степенем у порівнянні з іншими вузлами мережі. Модель Барабаші-Альберт саме й намагається пояснити природу цих вузлів в реальних мережах. Алгоритм названий на честь дослідників [en] та [en] і є окремим випадком більш загальної моделі Прайса.
Концепції
Багато мереж, що досліджувалися, потрапляють у клас безмасштабних мереж. Це означає, що вони мають степеневий розподіл за ступенем вузла, тоді як моделі випадкових графів (Воттса — Строгаца і Ердеша — Реньї не мають такого розподілу. Модель Барабаші — Альберт — одна з декількох запропонованих моделей зі степеневим розподілом, які генерують безмасштабні мережі. Вона включає в себе дві важливі загальні концепції:
- зростання мережі
- принцип переважного приєднання (ПП)
Обидві концепції широко представлені в мережах реального світу. Зростання означає, що число вузлів мережі збільшується з часом.
Принцип переважного приєднання полягає в тому, що чим більше зв'язків має вузол, тим більше ймовірність утворення нових зв'язків. Вузли з найбільшим ступенем мають більше можливостей забирати собі зв'язки, які додаються в мережу. Інтуїтивно, принцип переважного приєднання може бути зрозумілий, якщо ми думаємо в термінах соціальних мереж, які об'єднують людей. Тут зв'язок від А до B означає, що людина «знає» або «знайома» з людиною B. Сильно пов'язані вузли представлені відомими людьми з великою кількістю зв'язків. Коли новачок потрапляє в товариство, для нього/неї більш переважно зв'язатися з одним з відомих людей, ніж з відносно невідомих. Подібним чином у всесвітній мережі сторінки часто лінкуються з хабами, приміром, з добре відомими сайтами, як Гугл або Вікіпедія, на відміну від сайтів, які мало кому відомі. Якщо вибирати для зв'язку нову сторінку випадковим чином, то ймовірність вибору певної сторінки буде пропорційна її ступеню. Це пояснюється принципом переважного приєднання.
Принцип переважно приєднання — приклад позитивного зворотного зв'язку, де спочатку випадкові варіації (один вузол спочатку має більше посилань або починає збирати посилання раніше інших) автоматично посилюються, тим самим значно збільшуючи розрив. Це також іноді називають ефектом Матфея, «багаті стають багатшими», або автокаталізом в хімії.
Алгоритм
Мережа починається з початкової сітки з вузлами. і степінь кожного вузла в початковій мережі повинна бути не менше 1, інакше вона завжди буде відокремлена від іншої частини мережі.
У кожен момент часу в мережу додається новий вузол. Кожен новий вузол з'єднується з наявними вузлами з ймовірністю, пропорційною числу зв'язків цих вузлів. Формально, ймовірністю того, що новий вузол з'єднається з вузлом i дорівнює:
де —степінь i-го вузла, а в знаменнику підсумовуються степені всіх існуючих вузлів. Найбільш пов'язані вузли («хаби»), як правило, накопичують ще більше зв'язків, тоді як вузли з невеликим числом зв'язків навряд чи будуть обрані для приєднання нових вузлів. Нові вузли мають «перевагу» з'єднуватися з найбільш пов'язаними вузлами.
Властивості
Степеневий розподіл
Степеневий розподіл у моделі БА є безмасштабним, точніше підпорядковується степеневим законом
Середня довжина шляху
Середня довжина шляху в моделі БА збільшується в середньому, як логарифм розміру мережі. Точна форма має подвійну логарифмічну поправку і виглядає, як:
Модель БА має систематично коротший середній шлях, ніж випадковий граф.
Кореляції степеня вузла
Кореляції степенів сполучених вузлів розвиваються випадковим чином в моделі БА, через особливості розвитку мережі. Ймовірність знаходження зв'язку між вузлами зі ступенями і в моделі БА представлена, як:
Звичайно ж, результат буде іншим, якщо розподіл був не корельованим , .
Коефіцієнт кластеризації
Поки що немає аналітичних значень коефіцієнта кластеризації моделі БА. Коефіцієнти кластеризації, отримані емпіричним шляхом, в загальному випадку значно вище для моделі БА, ніж для випадкових мереж. Коефіцієнт кластеризації також залежить від розміру мережі згідно наближеному степеневим законом:
Це поведінка все ж відрізняється від поведінки малих мереж, де кластеризація не залежить від розміру мережі. У випадку ієрархічних мереж, кластеризація як функція ступеня вузла також підпорядковується степеневим законом:
Дані результати були аналітично отримані Дороговцевим, і .
Спектральні якості
Форма спектральної щільності моделі БА відрізняється від напівкруглої спектральної щільності випадкового графу. Вона має трикутну форму з вершиною, що лежить значно вище півкола, а краї спадають за степеневим законом.
Граничні випадки
Модель А
Модель А зберігає зростання, але не включає принцип переважного приєднання. Ймовірність приєднання нового вузла до наявних скрізь однакова. Кінцевий розподіл ступенів у цьому випадку говорить про те, що зріст сам по собі недостатній для отримання безмасштабної структури.
Модель 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.
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Model Barabashi Albert BA algoritm generaciyi vipadkovih bezmasshtabnih merezh z vikoristannyam principu perevazhnogo priyednannya Bezmasshtabni merezhi shiroko zustrichayutsya yak v prirodi harchovi lancyuzhki tak i stvoreni lyudinoyu Internet vsesvitnya pavutina merezhi cituvannya deyaki socialni merezhi Zaznacheni merezhi ye majzhe bezmasshtabnimi odnak v nih nayavni dekilka vuzliv yih zvut habami z nadvisokim stepenem u porivnyanni z inshimi vuzlami merezhi Model Barabashi Albert same j namagayetsya poyasniti prirodu cih vuzliv v realnih merezhah Algoritm nazvanij na chest doslidnikiv en ta en i ye okremim vipadkom bilsh zagalnoyi modeli Prajsa KoncepciyiBagato merezh sho doslidzhuvalisya potraplyayut u klas bezmasshtabnih merezh Ce oznachaye sho voni mayut stepenevij rozpodil za stupenem vuzla todi yak modeli vipadkovih grafiv Vottsa Strogaca i Erdesha Renyi ne mayut takogo rozpodilu Model Barabashi Albert odna z dekilkoh zaproponovanih modelej zi stepenevim rozpodilom yaki generuyut bezmasshtabni merezhi Vona vklyuchaye v sebe dvi vazhlivi zagalni koncepciyi zrostannya merezhi princip perevazhnogo priyednannya PP Obidvi koncepciyi shiroko predstavleni v merezhah realnogo svitu Zrostannya oznachaye sho chislo vuzliv merezhi zbilshuyetsya z chasom Princip perevazhnogo priyednannya polyagaye v tomu sho chim bilshe zv yazkiv maye vuzol tim bilshe jmovirnist utvorennya novih zv yazkiv Vuzli z najbilshim stupenem mayut bilshe mozhlivostej zabirati sobi zv yazki yaki dodayutsya v merezhu Intuyitivno princip perevazhnogo priyednannya mozhe buti zrozumilij yaksho mi dumayemo v terminah socialnih merezh yaki ob yednuyut lyudej Tut zv yazok vid A do B oznachaye sho lyudina znaye abo znajoma z lyudinoyu B Silno pov yazani vuzli predstavleni vidomimi lyudmi z velikoyu kilkistyu zv yazkiv Koli novachok potraplyaye v tovaristvo dlya nogo neyi bilsh perevazhno zv yazatisya z odnim z vidomih lyudej nizh z vidnosno nevidomih Podibnim chinom u vsesvitnij merezhi storinki chasto linkuyutsya z habami primirom z dobre vidomimi sajtami yak Gugl abo Vikipediya na vidminu vid sajtiv yaki malo komu vidomi Yaksho vibirati dlya zv yazku novu storinku vipadkovim chinom to jmovirnist viboru pevnoyi storinki bude proporcijna yiyi stupenyu Ce poyasnyuyetsya principom perevazhnogo priyednannya Princip perevazhno priyednannya priklad pozitivnogo zvorotnogo zv yazku de spochatku vipadkovi variaciyi odin vuzol spochatku maye bilshe posilan abo pochinaye zbirati posilannya ranishe inshih avtomatichno posilyuyutsya tim samim znachno zbilshuyuchi rozriv Ce takozh inodi nazivayut efektom Matfeya bagati stayut bagatshimi abo avtokatalizom v himiyi AlgoritmKroki zrostannya merezhi u vidpovidnosti z modellyu BA Merezha pochinayetsya z pochatkovoyi sitki z m 0 displaystyle m 0 vuzlami m 0 gt 2 displaystyle m 0 gt 2 i stepin kozhnogo vuzla v pochatkovij merezhi povinna buti ne menshe 1 inakshe vona zavzhdi bude vidokremlena vid inshoyi chastini merezhi U kozhen moment chasu v merezhu dodayetsya novij vuzol Kozhen novij vuzol z yednuyetsya z nayavnimi vuzlami z jmovirnistyu proporcijnoyu chislu zv yazkiv cih vuzliv Formalno jmovirnistyu togo sho novij vuzol z yednayetsya z vuzlom i dorivnyuye p i k i j k j displaystyle p i k i over sum j k j de k i displaystyle k i stepin i go vuzla a v znamenniku pidsumovuyutsya stepeni vsih isnuyuchih vuzliv Najbilsh pov yazani vuzli habi yak pravilo nakopichuyut she bilshe zv yazkiv todi yak vuzli z nevelikim chislom zv yazkiv navryad chi budut obrani dlya priyednannya novih vuzliv Novi vuzli mayut perevagu z yednuvatisya z najbilsh pov yazanimi vuzlami Merezha pobudovana u vidpovidnosti z modellyu BA Merezha pobudovana z 50 vershin z pochatkovoyu stupenem m 1 VlastivostiStepenevij rozpodil Stepenevij rozpodil u modeli BA ye bezmasshtabnim tochnishe pidporyadkovuyetsya stepenevim zakonom Rozpodil stepeniv modeli BA yake pidporyadkovuyetsya stepenevim zakonom U logarifmichnomu masshtabi stepeneva funkciya yavlyaye soboyu pryamu liniyu P k k 3 displaystyle P left k right sim k 3 Serednya dovzhina shlyahu Serednya dovzhina shlyahu v modeli BA zbilshuyetsya v serednomu yak logarifm rozmiru merezhi Tochna forma maye podvijnu logarifmichnu popravku i viglyadaye yak ℓ ln N ln ln N displaystyle ell sim frac ln N ln ln N Model BA maye sistematichno korotshij serednij shlyah nizh vipadkovij graf Korelyaciyi stepenya vuzla Korelyaciyi stepeniv spoluchenih vuzliv rozvivayutsya vipadkovim chinom v modeli BA cherez osoblivosti rozvitku merezhi Jmovirnist znahodzhennya zv yazku mizh vuzlami zi stupenyami i v modeli BA predstavlena yak n k ℓ 4 ℓ 1 k k 1 k ℓ k ℓ 1 k ℓ 2 12 ℓ 1 k k ℓ 1 k ℓ k ℓ 1 k ℓ 2 displaystyle 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 Zvichajno zh rezultat bude inshim yaksho rozpodil buv ne korelovanim n k ℓ k 3 ℓ 3 displaystyle n k ell k 3 ell 3 Koeficiyent klasterizaciyi Poki sho nemaye analitichnih znachen koeficiyenta klasterizaciyi modeli BA Koeficiyenti klasterizaciyi otrimani empirichnim shlyahom v zagalnomu vipadku znachno vishe dlya modeli BA nizh dlya vipadkovih merezh Koeficiyent klasterizaciyi takozh zalezhit vid rozmiru merezhi zgidno nablizhenomu stepenevim zakonom C N 0 75 displaystyle C sim N 0 75 Ce povedinka vse zh vidriznyayetsya vid povedinki malih merezh de klasterizaciya ne zalezhit vid rozmiru merezhi U vipadku iyerarhichnih merezh klasterizaciya yak funkciya stupenya vuzla takozh pidporyadkovuyetsya stepenevim zakonom C k k 1 displaystyle C k k 1 Dani rezultati buli analitichno otrimani Dorogovcevim i Spektralni yakosti Forma spektralnoyi shilnosti modeli BA vidriznyayetsya vid napivkrugloyi spektralnoyi shilnosti vipadkovogo grafu Vona maye trikutnu formu z vershinoyu sho lezhit znachno vishe pivkola a krayi spadayut za stepenevim zakonom Granichni vipadkiModel A Model A zberigaye zrostannya ale ne vklyuchaye princip perevazhnogo priyednannya Jmovirnist priyednannya novogo vuzla do nayavnih skriz odnakova Kincevij rozpodil stupeniv u comu vipadku govorit pro te sho zrist sam po sobi nedostatnij dlya otrimannya bezmasshtabnoyi strukturi Model B Model B zberigaye princip perevazhnogo priyednannya ale viklyuchaye zrostannya Model pochinayetsya z fiksovanogo chisla roz yednanih vuzliv i dodaye zv yazku perevazhno vibirayuchi tochkami priznachennya vuzli z visokim stupenem Hocha rozpodil stupeniv pochatku modelyuvannya viglyadaye bezmasshtabnim vono nestabilne i zreshtoyu staye blizkim do gausovogo koli merezha nablizhayetsya do nasichennya Takim chinom princip PP sam po sobi nedostatnij dlya stvorennya bezmasshtabnoyi strukturi Proval modelej A i B pri otrimanni bezmasshtabnogo rozpodilu govorit pro te sho zrostannya ta PP odnakovo neobhidni dlya vidtvorennya stacionarnogo stepenevogo rozpodilu doslidzhuvanogo v merezhah realnogo svituIstoriyaPrincip perevazhnogo priyednannya vpershe vikoristano dlya poyasnennya stepenevogo rozpodilu otrimanogo Yulem u 1925 roci hocha matematichnij analiz Yulya viznano tumannim za suchasnimi standartami cherez vidsutnist vidpovidnih instrumentiv dlya analizu vipadkovih procesiv Suchasnij metod osnovnogo kinetichnogo rivnyannya yake daye prozorishij visnovok zastosuvav do problemi Gerbert Sajmon 1955 roku v hodi doslidzhennya rozmiriv mist i inshih yavish Vpershe do zrostannya merezh jogo zastosuvav 1976 roku Derek de Solla Prajs yakij cikavivsya merezhami cituvannya mizh naukovimi publikaciyami Nazvu perevazhne priyednannya i sogodnishnyu populyarnist modelej bezmasshtabnih merezh pov yazuyut z robotami en i en yaki nezalezhno vidkrili proces u 1999 roci j zastosuvali jogo do stepenevogo rozpodilu u vsesvitnij pavutini PrimitkiAlbert Reka Barabasi Albert Laszlo 2002 PDF Reviews of Modern Physics 74 1 47 97 Bibcode 2002RvMP 74 47A doi 10 1103 RevModPhys 74 47 ISSN 0034 6861 Arhiv originalu PDF za 24 serpnya 2015 Procitovano 3 listopada 2016 amp October 1999 PDF Science 286 5439 509 512 doi 10 1126 science 286 5439 509 Arhiv originalu PDF za 17 kvitnya 2012 Procitovano 3 listopada 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 PosilannyaSkladni merezhi