Pejdž rank

Rang veb stranica (engl. PageRank) je Google-ova patentirana tehnologija koja pokazuje popularnost web stranice, a ne web sajta u celosti kako se pogrešno misli. Da bi web stranica dobila PR potrebno je da neka druga strana linkuje ka njoj i na taj način joj “prenosi” deo svog PR-a. Svi spoljni linkovi jedne stranice dele PR, tako da za maksimalne rezultate treba težiti ka tome da se postavi link na stranici sa visokim PR-om i malim brojem izlaznih (spoljnih) linkova. Mnoštvo izlaznih linkova obara PR. Što se tiče broja dolazećih linkova, što ih je više, to je bolje. I još nešto govori algoritam: nepostajanje dolazećih linkova može da ima negativan uticaj na PR koeficijent stranice na koju se ukazuje (najgori slučaj je da nema nikakav uticaj).

PR su u originalu formulisali Sergey Brin i Larry Page u svom radu The Anatomy of a Large-Scale Hypertextual. Zasnovan je na premisi da u akademskom svetu značaj istraživačkog rada se procenjuje na osnovu broja citata koje rad ima u drugim istraživačkim radovima.

Sergey Brin i Larry Page su kao prvu verzija internet pretraživača razvili BackRub. Ta verzija ocenjena je vrlo pohvalno od kolega sa univerziteta i pozitivne kritike počele su da cirkulišu internetom. S obzirom na to da su kuburili sa novcem, Lari je potreban hardver sklapao od jeftinih komponenti (prvi štampač imao je kućište od Lego kockica). S obzirom na sve veći broj web stranica koje su smeštali u svoju bazu podataka i sve širi krug korisnika, Sergej i Lari nikad nisu imali dovoljno računara i prateće opreme.

PR ne raste linearno, to je logaritamska funkcija. (Zato su vrednost PR1-PR10). Zato je neuporedivo lakše stići od PR1 do PR6 nego od PR6 do PR7. PR koji vidimo na Google Toolbaru za IE, ili PageRank Status ekstenziji za FireFox je samo aproksimacija prave vrednosti koja čak i ne mora biti tačna, jer se Toolbar PR ne update-uje redovno. Zato ga ne treba prihvatati kao relevantnog.

Najčešća zabluda vezana za PR jeste da on direktno utiče na rangiranje web strane u pretragama. Ta zabluda nagoni mnoge webmastere da usmere svu energiju u povećanje PR-a u želji da se što bolje rangiraju. Nažalost, PR je samo jedan od faktora koji utiču na SERP-ove Googla. Drugi aspekti se određuju na osnovu algoritma za rangiranje stranica.

Vremenom su se SEO kompanije izveštile u povećanju PageRank-a na načine koji već počinju da dovode u pitanje vrednost ove tehnike, te ju je Google u jednom od svojih patenata dodatno rafinirao. Naime, inicijalno dobijeni rezultati pretrage sada se dodatno vrednuju na osnovu njihove međusobne povezanosti, to jest dokumenti iz prvobitnog seta rezultata dobijaju na vrednosti ukoliko drugi dokumenti iz istog seta imaju link na njih.

Istorija uredi

Ideja o formulaciji problema link analize kao karakteristične vrednosti verovatno je prvo predložena 1976. od strane Gabriel Pinski i Francis Narin. PageRank su razvili Larry Page i Sergey Brin 1996. na univerzitetu Stanford kao deo istraživačkog projekta o novoj vrsti pretraživača. Sergey Brin je imao ideju da informacija na veb-u može biti uređena u hijerarhiju po "popularnosti linka" : strana je više rangirana ako postoji više linkova na nju. Koautori su bili Rajeev Motwani and Terry Winograd . Prvi zapis o projektu, koji opisuju PageRank i inicijalni prototip Google pretraživača je izdat 1998. , kratko nakon što su Page i Brin osnovali Google Inc. , kompaniju koja stoji iza Google pretraživača.

Naziv "PageRank" potiče od imena Larry Page , kao i koncept veb strana. Međutim, patent je dodeljen Stanford univerzitetu, a ne Google-u. Google ima ekskluzivno licencirana prava na patent, dodeljena od Stanford univerziteta. Univerzitet je primio 1,8 miliona akcija od Google-a u zamenu za korišćenje patenta; akcije su prodate 2005. godine za 336 miliona dolara.

PageRank su razvili Eugene Garfield i Massimo Marchiori u 1950-im godinama. Jon Kleinberg je 1998. godine izdao važan rad o HITS , kada je i PageRank predstavljen. Osnivači Google-a citiraju Garfield-a, Marchiori-a, i Kleinberg-a u svojim originalnim radovima.

Jednostavan algoritam uredi

