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 prirodnim 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 popdada 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 web-u, nove stranice linkuju prema poznatim sajtovima, kao na primer prema Google-u ili Wikipedii, pre nego ka sajtovima koje skoro niko nezna. Ako neko izabere novu stranicu da poveže tako što nasumično izabere postojeću vezu, verovatnoća da ce 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 pogatiji“, 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.