il PageRank di Google - Immagini e Appunti sul calcolo ricorsivo per capire meglio cos'è

Avvertenza: può essere utile smaltire questo lungo post utilizzando la versione in pdf (spero gradita!)
il PageRank di Google - Immagini e Appunti sul calcolo ricorsivo per capire meglio cos'è

Qualche tempo fa ho trovato su SEOmoz un interessante post che spiegava il PageRank di Google con delle immagini molto ben fatte. Siccome l'argomento mi interessa e (forse anche per pigrizia) non ho trovato delle pagine in Italiano che lo descrivono allo stesso modo, mi sono preso la briga di riprenderle traducendone il contenuto e di inserirle in una presentazione che pubblico di seguito.

Poi, siccome mi sto da un po' di tempo dedicando alla lettura del libro Google PageRank and Beyond - The science of Search Engine Rankings di Langville e Meyer, ho pensato, per completezza, di riportare da tale libro, in un modo che sia il più accessibile possibile (anche se mi rendo conto che occorrono delle basi di Matematica), la parte introduttiva alla teoria che c'è dietro la formula ed il conseguente calcolo dell'invenzione di Brin e Page.

Questo lavoro è propedeutico ad un piccolo studio che avrei in mente di fare di cui vi do un cenno alla fine del post.

Buona lettura!

| View | Upload your own

La formula che calcola il PageRank di una determinata pagina Web è una formula ricorsiva. Una formula, cioè, che necessita di più di una iterazione perchè produca un risultato affidabile. In gergo si dice che la formula converge verso un risultato. Chi è programmatore può pensare ad un processo ricorsivo come a quello che si può innescare con un ciclo di if annidati con un indice n...In teoria la convergenza la si avrebbe per un numero infinito di iterazioni ma, dato che siamo nel mondo reale, di iterazioni ne vengono fatte in un numero finito per arrivare ad un valore che approssima di parecchio quello che, invece, si avrebbe nel...mondo delle favole!

La formula per il calcolo del PageRank è quella della figura che segue:


Non è necessario, ai fini della trattazione, dire troppo su questa formula perchè le cose si chiariranno in seguito: per ora è sufficiente notare che la formula dice che il PageRank di una data pagina calcolato all'iterazione k+1 è la somma dei PageRank delle pagine che sono linkate a quella in esame calcolati al passo k messi poi in rapporto con il numero dei link che quelle pagine hanno in uscita. Trova riscontro, quindi, il concetto di Passable PageRank delle slides.

Per modellare meglio il calcolo del PageRank delle pagine Web, intese proprio come nodi tra di loro linkati, si fa ricorso alla teoria delle Matrici. Senza voler scendere nel particolare basti pensare che, invece di effettuare tante somme di prodotti per quante sono le pagine, con le matrici è possibile eseguire una sola operazione con una drastica riduzione del tempo di calcolo. Sempre che, ovviamente, si possa contare su risorse ad hoc!


Ogni elemento non nullo della riga j in posizione i della matrice ottenuta corrisponde ai link in uscita dal nodo j verso il nodo i; ogni elemento non nullo della colonna k in posizione l rappresenta i link in ingresso al nodo k dal nodo l. Uno zero rappresenta l'assenza, per il relativo nodo, di link in ingresso e link in uscita.

Sulla matrice H si possono fare almeno un paio di osservazioni:

(1) Una matrice riferita ad un sistema di n nodi (n pagine Web) porta nella generalità dei casi ad una complessità computazionale, per ciascuna iterazione (calcolo matriciale), che è funzione del quadrato del numero di nodi considerati (chiamiamo n questo numero). Se si pensa al numero di siti Web che ci sono si arriva ad un valore spaventoso!

(2) La matrice H è però una matrice sparsa: ha, cioè, diversi elementi nulli. Questo perchè le pagine sono linkate solo ad un numero (di gran lunga inferiore ad n) di altre pagine facenti parte dell'insieme complessivo. La cosa riduce di molto la complessità di calcolo e la porta ad essere funzione del quadrato di un numero molto minore di n.

Il calcolo, avendo considerato il formalismo delle matrici, può essere più comodamente espresso come appare nella formula in basso:

A questo punto gli autori del libro pongono alcune questioni:

(i) il processo iterativo del calcolo del PageRank continua all'infinito oppure è un processo che converge ad un numero?

(ii) sotto quali ipotesi o proprietà la matrice converge?

(iii) il calcolo converge in qualcosa che abbia senso?

(iv) il calcolo converge ad un unico valore o a valori multipli?

(v) il valore di convergenza dipende dal PageRank al passo zero di iterazione?

(vi) quante iterazioni sono necessarie per approssimare il valore di convergenza?

Le risposte a queste domande dipendono strettamente dalle ipotesi che i nostri Brin e Page fecero agli albori della loro invenzione. Diversi sarebbero, infatti, i problemi se la matrice di Google (quella su cui davvero si basa il calcolo del PageRank) fosse effettivamente la matrice H.

La matrice H è quella che forse meglio rappresenta la realtà del sistema di nodi (cioè dei siti); tale realtà è quella che Google si costruisce tramite la scansione che periodicamente fa del Web. Se però si pensa al fatto che nel web ci sono nodi che non hanno link in uscita (i cosiddetti dandling node che creano il problema del rank sinks) o che si linkano solo reciprocamente (problema dei cicli) si capisce quanto complicato (o, per meglio dire, impossibile) sarebbe fabbricarsi una matrice tale da rendere velocemente convergente il calcolo del PageRank.

