Learning Preferential Attachment Graphs under Partial Observability

Questa tesi analizza il problema della stima della topologia di una rete a partire dai segnali prodotti dai suoi nodi durante l’esecuzione di un algoritmo distribuito. In particolare, i suddetti segnali sono generati nel tempo secondo un modello autoregressivo vettoriale, ossia un modello diffusivo lineare in cui ogni nodo scambia messaggi con i suoi vicini (dunque, in base al grafo che descrive la rete) e li combina seguendo una certa regola. Si considera il complesso scenario in cui la stima della topologia debba avvenire sotto l’ipotesi di osservabilità parziale, secondo la quale solo parte dei nodi può essere osservata, e vengono studiate le condizioni sotto le quali il grafo relativo ai nodi osservati può essere ricostruito; si tratta di un problema complesso, in quanto i segnali osservati sono influenzati dalla presenza di nodi latenti, i cui segnali fungono da rumore e possono in principio inficiare la ricostruzione del grafo. Si considerano due aspetti fondamentali del problema. Il primo aspetto riguarda la fattibilità: sotto quali condizioni il problema di stima della topologia è risolvibile? Ossia, esiste uno stimatore in grado di ricostruire il grafo in esame a partire dai segnali emessi dai nodi osservati? In generale, una risposta affermativa a queste domande permette soltanto di sapere che uno stimatore esiste, e che funzionerà con un numero sufficientemente grande di campioni. Di conseguenza, il secondo aspetto analizzato riguarda l’onerosità della soluzione: dato uno stimatore individuato dalla suddetta analisi di fattibilità, quanti campioni richiede per funzionare correttamente in pratica? Studi recenti hanno analizzato il problema quando il grafo in esame `e generato secondo il modello aleatorio di Erdos-Renyi. .. [a cura dell'Autore]