Algoritmo PAGE-RANK di Google© : importanza dell'algebra lineare per le ricerche nel WEB

Una interrogazione ad un motore di ricerca spesso produce una lunga lista di risposte a causa della presenza di un enorme numero di pagine. Prima della nascita di Google negli anni ’90, il navigatore del web doveva scorrere schermate e schermate di link contenenti anche pagine irrilevanti ed elencate senza gerarchia di importanza: mostrate solo perché contenevano alcuni vocaboli corrispondenti ai termini elencati nella interrogazione. Con l’avvento di Google, l’elenco di pagine web è stato sistematicamente ordinato con un criterio efficace ed ampiamente condiviso per l’importanza delle singole pagine, fornendo in tal modo un notevole aiuto agli utenti. Un diverso concetto di "importanza" e un diverso metodo di analisi della struttura del web, tuttavia, possono produrre classifiche molto differenti. Per fornire la classifica delle pagine web più importanti, Google utilizza l’algoritmo PageRank. Quest’ultimo è il principale motivo dell’attuale rilevanza di Google e della sua posizione come motore di ricerca più utilizzato nel mondo. Ovviamente tutte le peculiarità dell’algoritmo non sono note e restano riservate. Capire come si calcola il PageRank è fondamentale per chiunque abbia un sito web e voglia avere molti visitatori, dal momento che si stima che nella maggior parte dei casi ad un utente bastano i primi dieci risultati forniti da Google per terminare la ricerca. Dal punto di vista matematico, il problema è incentrato sia sulla determinazione della matrice che descrive la struttura dei link di un dato network, la matrice Google, sia sulla ricerca del vettore PageRank, definito come l’autovettore dominante della suddetta matrice o come stato stazionario della catena di Markov corrispondente. La dimensione enorme del problema, tuttavia, limita rigorosamente la scelta degli algoritmi di calcolo che possono essere utilizzati e rende necessario l’utilizzo di un metodo veloce. I risultati presentati nel Capitolo 2 assicurano che la velocità di convergenza dipende dal secondo autovalore della matrice Google. L’algoritmo PageRank non è solo un modo semplice per misurare l’importanza delle pagine, ma è anche un modo computazionalmente vantaggioso rispetto alle altre tecniche di ranking poiché è indipendente sia dall’interrogazione (o query) che dal contenuto delle pagine. In altre parole, il vettore di ranking può essere calcolato offline usando solo la struttura del grafo web ed utilizzato nel momento in cui l’utente invia una query al motore di ricerca. Altri algoritmi, come HITS e Salsa, utilizzati da altri motori di ricerca, affrontano lo stesso problema in maniera differente. In questo lavoro analizzeremo l’Algebra Lineare che è alla base degli algoritmi PageRank ed HITS, evidenziandone le differenze. Ci concentreremo sulla distanza tra il primo e il secondo autovalore della matrice del web, mettendo in evidenza il legame tra la velocità di convergenza dell’algoritmo ed il secondo autovalore. Forniremo alcune proprietà del vettore di ranking, descriveremo la procedura di calcolo con il metodo delle potenze e discuteremo qualche tecnica di accelerazione. Infine, porremo la nostra attenzione sull’algoritmo TrustRank, che permette a Google di arginare l’effetto dannoso del cosiddetto link spamming.