Барабаси–Албертов модел

Барабаси-Албертов (БА) модел је алгоритам за генерисање неограничених мрежа користећи механизам преференцијалног повезивања. Неограничене мреже су запажене у великом броју природних и вештачких система, као што су интернет, светска комуникациона мрежа, мрежа цитата и неке друштвене мреже.

Концепти

Велики број мрежа подпада под класу неограничених мрежа, а то значи да имају поwер-лаw степен дистрибуције, док насумични граф модели као што је Ердос-Ренyи (ЕР) модел I Wаттс-Строгатз (WС) модел не показују поwер лаw. Барабаси-Алберт модел је један од неколикоко предложених модела који генеришу неограничене мреже. Он у себи садржи два тначајна уопштена концепта: раст и преференцијално повезивање. Оба ова концепта су широко распрострањена у реалним мрежама.

Раст значи да број чворова у мрежи расте временом.

Преференцијално повезивање значи да што је чвор више повезан, да је већа вероватноћа да ће да прими нове везе. Чворови са већим степеном имају већу могућност да хватају везе које се додају у мрежу. Интуитивно, преференцијално повезивање можемо да сагледамо како се људи повезују преко друштвених мрежа. У овом примеру веза између А и Б значи да особа А познаје особу Б. Високо повезани чворови представљају познате људе са доста познанстава. Када се нови члан прикључи заједници има већу шансу да буде упознат са тим познатим људима него са оним релативно непознатим. Слично томе, на вебу, нове странице линкују према познатим сајтовима, као на пример према Гугулу или Википедији, пре него ка сајтовима које скоро нико не зна. Ако неко изабере нову страницу да повеже тако што насумично изабере постојећу везу, вероватноћа да ће изабрати одређену страницу јер пропорционална са њеним степеном. Овиме се објашњава правило вероватноће преференцијалног повезивања.

Преференцијално повезивање је пример позитивног повратног круга где почетне насумичне варијације (где један чвор иницијално има више веза или је почео да скупља везе пре других) аутоматски појачане, чиме знатно повећавају разлику. Ово се понекад назива и Маттхеw ефекат, „богати постају богатији“, а у хемији аутокатализа.

Алгоритам

Мрежа започиње са иницијалном нрежем од $m_{0}$. Нови чворови се додају у мрежу појединачно. Сваки нови чвор је повезан са $m<=m_{0}$ постојећих чворова са вероватноћом која је пропорционална са бројем веза које постојећи чворови већ имају. Формално, вероватноћа пи да је нови чвор повезан са чвором и износи $p_{i}=k_{i}/(sum_{j}*k_{j})$ где је $k_{i}$ степен чвора $i$ а сума је направљена по свим постојецим ћворовима $j$ (на пример, делилац је тренутно број ивица у мрежи). Високо повезани чворови (хубови) теже да брзо прикупе још већи број веза, док чворови са свега неколико веза имају малу вероватноћу да буду изабрани као дестинација за нову везу. Нови чворови имају афинитет да се каче за високо повезане чворове.

Својства

Степен расподеле

Степен расподеле који произилази из БА модела неограничен, он има поwер лаw облика $P(k)~k^{-}3$

Просечна дужина путање

Просечна дужина путање БА модела се повећава скоро логаритамски са величином мреже. Права форма има дуплу логаритамску исправку $\ell \sim {\frac {\ln N}{\ln \ln N}}.$ БА модела има систематски краћу просечну путању он насумичног графа.

Степен корелације чворова

Корелација између степена повезаних чворова се спонтано развија у БА моделу због начина на који мрежа еволуира. Вероватноћа $n_{k\ell }$ проналажења везе између чворова степена $k$ и $\ell$ у БА моделу кад је $m=1$ се одредјује: $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}$

Коефицијент груписања

Док не постоје аналитички резултати за коефицијент груписања БА модела, емпиријски је закључено да је коефицијент груписања у БА моделу знатно веци него код насумичних мрежа. Коефицијент груписања се скалира са величином мреже приближно пратећи поwер лаw $C\sim N^{-0.75}.\,$ Понашање је и даље различито од понашања смалл-wорлд мрежа где су груписања независна од величине система. У случају хијерархијских мрежа, груписање у функцији степена чвора такође прати поwер-лаw $C(k)=k^{-1}.\,$ Ово резултат су аналитички добили Дороговтсев, Голтсев и Мендес.

Спектрална својства

Спектрална густина БА модела има различит облик од полукружне спектралне густине насумичног графа. Она има троугласт облик, са врхом далеко изнад полукруга и ивица распадајуци се као поwер лаw.

Ограничавајуци случајеви

Модел А

Модел А задржава раст али не садржи преференцијално повезивање. Вероватноца да се нови чвор повеже за било кој постојећи чвор је једнака. Резултујућа расподела степена у овом ограничењу је геометријска, сто указује да сам раст није довољан да произведе неограничену структуру.

Модел Б

Модел Б задржава преференцијално повезивање али елиминише раст. Модел почиње као фиксирани број неповезаних чворова и додаје везе, преференцијално бирајући чворове са високим степеном као одредишта за везе. Иако расподела степена у почетку делује као неограничена, дистибуција није стабилна и на крају постаје скоро Гаусова кад се мрежа приближава засићењу. Дакле, само преференцијално повезивање није довољно да произведе неограничену структуру.

Неуспех модела А и Б да доведу до неограничене расподеле указује да су и раст и преференцијално повезивање потребни да произведу стационарну поwер-лаw расподелу опажену у стварним мрежама.

Историја

Прва примена механизма преференцијалног повезивања да се објасни поwер-лаw расподела је вероватно спровео Yуле, 1925. године. Иако је Yуле-ов математички поступак наразумљив по данашњим стандардима јер му недостају одговарајући алати за анализирање стохастичког процеса. Модерна главни метод једначина, који даје транпарентније извођење, је применио на овај проблем Херберт А. Симонс 1955. током истраживања величине градова и осталих феномена. На раст мрежа ју је први применио Дерек де Солла Прице 1976. године, који је био заинтересован у мрежу цитата између научних папира. Име „преференцијално повезивање“ и данасњу популарност модела неограничених мрежа дугујемо раду Албет-Ласзло Барабаси-ју и Река Алберт, који су поново открили овај процес независно 1999. године и применили га цтепеној расподели на мрежи.