L'Algoritmo di PageRank

Il successo del motore di ricerca Google si basa principalmente sull’algoritmo di PageRank, capace di valutare quantitativamente l’importanza di ogni pagina web, consentendo a Google di classificare le pagine e quindi presentare all’utente per prime quelle più importanti e pertinenti. L’algoritmo di PageRank è un’applicazione dell’algebra lineare standard, infatti, per la sua elaborazione si sfruttano nozioni su matrici e grafi. In questa tesi si definisce il web come un grafo orientato e si studia la matrice dei link ad esso associata. Possono sorgere problemi come la presenza di dangling nodes, ossia pagine senza collegamenti in uscita, oppure il grafo del web potrebbe non essere fortemente connesso; la matrice dei link viene così modificata in modo da risultare stocastica per righe, irriducibile e non-negativa. Tale matrice viene detta matrice di Google. Si definisce il PageRank vector come l’autovettore sinistro della matrice di Google relativo all’autovalore 1. Si forniscono alcune espressioni implicite ed esplicite per il PageRank vector, lo si calcola, utilizzando il metodo delle potenze ed infine si è studiato l’errore alla k-esima iterata.