Ga naar hoofdinhoud

13.11 Cheatsheet — PageRank

Snelle referentie. Klap open wat je nodig hebt. Het college staat op stap 1 (de slides).

Het idee​

In één zin

Een pagina is belangrijk als er belangrijke pagina's naar linken; links zijn stemmen, en je lost het circulaire karakter op door te itereren tot de waarden stabiel zijn.

De formule​

De update-regel
rank(p) = (1 − d)/N  +  d · Σ  rank(i) / aantal_links(i)
                              i → p
  • d = damping factor (meestal 0,85)
  • N = aantal pagina's
  • (1 − d)/N = basisdeel: de surfer springt soms willekeurig
  • de som loopt over alle pagina's i die naar p linken

De functie​

De iteratieve implementatie
def pagerank(web, d=0.85, epsilon=1e-9):
    n = len(web)
    rank = {p: 1 / n for p in web}
    while True:
        nieuw = {}
        for p in web:
            som = sum(rank[i] / len(web[i]) for i in web if p in web[i])
            nieuw[p] = (1 - d) / n + d * som
        verschil = max(abs(nieuw[p] - rank[p]) for p in web)
        rank = nieuw
        if verschil < epsilon:
            return rank

Belangrijke punten​

Damping, convergentie, som
  • Damping (d = 0,85) houdt het stabiel: de surfer loopt nooit definitief vast en elke pagina blijft bereikbaar.
  • Convergentie: elke iteratie verandert minder; stop als de grootste verandering kleiner is dan een kleine epsilon.
  • De som van alle ranks blijft (ongeveer) 1 — je kunt rank lezen als "kans dat de random surfer hier is".
  • Reken een ronde altijd uit de ranks van de vorige ronde.
Dangling nodes

Een pagina zonder uitgaande links laat anders belang "weglekken". Oplossing: behandel hem alsof hij naar alle pagina's linkt.

links = web[i] if web[i] else set(web)

Twee invalshoeken​

Formule ↔ random surfer

De iteratieve formule rekent PageRank exact uit. De random surfer-simulatie (veel klikken tellen) benadert dezelfde waarden. Het zijn twee kanten van hetzelfde idee: waar komt een eindeloze surfer op de lange termijn terecht?

Klaar. Je hebt PageRank van idee tot werkende code gebouwd — en gezien waarom links méér zijn dan een telling.