Modelul matematic
Web-ul e un graf orientat G = (V, E). PageRank-ul e distributia stationara a unui lant Markov pe acest graf, unde probabilitatea de tranzitie de la pagina i la j e 1/L(i) daca exista link, altfel 0.
Formula PageRank
PR(A) = (1-d) + d · Σ(PR(v)/L(v))
d = 0.85 (damping factor). Simuleaza probabilitatea ca un utilizator sa continue sa navigheze (vs. sa sara la o pagina aleatoare).
Implementare ca vector propriu
PageRank e vectorul propriu principal al matricei Google: G = d·M + (1-d)/n · E
unde M e matricea de adiacenta normalizata. Se rezolva prin metoda puterii (power iteration), care converge in ~50-100 de iteratii pentru miliarde de pagini.
Teleportarea
Damping factor-ul rezolva problema dead-end-urilor (pagini fara linkuri) si a spider trap-urilor (cicluri infinite). Fara teleportare, lantul Markov n-ar fi ergodic.