Пејџ ранк

Ранг веб страница (енгл. PageRank) је Google-ова патентирана технологија која показује популарност wеб странице, а не wеб сајта у целости како се погрешно мисли. Да би wеб страница добила PR потребно је да нека друга страна линкује ка њој и на тај начин јој “преноси” део свог PR-а. Сви спољни линкови једне странице деле PR, тако да за максималне резултате треба тежити ка томе да се постави линк на страници са високим PR-ом и малим бројем излазних (спољних) линкова. Мноштво излазних линкова обара PR. Што се тиче броја долазећих линкова, што их је више, то је боље. И још нешто говори алгоритам: непостајање долазећих линкова може да има негативан утицај на PR коефицијент странице на коју се указује (најгори случај је да нема никакав утицај).

PR су у оригиналу формулисали Sergey Brin и Larry Page у свом раду The Anatomy of a Large-Scale Hypertextual. Заснован је на премиси да у академском свету значај истраживачког рада се процењује на основу броја цитата које рад има у другим истраживачким радовима.

Sergey Brin и Larry Page су као прву верзија интернет претраживача развили BackRub. Та верзија оцењена је врло похвално од колега са универзитета и позитивне критике почеле су да циркулишу интернетом. С обзиром на то да су кубурили са новцем, Лари је потребан хардвер склапао од јефтиних компоненти (први штампач имао је кућиште од Лего коцкица). С обзиром на све већи број wеб страница које су смештали у своју базу података и све шири круг корисника, Сергеј и Лари никад нису имали довољно рачунара и пратеће опреме.

PR не расте линеарно, то је логаритамска функција. (Зато су вредност PR1-PR10). Зато је неупоредиво лакше стићи од PR1 до PR6 него од PR6 до PR7. PR који видимо на Google Toolbaru за IE, или PageRank Status екстензији за FireFox је само апроксимација праве вредности која чак и не мора бити тачна, јер се Toolbar PR не упдате-ује редовно. Зато га не треба прихватати као релевантног.

Најчешћа заблуда везана за PR јесте да он директно утиче на рангирање wеб стране у претрагама. Та заблуда нагони многе wебмастере да усмере сву енергију у повећање PR-а у жељи да се што боље рангирају. Нажалост, PR је само један од фактора који утичу на SERP-ove Googla. Други аспекти се одређују на основу алгоритма за рангирање страница.

Временом су се SEO компаније извештиле у повећању PageRank-а на начине који већ почињу да доводе у питање вредност ове технике, те ју је Google у једном од својих патената додатно рафинирао. Наиме, иницијално добијени резултати претраге сада се додатно вреднују на основу њихове међусобне повезаности, то јест документи из првобитног сета резултата добијају на вредности уколико други документи из истог сета имају линк на њих.

Историја

Идеја о формулацији проблема линк анализе као карактеристичне вредности вероватно је прво предложена 1976. од стране Gabriel Pinski и Francis Narin. PageRank су развили Larry Page и Sergey Brin 1996. на универзитету Станфорд као део истраживачког пројекта о новој врсти претраживача. Sergey Brin је имао идеју да информација на веб-у може бити уређена у хијерархију по "популарности линка" : страна је више рангирана ако постоји више линкова на њу. Коаутори су били Rajeev Motwani and Terry Winograd . Први запис о пројекту, који описују PageRank и иницијални прототип Google претраживача је издат 1998. , кратко након што су Page и Brin основали Google Inc. , компанију која стоји иза Google претраживача.

Назив "PageRank" потиче од имена Larry Page , као и концепт веб страна. Међутим, патент је додељен Станфорд универзитету, а не Google-у. Google има ексклузивно лиценцирана права на патент, додељена од Станфорд универзитета. Универзитет је примио 1,8 милиона акција од Google-а у замену за коришћење патента; акције су продате 2005. године за 336 милиона долара.

PageRank су развили Eugene Garfield и Massimo Marchiori у 1950-им годинама. Jon Kleinberg је 1998. године издао важан рад о HITS , када је и PageRank представљен. Оснивачи Google-а цитирају Garfield-а, Marchiori-а, и Kleinberg-а у својим оригиналним радовима.

Једноставан алгоритам

Претпоставимо да имамо 4 веб стране A,B,C и D . Линкови страница на њих саме, или вишеструки линкови са једне на другу страницу су игнорисани. PageRank је иницијализован на исту вредност за све странице. У оригиналној форми PageRank-а, збир PageRank-а кроз све странице је укупан број страна на вебу у то време, па свака страница има иницијалну вредност 1. Међутим, касније везије PageRank-а, и остатак ове секције, претпостављају вероватноћу дистрибутивности између 0 и 1. Одатле иницијалне вредности за сваку страницу су 0.25 .

PageRank прелази од задате странице на страницу на коју води линк до следеће итерације, подељен је једнако између свих линкова. Ако су једини линкови били од B,C и D до А, сваки од њих би пребацио 0.25 PageRank-а на А до следеће итерације, што је укупно 0.75 .

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

Претопставимо да страна B има линк на C и A, страна C на страну А, и страна D има линкове на све стране. Тако, у првој итерацији, B пребацује половину своје постојеце вредности, тј. 0.125 страни А и другу половину страни C. Страна C би пребацила целу своју вредност, тј. 0.25 , страници А. Пошто D има три линка, она пребацује трећину своје вредности, што је приближно 0.083, на А. После ове итерације, страна А ће имати PageRank 0.458 .

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

Другим речима, PageRank који је поверен страни на коју линк показује је једнак PageRank-у те стране подељен са бројем линкова које та страна има (L( ))

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

У општем случају, вредност PageRank-а за сваку страницу u може се изразити као:

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

PageRank MATLAB/Octave имплементација

% Параметар 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

Пример позива ранг функицје, горе дефинисане:

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)

Овај пример има 13 итерација до конвергирања.

Закључак

Можда је прецизније рећи да PR алгоритам се примењује на резултате Google претраге након што се обаве друга израчунавања. Google алгоритам најпре израчуна релевантност страница из свог индекса у односу на појмове који се користе приликом претраге, потом релевантност множи са PR коефицијентом како би се добила коначна листа. Дакле, ако је већа вредност PR коефицијента, страница ће бити на бољем месту у оквиру резултата, али још увек постоје бројни други фактори који се разматрају, а који су обично везани за позиционорање кључних речи на Wеб страници.

PageRank калкулатор враћа резултат који је удео PageRank-а за сваку страницу и није једнак вредностима у Google toolbar-у.

Литература

• Утицај Google-а на свакодневни живот, Јелена Хаџи-Пурић, Математички факултет, Београд
• PageRank Wikipedia
• Google's PageRank

Спољашње везе

Математички факултет Београд

PageRank калкулатор