Back

ⓘ Barabasi–Albertov model




Barabasi–Albertov model
                                     

ⓘ Barabasi–Albertov model

Barabasi-Albertov 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.

                                     

1. 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 izmedu 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 odredenu 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.

Users also searched:

...