Passeggiate aleatorie su networks: l’algoritmo PageRank di Google

Le catene di Markov sono processi aleatori in cui la probabilità condizionata di passare da uno stato all'altro non dipende dalla sequenza degli stati percorsi. Questo elaborato nasce con l’obiettivo di approfondire la teoria delle catene di Markov e la loro applicazione all'algoritmo PageRank di Google, un algoritmo di ricerca che consiste nell'indicizzare le pagine del web imponendo un ordine di priorità in cui esse devono apparire. Ciò è possibile grazie al teorema ergodico che permette di assegnare un indice di popolarità ad ogni pagina web. Il web viene quindi rappresentato come un grafo orientato, perciò il problema si riduce a passeggiate aleatorie su networks. Più precisamente, attraverso il metodo MonteCarlo si possono simulare catene di Markov, la cui legge può essere descritta da una matrice che a sua volta viene rappresentata dal suo corrispettivo grafo orientato.