Barabasi–Albertov model

Barabasi-Albertov (BA) model je algoritam za generisanje neograničenih mreža koristeći mehanizam preferencijalnog povezivanja. Neograničene mreže su zapažene u velikom broju prirodnih i veštačkih sistema, kao što su internet, svetska komunikaciona mreža, mreža citata i neke društvene mreže.

Koncepti

Veliki broj mreža podpada pod klasu neograničenih mreža, a to znači da imaju power-law stepen distribucije, dok nasumični graf modeli kao što je Erdos-Renyi (ER) model I Watts-Strogatz (WS) model ne pokazuju power law. Barabasi-Albert model je jedan od nekolikoko predloženih modela koji generišu neograničene mreže. On u sebi sadrži dva tnačajna uopštena koncepta: rast i preferencijalno povezivanje. Oba ova koncepta su široko rasprostranjena u realnim mrežama.

Rast znači da broj čvorova u mreži raste vremenom.

Preferencijalno povezivanje znači da što je čvor više povezan, da je veća verovatnoća da će da primi nove veze. Čvorovi sa većim stepenom imaju veću mogućnost da hvataju veze koje se dodaju u mrežu. Intuitivno, preferencijalno povezivanje možemo da sagledamo kako se ljudi povezuju preko društvenih mreža. U ovom primeru veza između A i B znači da osoba A poznaje osobu B. Visoko povezani čvorovi predstavljaju poznate ljude sa dosta poznanstava. Kada se novi član priključi zajednici ima veću šansu da bude upoznat sa tim poznatim ljudima nego sa onim relativno nepoznatim. Slično tome, na vebu, nove stranice linkuju prema poznatim sajtovima, kao na primer prema Gugulu ili Vikipediji, pre nego ka sajtovima koje skoro niko ne zna. Ako neko izabere novu stranicu da poveže tako što nasumično izabere postojeću vezu, verovatnoća da će izabrati određenu stranicu jer proporcionalna sa njenim stepenom. Ovime se objašnjava pravilo verovatnoće preferencijalnog povezivanja.

Preferencijalno povezivanje je primer pozitivnog povratnog kruga gde početne nasumične varijacije (gde jedan čvor inicijalno ima više veza ili je počeo da skuplja veze pre drugih) automatski pojačane, čime znatno povećavaju razliku. Ovo se ponekad naziva i Matthew efekat, „bogati postaju bogatiji“, a u hemiji autokataliza.

Algoritam

Mreža započinje sa inicijalnom nrežem od $m_{0}$. Novi čvorovi se dodaju u mrežu pojedinačno. Svaki novi čvor je povezan sa $m<=m_{0}$ postojećih čvorova sa verovatnoćom koja je proporcionalna sa brojem veza koje postojeći čvorovi već imaju. Formalno, verovatnoća pi da je novi čvor povezan sa čvorom i iznosi $p_{i}=k_{i}/(sum_{j}*k_{j})$ gde je $k_{i}$ stepen čvora $i$ a suma je napravljena po svim postojecim ćvorovima $j$ (na primer, delilac je trenutno broj ivica u mreži). Visoko povezani čvorovi (hubovi) teže da brzo prikupe još veći broj veza, dok čvorovi sa svega nekoliko veza imaju malu verovatnoću da budu izabrani kao destinacija za novu vezu. Novi čvorovi imaju afinitet da se kače za visoko povezane čvorove.

Svojstva

Stepen raspodele

Stepen raspodele koji proizilazi iz BA modela neograničen, on ima power law oblika $P(k)~k^{-}3$

Prosečna dužina putanje

Prosečna dužina putanje BA modela se povećava skoro logaritamski sa veličinom mreže. Prava forma ima duplu logaritamsku ispravku $\ell \sim {\frac {\ln N}{\ln \ln N}}.$ BA modela ima sistematski kraću prosečnu putanju on nasumičnog grafa.

Stepen korelacije čvorova

Korelacija između stepena povezanih čvorova se spontano razvija u BA modelu zbog načina na koji mreža evoluira. Verovatnoća $n_{k\ell }$ pronalaženja veze između čvorova stepena $k$ i $\ell$ u BA modelu kad je $m=1$ se odredjuje: $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)}}.$ Ovo trenutno nije rezultat koji bi se očekivao da raspodela nije u korelaciji, $n_{k\ell }=k^{-3}\ell ^{-3}$

Koeficijent grupisanja

Dok ne postoje analitički rezultati za koeficijent grupisanja BA modela, empirijski je zaključeno da je koeficijent grupisanja u BA modelu znatno veci nego kod nasumičnih mreža. Koeficijent grupisanja se skalira sa veličinom mreže približno prateći power law $C\sim N^{-0.75}.\,$ Ponašanje je i dalje različito od ponašanja small-world mreža gde su grupisanja nezavisna od veličine sistema. U slučaju hijerarhijskih mreža, grupisanje u funkciji stepena čvora takođe prati power-law $C(k)=k^{-1}.\,$ Ovo rezultat su analitički dobili Dorogovtsev, Goltsev i Mendes.

Spektralna svojstva

Spektralna gustina BA modela ima različit oblik od polukružne spektralne gustine nasumičnog grafa. Ona ima trouglast oblik, sa vrhom daleko iznad polukruga i ivica raspadajuci se kao power law.

Ograničavajuci slučajevi

Model A

Model A zadržava rast ali ne sadrži preferencijalno povezivanje. Verovatnoca da se novi čvor poveže za bilo koj postojeći čvor je jednaka. Rezultujuća raspodela stepena u ovom ograničenju je geometrijska, sto ukazuje da sam rast nije dovoljan da proizvede neograničenu strukturu.

Model B

Model B zadržava preferencijalno povezivanje ali eliminiše rast. Model počinje kao fiksirani broj nepovezanih čvorova i dodaje veze, preferencijalno birajući čvorove sa visokim stepenom kao odredišta za veze. Iako raspodela stepena u početku deluje kao neograničena, distibucija nije stabilna i na kraju postaje skoro Gausova kad se mreža približava zasićenju. Dakle, samo preferencijalno povezivanje nije dovoljno da proizvede neograničenu strukturu.

Neuspeh modela A i B da dovedu do neograničene raspodele ukazuje da su i rast i preferencijalno povezivanje potrebni da proizvedu stacionarnu power-law raspodelu opaženu u stvarnim mrežama.

Istorija

Prva primena mehanizma preferencijalnog povezivanja da se objasni power-law raspodela je verovatno sproveo Yule, 1925. godine. Iako je Yule-ov matematički postupak narazumljiv po današnjim standardima jer mu nedostaju odgovarajući alati za analiziranje stohastičkog procesa. Moderna glavni metod jednačina, koji daje tranparentnije izvođenje, je primenio na ovaj problem Herbert A. Simons 1955. tokom istraživanja veličine gradova i ostalih fenomena. Na rast mreža ju je prvi primenio Derek de Solla Price 1976. godine, koji je bio zainteresovan u mrežu citata između naučnih papira. Ime „preferencijalno povezivanje“ i danasnju popularnost modela neograničenih mreža dugujemo radu Albet-Laszlo Barabasi-ju i Reka Albert, koji su ponovo otkrili ovaj proces nezavisno 1999. godine i primenili ga ctepenoj raspodeli na mreži.