Analisi del metodo SIAD per il PageRank

In questo lavoro di tesi si analizzerà un metodo per risolvere il problema del PageRank alternativo rispetto al tradizionale metodo delle potenze. Verso la fine degli anni '90, con l’avvento del World Wide Web, fu necessario sviluppare degli algoritmi di classificazione in grado di ordinare i siti web in base alla loro rilevanza. Davanti a questa sfida i due matematici A.N.Langville e C.D.Meyer svilupparono il metodo SIAD, "special iterative aggregation/disaggregation method". Lo scopo di questa tesi è in primo luogo di ricostruire il metodo SIAD e analizzarne le proprietà. Seguendo le analisi in un articolo di I.C.Ipsen e S.Kirkland, si ricostruirà nel dettaglio il metodo SIAD, così da esplicitare la convergenza asintotica del metodo in relazione al complemento stocastico scelto. In secondo luogo si analizzerà il metodo SIAD applicato ad una matrice di Google che rispetta ipotesi determinate, le matrici di Google sono solitamente utilizzate per rappresentare il problema del PageRank. Successivamente, si dimostrerà un importante teorema che prova come per ogni matrice di Google si possa individuare un complemento stocastico per cui il metodo SIAD converge più velocemente del metodo delle potenze. Infine, nell’ultimo capitolo si implementerà con il inguaggio di programmazione Matlab il metodo SIAD per una matrice generica e per una matrice di Google. In particolare, si sfrutterà la struttura della matrice di Google per ridurre sensibilmente il costo computazionale del metodo quando applicato applicato ad una tale matrice.