Cheatsheet — PageRank

Snelle referentie. Klap open wat je nodig hebt. De slides van het college staan bij het idee.

Het idee

In één zin

Een pagina is belangrijk als er belangrijke pagina's naar linken. Links zijn stemmen, en omdat dat rondjes draait, reken je in rondes tot de waarden niet meer veranderen.

De formule

De update-regel

rank(p) = (1 − d)/N  +  d · Σ  rank(i) / aantal_links(i)
                              i → p

• d = damping factor, gewoonlijk 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 = {}
    for p in web:
        rank[p] = 1 / n
    while True:
        nieuw = {}
        for p in web:
            som = 0.0
            for i in web:
                if p in web[i]:
                    som += rank[i] / len(web[i])
            nieuw[p] = (1 - d) / n + d * som
        verschil = 0.0
        for p in web:
            verschil = max(verschil, abs(nieuw[p] - rank[p]))
        rank = nieuw
        if verschil < epsilon:
            return rank

Belangrijke punten

Damping, convergentie, som

• Damping (d = 0,85): de surfer loopt nooit voorgoed vast, en elke pagina blijft bereikbaar.
• Stoppen: elke ronde veranderen de waarden minder. Stop zodra de grootste verandering kleiner is dan epsilon.
• De som van alle ranks blijft (ongeveer) 1. Lees een rank als de kans dat de random surfer op die pagina is.
• Reken een ronde altijd uit de ranks van de vorige ronde.

Dangling nodes

Een pagina zonder uitgaande links laat belang weglekken. Doe daarom alsof zo'n pagina naar alle pagina's linkt.

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

Twee invalshoeken

Formule ↔ random surfer

De formule rekent uit waar een eindeloze surfer op de lange duur terechtkomt. De simulatie laat de surfer heel vaak klikken, telt waar hij was, en komt op bijna dezelfde waarden uit.