• spacey random walk
• Multilinear PageRank
• graph clustering
• tensor

Il PageRank è un modello ben noto ed usato per gestire grafi che rappresentano reti del mondo reale. Recentemente, in letteratura è stato largamente studiato e spesso utilizzato per partizionare grafi in clusters (si veda a titolo di esempio [1], [2], [3]).
In questa tesi, analizziamo la sua recente generalizzazione chiamata multilinear PageRank, pubblicata per la prima volta in [4]. Matematicamente il problema consiste nella risoluzione di un sistema di equazioni polinomiali.
Si esaminano le proprietà teoriche e si affrontano le sfide computazionali che ne derivano.
Successivamente, affrontiamo il problema del partizionamento di grafi basato su strutture quali triangoli e cicli tra nodi, per le quali il multilinear PageRank risulta uno strumento di grande utilità. Il testo della tesi è organizzato come segue.
Nel capitolo 1 richiamiamo alcuni fatti basilari sulle matrici non negative, alcune nozioni sui tensori, un utile risultato riguardante la soluzione di equazioni vettoriali quadratiche e alcune definizioni sui processi stocastici.
Nel capitolo 2 studiamo il multilinear PageRank da un punto di vista teorico. Più in particolare, trattiamo un modello stocastico detto spacey random walk, la cui distribuzione stazionaria risolve l’equazione di multilinear PageRank e trattiamo il problema dell’esistenza e unicità della sua soluzione.
Nel capitolo 3 riportiamo alcuni algoritmi per calcolare le soluzioni stocastiche dell’equazione suddetta e li confrontiamo dal un punto di vista della velocità di convergenza, del costo computazionale e della stabilità numerica.
Nel capitolo 4 introduciamo il problema del partizionamento di grafi basato su strutture che richiedono l’uso di tensori tridimensionali per essere memorizzate, come i già citati triangoli e cicli tra tre nodi. A tal proposito, presentiamo un algoritmo di cluster basato sul modello di multilinear PageRank, e un ulteriore algoritmo basato su un modello stocastico detto super-spacey random walk, che richiede la risoluzione di un’equazione non lineare. Presentiamo due algoritmi di risoluzione: uno è stato introdotto in [5] e l’altro è un contributo originale di questo lavoro.
Infine, nel capitolo 5, ci focalizziamo sui dettagli implementativi degli algoritmi precedentemente presentati e riportiamo i risultati della sperimentazione numerica effettuata. In particolare, testiamo i nostri codici su alcuni casi critici dell’equazione di multilinear PageRank e affrontiamo alcune istanze del problema di partizionamento di grafi, sia costruiti sinteticamente che emergenti da dati reali.