Algoritmi di Page Ranking

Come funziona un motore di ricerca per cercare le pagine più attinenti? Qual è l'attuale matematica che c'è dietro?

Il page rank è calcolato in base alla importanza della pagina. Ma come si deve definire l'importanza di una pagina?

Ci possono essere vari modi:
1) in base al numero di volte che la parola compare
2) in base al numero di link che da essa partono
3) in base al numero di link che ad essa arrivano
4) in base al numero di pagine valutate importanti che puntano alla pagina

L'idea di Brin e Page di Google è legata proprio al quarto punto di sopra, che offre maggiori risultati.

Il concetto è semplice: una pagina è importante per le pagine importanti che vi puntano e non tanto per una parola, magari presente una sola volta, e da noi ricercata. Una pagina importante, quindi, da valore ad una pagina a cui punta; per cui l'importanza di una pagina è la somma delle frazioni di importanza che le trasferiscono le pagine che ad esso puntano.

Supponiamo di numerare le pagine web da 1 a n. Avremo una matrice di connettività H (nxn), dove hij è l'elemento generico della matrice H,  di riga i e colonna j . Ora hij=1 se esiste un link dalla pagina i alla pagina j; mentre hij=0 se non esiste il link e se i=j hii=0 perchè una pagina non punta a sè stessa. Supponiamo n=4, ovvero 4 pagine web.

Una matrice H potrebbe ad esempio avere:
h11=0    h12=1    h13=1    h14=1
h21=1    h22=0    h23=0    h24=1
h31=0    h32=0    h33=0    h34=1
h41=0    h42=1    h43=1    h44=0

Se sommiamo gli 1 su una riga otteniamo ri, cioè il numero di link (che è un dato noto). Chiamiamo con xj l'importanza della pagina; per cui è:

xj = h1j * x1/r1 + h2j * x2/r2 + ... + hnj * xn/rn  per j=1..n   (1)

La (1) è un sistema di equazioni lineare in n incognite xi che rappresentano l'importanza delle pagine. Google usa una equazione leggermente differente:

xj = d(h1j * x1/r1 + h2j * x2/r2 + ... + hnj * xn/rn) * 1/n * (1-d)  per j=1..n   (2)

dove d è un parametro nell'intervallo (0,1); di solito si usa d=0,85. Ora un metodo di soluzione come quello di eliminazione di Gauss ha una complessità O(n^3). Se n è molto grande, la soluzione del sistema di equazioni potrebbe richiedere miliardi di anni.

Come allora avviene, visto che i motori di ricerca lo fanno? Sono stati implementati algoritmi veloci e se ne stanno cercando ancora ulteriori.

Si usa un metodo iterativo di convergenza:
1) Si fissano inizialmente dei valori qualsiasi agli xi di destra per ottenere xj di sinistra nella (2),
2) Si ripete il passo 1 stavolta col valore xj trovato mettendolo a destra della (2) e, per successive approssimazioni (ripetendo i passi 1 e 2), si converge alla soluzione finale  xi(1), xi(2), ..., xi(k) -> xj

Questa è una tecnica usata anche per lo studio dei campi elettrici, magnetici etc.

L'errore che si commette e(k) = max|xi(k) - xi| ed è tale che: e(k) <= lambda(k)   0 < lambda < 1
Purtroppo più grande è d nella (2) più lambda è grande e più lenta è la convergenza. La (2) ha anche una sua giustificazione probabilistica; xj rappresenta la probabilità che una pagina venga visitata ritenendo equiprobabili i link che una persona sceglie sulla  pagina: d è la probabilità che la persona scelga un link offerto dalla pagina e 1-d se ne sceglie un altro.

Dietro a tutto questo c' è la teoria delle catene di Markov e delle matrici non negative che forniscono
l'esistenza e l'unicità della soluzione xj.

Oggi allo studio ci sono molti altri problemi importantissimi:
- trovare metodi più veloci affinchè le successioni convergano più velocemente

•   successioni di Krylov
•   metodi del gradiente o delle differenze finite
•   etc

- studiare modelli più complessi dove non c'è l'equiprobabilità
- studiare i valori migliori assumibili da lambda

Alla prox