Progetto Lauree Scientifiche 2010-2011:
Come funziona Google?
Liceo ”Gabriele D’Annunzio” di Fidenza Università degli Studi di Parma
Docenti della scuola superiore:
M. Armani, S. Di Maiolo Docenti dell’università:
M. Belloni, C. Medori Studente del tirocinio:
E. Pini
Introduzione: i motori di ricerca e la scelta di Google
In principio abbiamo concentrato la nostra attenzione sul funzionamento di un motore di ricerca, con particolare attenzione al più popolare ed utilizzato tra questi:
Google.
Abbiamo scoperto che l’azione del motore di ricerca si suddivide in tre fasi:
- l’analisi del web, con la scansione delle pagine che lo compongono e la raccolta delle relative informazioni in un database;
- la determinazione di una gerarchia di importanza tra le pagine presenti nel database;
- la risposta alle richieste degli utenti: in seguito all’inserimento di una o più parole chiave all’interno dell’apposita barra di ricerca, il motore di ricerca fornisce un elenco delle pagine web presenti nel database che contengono le parole chiave inserite dall’utente; l’ordinamento dei risultati è effettuato se- condo la gerarchia di importanza stabilita in precedenza (nelle prime posizioni compaiono i link ritenuti più interessanti).
In particolare, Google assegna ad ogni pagina web P una misura della sua impor- tanza, nota come PageRank e denotata da I(P ). Stabilisce che una pagina è tanto più importante (cioè ha PageRank alto) quanti più sono i link verso tale pagina e quanto più sono importanti le pagine che linkano verso di essa. Abbiamo riflettu- to su come il PageRank rispecchi il concetto di popolarità proprio delle relazioni sociali umane.
La matrice di Hyperlink
Abbiamo visto che il principio alla base del Pagerank di Google viene formalizzato nel sistema lineare
I(Pi) = X
Pj∈Bi
I(Pj) lj
, i = 1, 2, . . . , n
in cui {P1, . . . , Pn} sono le pagine che costituiscono il web. Bi è l’insieme delle pagine che linkano verso la pagina Pi mentre lj è il numero di link della pagina Pj
verso altre pagine.
Abbiamo poi verificato che, indicato con I il vettore colonna avente per componenti i valori di PageRank I(Pi), il sistema lineare si può riscrivere in forma matriciale come
I = HI dove H è la cosiddetta matrice di Hyperlink :
Hij =
( 1/lj se Pj ∈ Bi
0 altrimenti
Una volta risolto il sistema lineare, cioè una volta determinata la soluzione I, è noto il Pagerank di ciascuna pagina e risulta stabilita la gerarchia di importanza delle pagine web.
Per meglio comprendere il problema, abbiamo preso in esame un semplice esempio di web costituito da n = 8 pagine:
P1
P2
P3
P4
P5
P6
P7
P8
Abbiamo osservato che:
- P1 ha l1 = 2 link, verso P2 e P3, quindi P1 passa 1/2 della sua importanza a P2 e 1/2 della sua importanza a P3;
- P2 ha l2 = 1 link, verso P4, quindi P2 passa tutta la sua importanza a P4; - P3 ha l1 = 2 link, verso P2 e P5, quindi P3 passa 1/2 della sua importanza a
P2 e 1/2 della sua importanza a P5;
- P4 ha l1 = 3 link, verso P2, P5 e P6, quindi P4 passa 1/3 della sua importanza a P2, 1/3 della sua importanza a P5 e 1/3 della sua importanza a P6;
- . . .
L’importanza di una pagina è data dalla somma di tutti i contributi dati dalle pagine che linkano ad essa. Sulla base di tali considerazioni, siamo arrivati a scrivere il sistema lineare:
I(P1) = I(P7) 3 I(P2) = I(P1)
2 + I(P3)
2 +I(P4) 3 I(P3) = I(P1)
3 I(P4) = I(P2) I(P5) = I(P3)
2 + I(P4)
3 +I(P7) 3 I(P6) = I(P4)
3 + I(P5)
3 +I(P8) 2 I(P7) = I(P5)
3 + I(P8) 2 I(P8) = I(P5)
3 + I(P6) + I(P7) 3 e quindi la matrice di Hyperlink:
H =
0 0 0 0 0 0 1/3 0
1/2 0 1/2 1/3 0 0 0 0
1/2 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1/2 1/3 0 0 1/3 0
0 0 0 1/3 1/3 0 0 1/2
0 0 0 0 1/3 0 0 1/2
0 0 0 0 1/3 1 1/3 0
Abbiamo constatato che la risoluzione del sistema lineare non è immediata, nono- stante il numero esiguo di pagine. Abbiamo quindi concluso che gli usuali metodi diretti per la risoluzione di sistemi lineari non sono utilizzabili quando le pagine
che compongono il web sono all’incirca 25 · 109 (questo è il numero di pagine che Google dichiara di indicizzare nel proprio database).
In attesa di affrontare metodi alternativi, siamo ritornati al sistema lineare scritto nella forma
HI = I
e abbiamo introdotto le nozioni di autovalore e autovettore. Questo ci ha permesso di tradurre il problema nella ricerca di un autovettore della matrice H di autovalore λ = 1.
Il metodo iterativo
Prima di proseguire, abbiamo concentrato una lezione intorno al concetto di con- vergenza. Grazie a questo abbiamo potuto prendere in considerazione la sequenza di vettori colonna definita da
( I0 scelto arbitrariamente Ik+1 = HIk, k = 0, 1, . . .
e discutere la convergenza della sequenza alla soluzione I del sistema lineare. Ab- biamo inoltre parlato di possibili scelte per il vettore I0 e ci siamo chiesti se tali scelte influenzano la convergenza della sequenza.
Ancora una volta abbiamo fatto ricorso ad esempi di web per chiarirci le idee.
Abbiamo utilizzato Derive per calcolare per ciascuno di tali web le iterate Ik (op- portunamente normalizzate in modo che la somma di tutti i valori di PageRank sia uguale a 1) e abbiamo osservato come generalmente il metodo fornisce, dopo un numero contenuto di passi, una buona approssimazione della soluzione I del sistema lineare.
Non sempre le cose funzionano..
Nelle successive lezioni abbiamo capito che quanto visto in precedenza non assicura di determinare in tutti i casi la gerarchia di importanza delle pagine.
• Abbiamo considerato il seguente web, formato da sole n = 3 pagine e quindi particolarmente semplice:
P1 P2
P3
Il sistema lineare da risolvere è
I(P1) = I(P3) 2 I(P2) = I(P1)
2 + I(P3) 2 I(P3) = I(P1)
2 e la matrice di Hyperlink risulta
H =
0 0 1/2 1/2 0 1/2 1/2 0 0
Abbiamo appurato che l’unica soluzione del sistema lineare è data dal vettore nullo, ma questa soluzione è da scartare dal momento che il vettore nullo non ci dice alcunchè circa la gerarchia di importanza delle pagine. Abbiamo capito che questa situazione è dovuta alla presenza di una pagina non linkante e che questa corrisponde ad una colonna di soli 0 nella matrice H.
Come risolvere tale problematica? Abbiamo pensato a ciò che avviene nella realtà quando si naviga nel web: qualora non sia più possibile muoversi da
una pagina ad un’altra tramite un link, si riparte da una pagina qualunque.
Questo equivale a sostituire alla colonna di soli 0 una colonna con tutte le componenti uguali a 1/n = 1/3. Si ottiene così una nuova matrice S:
S =
0 1/3 1/2 1/2 1/3 1/2 1/2 1/3 0
ed un nuovo sistema lineare:
I = SI
La matrice S gode di proprietà particolari: ha elementi tutti non negativi (così come H) e la somma degli elementi in ciascuna colonna è 1. Una ma- trice di questo tipo è detta matrice stocastica.
• Abbiamo visto che problematiche analoghe a quelle riscontrate nel caso di pagine senza link uscenti si manifestano per web del tipo
P1
P2
P3
P4
P5
P6
P7
P8
in cui è presente un sottoweb, ossia un insieme di pagine web collegate tra loro ma che non linkano a pagine al di fuori.
La matrice di Google e il teorema di Perron
Nelle ultime lezioni abbiamo appreso che Google introduce un’ulteriore modifica alla matrice di Hyperlink. Si passa così dalla matrice S (ottenuta rimpiazzando le
colonne di soli 0 della matrice H) ad una nuova matrice G data da G = αS + (1 − α)1
n1
dove 1è la matrice n × n di soli 1 ed α è un valore numerico compreso fra 0 e 1.
G è stocastica perchè combinazione di matrici stocastiche; in più i suoi elementi sono positivi. Ma perchè Google sceglie di adottare una simile matrice?
Abbiamo studiato il Teorema di Perron e abbiamo visto come questo offra una condizione sufficiente affinchè una matrice ammetta l’autovalore semplice λ = 1 ed esista un unico autovettore con componenti positive relativo a tale autovalore. La soluzione adottata da Google è quindi perturbare la matrice di Hyperlink in modo che soddisfi le ipotesi del teorema di Perron, perchè sia garantita la convergenza del metodo iterativo alla soluzione del sistema lineare e la determinazione della gerarchia di importanza delle pagine.
Abbiamo osservato come sia importante la scelta del parametro α. Infatti α = 0 ⇒ G = 1
n1
quindi scegliere α = 0 significa considerare, in luogo del web autentico, un web in cui tutte le pagine si linkano tra loro. D’altra parte
α = 1 ⇒ G = S
quindi scegliere α = 1 significa mantenere inalterata la matrice di Hyperlink, con le eventuali problematiche che si possono presentare. Abbiamo quindi valutato importante scegliere per α un valore vicino a 1 per tenere in buona considerazione l’originaria struttura del web. Abbiamo infine scoperto che Google adotta il valore α = 0.85.
Link utili
D. Austin, How Google Finds Your Needle in the Web’s Haystack : http://www.ams.org/samplings/feature-column/fcarc-pagerank
M. A. Garuti, Google, ovvero: come diagonalizzare Internet:
http://www.math.unipd.it/∼mgaruti/google.pdf
E. Morini, Il metodo del PageRank: l’origine del successo di Google:
http://poisson.phc.unipi.it/∼morini/tesina_web.pdf
