Advances in graph partitioning algorithms

Graph partitioning is a problem that interested scientists since the last cen- tury. Many real-world applications can be modelled as graphs: social net- works, telecommunication routing, images, circuitry design, etc. Over the course of the last 60 years, an increasing variety of algorithm has been pro- posed to solve the graph partitioning problem, adapting to its evolution. If at the beginning the main goal was to divide graphs into equal sized groups, the explosion of data occurred in the last decade shifted the focus on scalable methods, capable of working on large graphs, trying to maintain balanced solutions. In this thesis, three new graph partitioning algorithms are presented, hav- ing different purposes and working principles. These algorithms were thought with multiple goals. First, they complete unused ideas, never fully explored in the literature or that were simply discarded due to their inefficiency. Sec- ond, these algorithms are created to reach results comparable with state of the art algorithms, in terms of speed and quality. The last, and main, pur- pose is to find solutions to specific real-world problems, as mesh partition- ing or image segmentation, that in the last years moved towards real-time requirements. With these algorithms, we were able to achieve three results: a fast and scalable hybrid multi-level clustering; an incredibly fast tree based partitioning, performing better than the state of the art algorithms, and a slightly slower method, derived from the depth first search on graphs, to obtain perfectly balanced partitions.

Il partizionamento di grafi è un problema che interessa gli scienziati sin dall'ultimo secolo. Molte applicazioni del mondo reale possono essere modellate come grafi: reti sociali, routing di telecomunicazione, immagini, progettazione di circuiti, ecc. Nel corso degli ultimi 60 anni, è stata proposta una crescente varietà di algoritmi per risolvere il problema di partizionamento di grafi, adattandosi alla sua evoluzione. Se all'inizio l'obiettivo principale fu quello di dividere i grafi in gruppi di dimensioni uguali, l'esplosione di dati avvenuta nell'ultimo decennio spostò l'attenzione su metodi scalabili, in grado di lavorare su grandi grafi, cercando di mantenere soluzioni bilanciate. In questa tesi vengono presentati tre nuovi algoritmi di partizionamento di grafi, con scopi e principi di funzionamento differenti. Questi algoritmi sono stati pensati con più obiettivi. In primo luogo, completano le idee inutilizzate, mai completamente esplorate in letteratura o semplicemente scartate a causa della loro inefficienza. In secondo luogo, questi algoritmi sono creati per raggiungere risultati confrontabili con algoritmi allo stato dell'arte, in termini di velocità e qualità. L'ultimo scopo è quello di trovare soluzioni a specifici problemi del mondo reale, come la divisione di mesh o la segmentazione delle immagini, che negli ultimi anni si sono spostati verso requisiti in tempo reale. Con questi algoritmi, siamo stati in grado di ottenere tre risultati: un clustering ibrido multilivello veloce e scalabile; un partizionamento basato su albero incredibilmente veloce, con prestazioni migliori rispetto agli algoritmi allo stato dell’arte e un metodo leggermente più lento, derivato dalla Ricerca di Profondità su grafi, per ottenere partizioni perfettamente bilanciate.