Google PageRank algoritam

Guglanje, pojam koji označava pretraživanje Interneta upotrebom Google tražilice, već se
duboko ukorijenio u hrvatski jezik. Ovisno o vlastitim interesima svakodnevno guglamo kako
bismo saznali razne informacije. Na Internetu možemo pronaći gotovo sve što nam padne na
pamet, od recepata, glazbe, slavnih ličnosti, auta do znanstvenih istraživanja i najnovijih
događaja u svijetu. Informacije iz cijelog svijeta dostupne su nam u nekoliko klikova. No, jeste li
se ikada pitali kako Google radi? Na koji način rangira rezultate pretraživanja?
Iako bi na prvu pomislili da nam na vrhu nudi web stranice ili kraće stranice s najviše pregleda,
to nije način na koji Google pretraživanje funkcionira. Google je jedinstven po tome što koristi
PageRank algoritam prema kojem se web stranice rangiraju po važnosti prilikom pretraživanja
samo na temelju poveznica (linkova). Algoritam su razvili Larry Page i Sergey Brin na
Sveučilištu Stanford 1996. godine. Patent algoritma je zadržalo Sveučilište Stanford, dok
Google ima ekskluzivnu licencu i prava. Danas je jedan od najpoznatijih algoritama, a naziv je
dobio prema terminu “web page” i jednom od kreatora. Osnovna ideja je da su važne stranice
one na koje upućuje mnogo drugih stranica, dok poveznice s važnijih stranica pridonose više.
Odnosno kod određivanja važnosti pojedine stranice gleda se broj i kvaliteta svih poveznica
koje upućuju na tu stranicu. Kvaliteta poveznice određuje se na temelju važnosti stranice s koje
dolazi.
Matematički gledano to je broj između 0 i 1 koji predstavlja vjerojatnost da će osoba slučajnim
klikanjem stići do određene stranice. Ideju PageRank algoritma možemo promatrati kao
usmjereni graf kod kojeg su vrhovi web stranice, a bridovi poveznice. Vrhovi označeni
krugovima su veći ukoliko je stranica važnija. Promotrimo pojednostavljenu verziju algoritma na
skupu od 4 web stranice A, B, C i D.

Određivanje PageRanka provodi se iterativno, odnosno u više koraka, tako da se PageRank
neke stranice dijeli jednako između svih stranica na koje upućuje. Inicijalna vrijednost koju
pridružujemo svakoj web stranici je 1/4, odnosno 0.25. PageRank stranice A, u oznaci PR(A),
računa se prema formuli PR(A) = PR(B)/L(B) + PR(C)/L(C) + PR(D)/L(D) pri čemu L(V)

označava broj poveznica sa stranice V. Ako uvrstimo vrijednosti u formulu dobivamo PR(A) =
0.25/2 + 0.25/1 + 0.25/3 = 0.458. Dobivamo da je vjerojatnost da će osoba slučajnim klikanje na
ovom skupu stranica doći do stranice A s vjerojatnošću 45.8%. U složenijoj verziji algoritma
uzimaju se u obzir i različiti faktori i algoritam se odvija u puno više koraka. Jedan od bitnih
faktora je tzv. damping factor, u oznaci d, koji označava vjerojatnost da će osoba u svakom
koraku nastaviti klikati. Time se uzima u obzir da će osoba u nekom trenutku stati. Najčešće se
postavlja na vrijednost 0.85. Ukoliko u gornju formulu uvrstimo damping factor d dobivamo
sljedeću formulu PR(A) = (1-d)/ N + d * (PR(B)/L(B) + PR(C)/L(C) + PR(D)/L(D)) pri čemu je N
ukupan broj web stranica, u našem slučaju 4.
Ukoliko neka stranica nema izlaznih poveznica smatra se da upućuje na sve stranice unutar
skupa promatranih stranica. Također, ukoliko neka stranica nema ulaznih poveznica u svakom
koraku joj se koristeći damping factor pridodaje neka malena vrijednost kako bi ona i dalje imala
utjecaj prilikom rangiranja. To je čest slučaj kod novijih stranica.
Kako smo web stranice i poveznice među njima predstavili pomoću usmjerenog grafa problem
određivanja PageRanka možemo promatrati kao slučajnu šetnju po Markovljevom lancu kod
kojeg bridovi predstavljaju prijelaze iz jednog vrha u drugi. U Markovljevoj teoriji PageRank
predstavlja vjerojatnost dostizanja određenog vrha (web stranice) nakon velikog broja koraka
(klikova).
Budući da je važna stavka marketinga biti visokorangiran prilikom pretraživanja, a algoritam je
podložan manipulaciji neke visokorangirane kompanije nude prodaju poveznica čime se
smanjuje točnost i stabilnost samog algoritma. Stoga Google penalizira takve plaćene
poveznice ukoliko ih otkrije. Korištenjem PageRank algoritma dobiveni su puno precizniji
rezultati prilikom pretraživanja i Google se izdigao iznad ostalih pretraživača. Google i danas
koristi PageRank algoritam, ali samo kao dio puno kompleksnijeg algoritma za rangiranje web
stranica koji se i dalje usavršava.

Vaša eMatematika