Algoritmus PageRank

Pôvodný algoritmus PageRank ako bol uverejnený jeho tvorcovia.
PR (A) = (1-d) + d (PR (Ti) / C (Ti) + ... + PR (Tn) / C (Tn))
kde

• PR (A) je PageRank stránky A,
• PR (Ti) je PageRank stránok Ti, ktoré odkazujú na A,
• C (Ti) je počet odchádzajúcich odkazov na stránke Ti
• d je faktor tlmenia (damping factor), ktorý je medzi 0 a 1

V súčasnosti nie je aktuálny PageRank známy, takže o jeho nastavenia alebo tvare sa vedú len dohady. Mal by však vychádzať z princípov tejto rovnice.

---

Charakteristika PageRank

Ako PageRank funguje sa dá ukázať na príklade, ktorý je uvedený na nemeckej stránke eFactory Uvažujeme o malom webe s tromi stránkami A, B a C, kde stránka A odkazuje na B a C, stránka B odkazuje na C a stránka C odkazuje na A. Podľa pôvodnej verzie mal byť faktor útlmu na 0,85. Ale aby sa to dalo ľahko spočítať použijeme 0.5.

Po doplnení dostaneme nasledujúce rovnice:

• PR (A) = 0.5 + 0.5 PR (C)
• PR (B) = 0.5 + 0.5 (PR (A) / 2)
• PR (C) = 0.5 + 0.5 (PR (A) / 2 + PR (B))

Tieto rovnice idú jednoducho vyriešiť a tu sú výsledky:

• PR (A) = 14/13 = 1.07692308
  
• PR (B) = 10/13 = 0.76923077
  
• PR (C) = 15/13 = 1.15384615
  

Suma všetkých PageRank je 3, a tak sa rovná počtu všetkých webových stránok. V praxi je to trochu zložitejšie, pretože web má miliardy stránok, takže nájsť riešenie nie je tak jednoduché. Práve kvôli veľkosti webu nielen Google používa približný odhad PageRank. Každá stránka dostane na začiatku počiatočnú hodnotu a PageRank ostatných sa dopočítava v niekoľkých výpočtových cykloch, ktoré sú založené na základnej rovnici algoritmu PageRank. Pre náš príklad použijeme počiatočnú hodnotu 1.

Tabuľka : Cykly odhadu Google PageRank

Zdroj:http://pr.efactory.de

Kvalitný odhad PageRank možno dosiahnuť len po pár opakovaniach. Podľa Lawrenca Pagea a Sergeya Brina je potrebné vykonať aspoň 100 opakovaní, aby sme dostali dobrý odhad hodnôt PageRank celého webu. To tiež znamená, že súčet všetkých PageRank sa stále blíži k celkovému počtu webových stránok. Priemerný PageRank je rovný 1. Minimálny PageRank je daný (1-d). Maximálna PageRank môžeme dostať ak by všetky stránky odkazovali na jedinú a tá by odkazovala sama na seba. Hodnota by potom bola rovná dN + (1-d), kde N je celkový počet stránok.