The relevance of the second eigenvalue in Google PageRank algorithm

Google was born in 1998 and with it, its revolutionary page-ranking method. Indeed, with the continuing growth of the Internet network, a way to ranking all pages belonging to it, was mandatory. The main goal of this technique is to have an easier access to all the results relative to a certain query asked by the users. The final ranking has both qualitative and quantitative dependences, the first one takes into account the content of the websites and their relevance with respect to the query, while the second one is about the structure of the Web and all its connections. The latter is where the Google PageRank algorthm focus. The PageRank is an index associated to each website of the Network, which represents its relative importance and makes it comparable to all others websites. This work is divided in three sections. In the first one PageRank is defined and computed, passing through the definition of the Google matrix which represents the transition matrix of the Markov process modelling the algorithm. In the second one the relevance of the second eigenvalue of the Google matrix is discussed, with all its implications, paying particular attention to the link spamming and to some methods to recognize and avoid it. In the third and last one the "personalized" PageRank is defined. This is a strategy to take into account the preferences of the users and to make the process computationally faster.

Nel 1998 venne fondato quello che tuttora rimane uno dei più potenti e funzionali tra i motori di ricerca, Google. Con lo sviluppo di una rete Internet così ampia e complessa, si è presto presentato il problema di trovare un ordinamento totale, relativo alle ricerche effettuate dagli utenti, per tutte le pagine Web appartenenti alla rete; in modo da avere un output chiaro ed accessibile da presentare agli utenti stessi. L'ordinamento ottenuto è basato su due aspetti principali, quello qualitativo, legato al contenuto di un certo documento e alla sua attinenza con una determinata ricerca, e quello quantitativo, legato alla struttura del Web. Quest'ultimo è proprio quello di cui si occupa l'algoritmo Google PageRank, associando a ciascuna pagina della rete un valore (chiamato PageRank), che rappresenti la sua importanza nella rete stessa e che renda la pagina comparabile a tutte le altre. Questo lavoro è diviso principalmente in tre sezioni. Nella prima si definisce il PageRank e si spiega come calcolarlo passando attraverso la "costruzione" della matrice di Google, che rappresenta la matrice di transizione del processo di Markov che modellizza l'algoritmo. Nella seconda si discute il significato del secondo autovalore della matrice di Google, con tutte le sue implicazioni, soffermandosi in particolare sul cosiddetto link spamming e su alcune strategie per riconoscerlo e di conseguenza evitarlo. Nella terza e ultima sezione si definisce una tecnica che personalizza il PageRank, conferendo maggiore importanza alle preferenze degli utenti e velocizzando il processo computazionale; in questo modo il risultato della ricerca sarà più rapido e specifico.