Il Pagerank `e solo una parte del sistema di ranking di Google, infatti `e combi- nato con altri punteggi al fine di ottenere un ranking completo e globale. Per semplificare gli esempi presentiamo un modello base per l’uso del Pagerank costituito da due passi principali: nel primo passo si determina il sottoinsie-
1Una catena di Markov `e NCD se lo spazio degli stati pu`o essere suddiviso in sottoinsie- mi disgiunti con forti interazioni fra gli stati di un sottoinsieme ma con deboli interazioni fra i sottoinsiemi stessi. La matrice di transizione di una catena NCD pu`o essere riordinata in modo da essere una matrice a blocchi dove i blocchi sulla diagonale sono densi mentre quelli fuori dalle diagonali sono sparsi.
2.3. ALGORITMI 33
me di nodi che contengono i termini della query, chiamato sottoinsieme di rilevanza per la query; nel secondo passo l’insieme di rilevanza `e ordinato secondo i valori dei Pageranks di ciascun documento dell’insieme, quindi os- serviamo che il vettore Pagerank non dipende dalla query. Il calcolo di tale vettore `e costoso e richiede molto tempo in quanto bisogna trovare il vettore stazionario di una matrice stocastica ed irriducibile le cui dimensioni sono dell’ordine di miliardi ed il metodo delle potenze sembra essere il metodo scelto da Google. L’algoritmo per calcolare il vettore Pagerank r per la ma- trice di Google A = αP + (1 − α)ee
T
n presenta diverse varianti. Innanzitutto osserviamo che, nella pratica, la matrice di adiacenza non viene quasi mai utilizzata. Ad essa si preferisce la matrice di connettivit´a G cos´ı definita:
gi,j =
(
1 se c’`e un link da pagina j a pagina i , 0 altrimenti .
`
E evidente che `e pi`u facile costruire questa matrice rispetto a quella di adia- cenza. La matrice G sar`a una matrice sparsa ovvero una matrice i cui elementi saranno soprattutto zeri.
Esempio 2.3.1. Vediamo come costruire in Matlab la matrice di connettivit´a relativa alla seguente porzione di web:
Possiamo generare la matrice specificando la coppia di indici (i, j) di elementi non zero. Poich`e c’`e un link da alpha.com a beta.com l’elemento (2, 1) di G `e non zero. Procedendo allo stesso modo con le altre connessioni i due vettori i e j avranno la seguente forma:
i = [ 2 6 3 4 4 5 6 1 1]; j = [ 1 1 2 2 3 3 3 4 6];
In questo caso la nostra matrice 6 × 6 ha 27 zeri e solo 9 elementi diversi da zero. L’istruzione
n = 6;
G = sparse(i,j,1,n,n);
genera una rappresentazione sparsa di una matrice n × n con 1 nelle posizioni specificate dai vettori i e j.
Partendo dalla matrice di connettivit`a G, il modo migliore per scrivere in Matlab la matrice di Google A `e il seguente:
A = pGD + ezT , (2.8)
dove D `e la seguente matrice diagonale di elementi
dj,j = 1 cj se cj 6= 0 0 se cj = 0 ,
con c vettore riga le cui componenti sono la somma degli elementi di G per colonne, e `e il vettore colonna di tutti 1, p = α = 0.85 e z `e il vettore di componenti zj = (1 − p) n se cj 6= 0 1 n se cj = 0 .
Precisiamo che le due espressioni (2.6) e (2.8) sono equivalenti, cio`e la matrice che viene creata `e la stessa. A questo punto possiamo applicare il metodo
2.3. ALGORITMI 35
delle potenze: definiamo un iterato iniziale r(0) = e
n, dove n `e la dimensione della matrice G, e iteriamo
r(k+1) = Ar(k) (k ≥ 0)
finch`e non si raggiunge il grado di convergenza desiderato, ovvero finch`e la norma della differenza fra gli ultimi iterati generati, r(k+1) ed r(k), non `e
minore di una tolleranza fissata (per esempio 10−2). Ovviamente non si me- morizzano tutti gli iterati r(0), r(1), r(2), . . . ma ad ogni passo si memorizzano solo gli ultimi due iterati generati, r(k−1) ed r(k), ed al passo successivo si sovrascrivono con r(k) ed r(k+1). Tuttavia applicare il metodo delle potenze
in modo convenzionale come abbiamo fatto ora non `e la scelta migliore in quanto la creazione della matrice A ed il prodotto matrice-vettore Ar(k), che
va calcolato ad ogni passo, sono molto costosi. Il metodo delle potenze pu`o anche essere implementato in modo da non costruire la matrice di Google A. Prima di tutto si modifica la matrice di connettivit`a G in questo modo:
G = p G D , poi si considera l’iterato iniziale r(0) = e
n e si ripete l’istruzione r(k+1)= Gr(k)+ e(zr(k)) (k ≥ 0)
finch`e la norma della differenza fra gli iterati r(k+1) ed r(k) non `e minore di
una tolleranza fissata. Questa implementazione ha due aspetti positivi: si preserva la sparsit`a delle matrici e la moltiplicazione matrice-vettore Gr(k)
richiede solo prodotti scalari sparsi quindi `e poco costosa. Questi prodotti scalari sparsi possono facilmente essere implementati in parallelo e l’uso del calcolo parallelo `e imperativo per problemi di queste dimensioni. Ci sono sta- ti recenti progressi nel calcolo e nell’implementazione del Pagerank, proposti per la maggior parte da ricercatori di Stanford. Arasu e alunni suggeriscono l’uso del metodo di Gauss-Seidel al posto del semplice metodo delle potenze, mentre Kamvar e alunni hanno sviluppato diverse modifiche al metodo delle potenze per accelerare la convergenza. Una tecnica usa l’estrapolazione qua- dratica per velocizzare la convergenza al vettore Pagerank.
Il modo migliore di calcolare il vettore Pagerank in Matlab `e considerare la particolare struttura della matrice di Google A [7]. L’equazione r = Ar pu´o essere scritta come:
(I − pGD)r = γe dove γ = zTr .
Il valore di γ non si conosce in quanto dipende dal vettore r che `e sconosciuto ma possiamo considerare γ = 1. Se p `e strettamente minore di 1 la matrice dei coefficienti I − pGD `e non singolare e l’equazione
(I − pGD)r = e
pu`o essere risolta in r. In conclusione il vettore Pagerank `e dato dalla soluzio- ne, tramite l’eliminazione di Gauss, di un sistema lineare sparso e pu`o essere scalato in modo tale che P
iri = 1. Notiamo che in questa implementazione
il vettore z non `e minimamente coinvolto. `
E possibile usare anche un algoritmo chiamato iterazione inversa [7]. Per prima cosa si costruisce la matrice di Google in questo modo:
A = p G D + 1 − p n e poi si risolve il sistema lineare
(I − A)r = e .
Ad una prima occhiata questa idea potrebbe sembrare pericolosa poich`e la matrice (I − A) `e in linea teorica singolare, ma grazie agli errori di arroton- damento `e molto probabile che la matrice calcolata non lo sia, infatti, anche se inizialmente la matrice `e singolare, gli errori di arrotondamento che inter- vengono nell’eliminazione di Gauss fanno s`ı che gli elementi diagonali siano difficilmente degli zeri esatti. Inoltre l’algoritmo di eliminazione di Gauss con pivoting per colonne produce una soluzione con un residuo piccolo anche se la matrice risulta mal condizionata. Il vettore r ottenuto con l’operazione
2.3. ALGORITMI 37
generalmente ha componenti grandi e se viene scalato in modo tale che P
iri = 1 il residuo risulta scalato del medesimo fattore e diventa molto
piccolo. Di conseguenza, i due vettori x e Ax risultano uguali a meno di un errore di arrotondamento.
Ora applichiamo questi quattro algoritmi al grafo dell’esempio (2.3.1) e con- frontiamo i quattro vettori Pagerank ottenuti.
---POTENZE CONVENZIONALE---
page-rank in out url
1 0.3177 2 2 alpha 6 0.2018 2 1 sigma 2 0.1702 1 2 beta 4 0.1383 2 1 delta 3 0.1067 1 3 gamma 5 0.0652 1 0 rho
----POTENZE MATRICI SPARSE----
page-rank in out url
1 0.3177 2 2 alpha 6 0.2018 2 1 sigma 2 0.1702 1 2 beta 4 0.1383 2 1 delta 3 0.1067 1 3 gamma 5 0.0652 1 0 rho ---SISTEMA LINEARE---
page-rank in out url
1 0.3210 2 2 alpha 6 0.2007 2 1 sigma 2 0.1705 1 2 beta 4 0.1368 2 1 delta 3 0.1066 1 3 gamma 5 0.0643 1 0 rho ---ITERAZIONE INVERSA---
page-rank in out url 1 0.3210 2 2 alpha 6 0.2007 2 1 sigma 2 0.1705 1 2 beta 4 0.1368 2 1 delta 3 0.1066 1 3 gamma 5 0.0643 1 0 rho
Con tutti e quattro gli algoritmi l’ordine delle pagine riportate in base alla loro importanza `e lo stesso. I vettori Pagerank ottenuti sono leggermente diversi: quelli ottenuti tramite i primi due algoritmi (nei quali si usa il metodo delle potenze) sono uguali, come del resto lo sono i vettori ottenuti con gli ultimi due algoritmi (nei quali si risolve un sistema lineare). Questo ci fa capire che, in base alla situazione in cui ci troviamo, `e pi`u conveniente usare un algoritmo al posto di un altro. Come abbiamo gi`a detto, quando si lavora in Matlab il terzo algoritmo `e il migliore ma in generale, quando si lavora con vere porzioni di web le cui dimensioni sono dell’ordine di milioni di pagine, `e pi`u conveniente usare il metodo delle potenze che preserva la sparsit`a e non va a calcolare esplicitamente la matrice A.
Nelle tabelle, oltre ad essere riportati i valori dei Pageranks, sono anche riportati gli url, ovvero gli indirizzi delle pagine web, ed il numero di inlinks ed outlinks che ogni pagina ha.