Non backtracking PageRank

In questa tesi abbiamo analizzato il non backtracking PageRank, un algoritmo di classificazione variante del PageRank che non considera il backtracking, cioè i cammini che tornano nel nodo da cui sono partiti al passo subito successivo. Lo scopo di questa variante è ottenere una classificazione migliore in tutti quei problemi in cui il backtracking viene evitato. Siamo partiti introducendo il PageRank standard, per poi spiegare nel dettaglio il non backtracking PageRank e quali fossero le analogie e differenze tra i due. Ci siamo poi chiesti come risolvere computazionalmente il problema, studiando il risolutore di sistemi lineari GMRES e facendo delle osservazioni su come si possano ridurre il numero di iterazioni e il tempo di calcolo tramite il precondizionamento. Infine, abbiamo eseguito degli esperimenti sulle reti stradali di alcune città e confrontato i risultati ottenuti tramite le diverse classificazioni.