Metodi numerici
per catene di Markov - laboratorio
Docente:
Beatrice Meini
Lezione 3: Il pagerank di Google
Vogliamo calcolare il "page rank" di piccole reti con vari metodi numerici.
Le reti vengono rappresentate da 2 variabili: la matrice G che rappresenta la "connectivity matrix" e il vettore U che contiene i nomi delle pagine web della rete.
Usiamo due piccole reti, una sottorete di 500 pagine web della Harvard University, e una sottorete di 600 pagine web, ottenuta mediante la function surfer.m a partire dalla pagina betti.dm.unipi.it.
Il file harvard500 contiene le variabili G e U relative alla Harvard University, mentre il file UGbetti600 contiene le variabili G e U ottenute partendo da betti. Dando il comando load harvard500 ( load UGbetti600, rispettivamente) nel Workspace appaiono le variabili G e U (Gbetti, Ubetti rispettivamente). Per osservare la struttura di G, dare il comando spy(G).
Il "page rank" viene calcolando ordinando il vettore invariante di probabilita' della matrice di transizione P ottenuta a partire dalla matrice G, come descritto a lezione. Le seguenti funzioni costruiscono la matrice P, in funzione di G e del parametro p, che rappresenta la probabilita' di scegliere una della pagine linkate da quella che sto visitando (un valore standard e' p=0.85), e resituiscono in output il vettore invariante di probabilita'.
La function x = pagerank(U,G,p) calcola il Pagerank risolvendo con un metodo diretto il sistema lineare sparso (I - p*G*D)x = delta*e, dove e e' il vettore con tutte le componenti 1. Tale sistema deriva dal sistema (I-p*G*D-e*e'/n)x=0 e imponendo la condizione e'*x=1. La function disegna anche il grafico del pagerank (commentare queste istruzioni se il tempo per tracciare il grafico e' troppo lungo). Il valore di default per p e' 0.85; provare a modificare questo valore.
La function x = pagerankgth(U,G,p) calcola il Pagerank risolvendo un sistema lineare utilizzando fattorizzazione LU con aggiustamento diagonale. Osservare come il tempo di calcolo sia lungo.
La function x = pagerankpow(U,G,p) calcola il Pagerank mediante il metodo delle potenze, sfruttando la sparsita' della matrice.
Con la function surfer potete provare a generare altre reti.