Per tale ragione Brin e Page pensarono a dei fattori correttivi con l'obiettivo di conferire, a quella che poi sarebbe diventata la Matrice di Google, le proprietà in grado di garantire una rapida convergenza del processo iterativo. Tali fattori dovevano rispecchiare il comportamento di quello che i nostri eroi chiamano il Random Surfer.

Il Random Surfer, quando entra in un dandling node, esce verso un qualsiasi altro nodo scelto in modo del tutto casuale (random, per l'appunto). Questo è il motivo per cui, alla originaria matrice H, gli elementi nulli delle righe associati a nodi che non hanno link in uscita, sono stati sostituiti con l'inverso del numero totale di nodi del Web (cioè 1/n). Dato però che questa modifica da sola non sarebbe bastata a garantire la convergenza del calcolo, è stato aggiunto un altro fattore correttivo, il parametro alfa, un numero compreso tra 0 e 1, che rappresenta la probabilità con cui il Random Surfer segue la struttura naturale dei link (indipendentemente dal suo ritrovarsi a fare i conti con un dandling node oppure no) durante la scansione del Web.

Il Random Surfer, insomma, nella sua scansione della rete può decidere in qualsiasi momento (e con una probabilità pari ad alfa) di non seguire più la naturale struttura dei link. Il Random Surfer, però, trovandosi in un nodo senza uscita, salterebbe comunque verso un altro nodo. Il nodo scelto dal Surfer sarebbe, in questo caso, estratto a sorte da un'urna contenente tutti i nodi del web.

Con queste ipotesi si arriva alla fomulazione delle Matrice di Google, la matrice G che poi è quella che compare nella formula adottata da Brin e Page per il calcolo del PageRank.



Nella equazione della matrice G compare un vettore, il vettore a, che, in posizione j ha un 1 se il nodo j è un dandling node.

Nel libro citato si dice che il numero di iterazioni necessarie per avere la convergenza con una buona approssimazione al PageRank dei nodi (pagine) del sistema complessivo (Web) è pari a 50 avendo considerato un parametro alfa pari a 0.85 che pare sia quello adottato ancora adesso da Google. Tale valore è un compromesso tra la velocità di convergenza e l'accuratezza del valore ottenuto dopo l'ultima iterazione. Ovviamente più il numero è alto e maggiore è l'affidabilità del risultato da pagare, però, con diversi giorni di computazione!

Riprendiamo adesso le domande erano state poste in precedenza. A gran parte di esse Brin e Page hanno dato una risposta. Per rispondere qualche altra occorrerà fare delle ulteriori ipotesi.

(i) il processo iterativo del calcolo del PageRank continua all'infinito oppure è un processo che converge ad un numero?
Abbiamo visto che il processo iterativo può convergere ad un numero senza che debba durare al'infinito.

(ii) sotto quali ipotesi o proprietà la matrice converge?
Le ipotesi sono quelle di applicare dei parametri di tipo probabilistico che modellino il comportamento del Randm Surfer (probabilità di seguire la struttura dei link e probabilità equa di saltare ad un qualsiasi nodo quando si trova di fronte ad un dandling node).

(iii) il calcolo converge in qualcosa che abbia senso?
Si, il calcolo converge ad un valore prossimo a quello che si avrebbe con infinite iterazioni.

(iv) il calcolo converge ad un unico valore o a valori multipli?
Sembrerebbe, per quanto detto finora, di si. Anche se... La chiave di tutto sta in quel numero (1/n) che esprimerebbe il carattere democratico di Google: l'equiprobabilità con cui ciascun nodo potrebbe essere ragiunto dal Surfer in caso di assenza di vie d'uscita durante la scansione. Al variare del numero associato a ciascun nodo, varia il PageRank dei nodi del sistema e, quindi, per rispondere alla domanda, si deve dire che il calcolo può convergere a valori multipli.

(v) il valore di convergenza dipende dal PageRank al passo zero di iterazione?
Certamente si!

(vi) quante iterazioni sono necessarie per approssimare il valore di convergenza?
Come detto il numero di iterazioni è pari a 50 ma è dipendente dal parametro alfa. Nel libro citato si dimostra che si passa da un valore di 34 iterazioni per alfa pari a 0.5 fino a 23015 iterazioni per un alfa pari a 0.999.

Per adesso mi fermo qui. Nelle prossime settimane (con il tempo necessario che sarò riuscito a ritagliarmi per questo studio) tornerò sull'argomento; gli autori del libro mettono a disposizione dei piccoli programmi di simulazione di calcolo del PageRank che mi piacerebbe applicare per cercare di rispondere ad alcune domande che mi vado ponendo da un po'.Due in particolare:

quanto bene fa un link in uscita al (proprio) PageRank?
Come potrebbe essere gestito in modo diverso il parametro 1/n applicando un sistema a punteggi tipico del Social Bookmarking?

Volete aiutarmi?
O avete già le risposte?

il PageRank di Google - Immagini e Appunti sul calcolo ricorsivo per capire meglio cos'è