Teorema Ergodico e PageRank

L’algoritmo PageRank è un metodo di ranking di pagine web del motore di ricerca Google sviluppato tra il 1996 e il 1998 da Sergey Brin e Lawrence Page come modo per misurare l’importanza relativa delle varie pagine. Questo utilizza le proprietà delle catene di Markov ed in particolare il teorema ergodico per trovare un valore associato ad ogni pagina web. Durante il corso di questa tesi approfondiremo l’innovazione e l’efficacia di questo algoritmo. Svilupperemo quindi nel primo capitolo le idee teoriche relative alle catene di Markov per poi introdurre e approfondire nel secondo capitolo l’algoritmo in sé. L’idea matematica fondamentale e l’obiettivo a livello teorico di questa tesi è il teorema ergodico. Questo teorema estende la legge dei grandi numeri a variabili aleatorie non necessariamente indipendenti e quindi permette di provare la convergenza del metodo PageRank. Osserveremo inoltre gli sviluppi del motore di ricerca di Google portati dopo la pubblicazione di PageRank per comprendere al meglio come questo sia utilizzato tutt’oggi. Infine nel terzo capitolo svilupperemo un esempio di uso del metodo PageRank per risolvere un problema all’apparenza totalmente differente dal suo scopo originale. Utilizzeremo infatti l’algoritmo per creare un ranking della popolazione in base alla probabilità di un individuo di essere contagiato durante un’ipotetica epidemia. Osserveremo perciò in questo capitolo sia come viene implementato l’algoritmo, sia la sua possibile versatilità d’uso.