Metodi Spettrali per l'Approssimazione di Segnali su Grafi e la Community Detection

Signal processing on social or sensors networks, anomaly detection and pattern recognition in complex networks, such as biological or transport networks, are highly relevant problems today. More generally, given the increasing complexity of networks, extracting information from large datasets requires appropriate tools to represent and analyze them. Graph theory provides a representation of networks through vertices and edges, allowing the generalization of concepts usually referred to the time domain to nonlinear and irregular domains. In this context, the aim of this thesis is to analyze the literature on graph signal interpolation and approximation and to introduce a new approach based on the integration of a spectral method for Community Detection and the Partition of Unity method. The thesis also includes numerical experiments performed on different datasets, which allowed to test the resulting method and show both good accuracy in signal reconstruction and low computational cost.

L’elaborazione e la ricostruzione di segnali su reti sociali o di sensori, la rilevazione di anomalie e l’identificazione di pattern all’interno di reti complesse, come quelle biologiche o di trasporto, rappresentano dei problemi del tutto attuali. Più in generale, di fronte alla crescente complessità delle reti al giorno d’oggi, l’estrazione di informazioni da grandi insiemi di dati rende necessario l’impiego di strumenti adeguati per rappresentarli e analizzarli. La teoria dei grafi offre una rappresentazione delle reti attraverso vertici e lati che permette di estendere alcuni concetti tipici del dominio temporale a domini non-lineari e irregolari. All’interno di questo contesto, questa tesi si propone di analizzare la letteratura riguardante l’interpolazione e l’approssimazione di segnali su grafi e presentare un nuovo approccio basato sull’integrazione di un metodo spettrale di Community Detection e del metodo di Partizione dell’Unità. Nella tesi sono inoltre inclusi esperimenti numerici effettuati su dataset di vario tipo, che hanno permesso di testare il metodo risultante e di mostrare allo stesso tempo una buona accuratezza nella ricostruzione del segnale e un basso costo computazionale.