Pretpostavimo da imamo 4 veb strane A,B,C i D . Linkovi stranica na njih same, ili višestruki linkovi sa jedne na drugu stranicu su ignorisani. PageRank je inicijalizovan na istu vrednost za sve stranice. U originalnoj formi PageRank-a, zbir PageRank-a kroz sve stranice je ukupan broj strana na vebu u to vreme, pa svaka stranica ima inicijalnu vrednost 1. Međutim, kasnije vezije PageRank-a, i ostatak ove sekcije, pretpostavljaju verovatnoću distributivnosti između 0 i 1. Odatle inicijalne vrednosti za svaku stranicu su 0.25 .

PageRank prelazi od zadate stranice na stranicu na koju vodi link do sledeće iteracije, podeljen je jednako između svih linkova. Ako su jedini linkovi bili od B,C i D do A, svaki od njih bi prebacio 0.25 PageRank-a na A do sledeće iteracije, što je ukupno 0.75 .

PR(A)=PR(B)+PR(C)+PR(D).\,

Pretopstavimo da strana B ima link na C i A, strana C na stranu A, i strana D ima linkove na sve strane. Tako, u prvoj iteraciji, B prebacuje polovinu svoje postojece vrednosti, tj. 0.125 strani A i drugu polovinu strani C. Strana C bi prebacila celu svoju vrednost, tj. 0.25 , stranici A. Pošto D ima tri linka, ona prebacuje trećinu svoje vrednosti, što je približno 0.083, na A. Posle ove iteracije, strana A će imati PageRank 0.458 .

PR(A)={\frac {PR(B)}{2}}+{\frac {PR(C)}{1}}+{\frac {PR(D)}{3}}.\,

Drugim rečima, PageRank koji je poveren strani na koju link pokazuje je jednak PageRank-u te strane podeljen sa brojem linkova koje ta strana ima (L( ))

PR(A)={\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}.\,

U opštem slučaju, vrednost PageRank-a za svaku stranicu u može se izraziti kao:

PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}

,

PageRank MATLAB/Octave implementacija

% Параметар M матрица повезаности
% где M_i,j представља линк од 'j' до 'i', тако да важи за све 'j' sum(i, M_i,j) = 1
% Параметар d фактор пригушивања
% Параметар v_quadratic_error квадратна грешка за v
% Враћа v, вектор рангова при чему је v_i i-th ранг из интервала [0, 1]

function [v] = rank(M, d, v_quadratic_error)

N = size(M, 2); % N је половина од реда M
v = rand(N, 1);
v = v ./ norm(v, 2);
last_v = ones(N, 1) * inf;
M_hat = (d .* M) + (((1 - d) / N) .* ones(N, N));

while(norm(v - last_v, 2) > v_quadratic_error)
	last_v = v;
	v = M_hat * v;
	v = v ./ norm(v, 2);
end

endfunction

function [v] = rank2(M, d, v_quadratic_error)

N = size(M, 2); % N је половина од реда M
v = rand(N, 1);
v = v ./ norm(v, 1); % Сада је ово L1, а не L2
last_v = ones(N, 1) * inf;
M_hat = (d .* M) + (((1 - d) / N) .* ones(N, N));

while(norm(v - last_v, 2) > v_quadratic_error)
	last_v = v;
	v = M_hat * v;
        % избачена L2 норма из текуће итерације PR-а
end

endfunction

Primer poziva rang funkicje, gore definisane:

M = [0 0 0 0 1 ; 0.5 0 0 0 0 ; 0.5 0 0 0 0 ; 0 1 0.5 0 0 ; 0 0 0.5 1 0];
rank(M, 0.80, 0.001)

Ovaj primer ima 13 iteracija do konvergiranja.

Zaključak uredi

Možda je preciznije reći da PR algoritam se primenjuje na rezultate Google pretrage nakon što se obave druga izračunavanja. Google algoritam najpre izračuna relevantnost stranica iz svog indeksa u odnosu na pojmove koji se koriste prilikom pretrage, potom relevantnost množi sa PR koeficijentom kako bi se dobila konačna lista. Dakle, ako je veća vrednost PR koeficijenta, stranica će biti na boljem mestu u okviru rezultata, ali još uvek postoje brojni drugi faktori koji se razmatraju, a koji su obično vezani za pozicionoranje ključnih reči na Web stranici.

PageRank kalkulator vraća rezultat koji je udeo PageRank-a za svaku stranicu i nije jednak vrednostima u Google toolbar-u.

Literatura uredi

Uticaj Google-a na svakodnevni život, Jelena Hadži-Purić, Matematički fakultet, Beograd
PageRank Wikipedia
Google's PageRank

Spoljašnje veze uredi

Matematički fakultet Beograd

PageRank kalkulator