Fundamentos matemáticos de estratégias espectrais para particionamento de grafos

Abstract

O problema de particionamento consiste, basicamente, em agrupar dados semelhantes e separar aqueles que não se assemelham e pode ser modelado matematicamente a partir de grafos. Recentemente, foram publicados diversos resultados teóricos sobre o tema e alguns deles fornecem algoritmos que utilizam o espectro de uma matriz associada a um grafo para gerar uma partição que auxilia a demonstrar estes resultados. Tais resultados trazem argumentos teóricos que podem ser evidências de que este algoritmo teria um bom desempenho como método para encontrar a melhor partição do problema de particionamento. Neste trabalho, procuramos entender o funcionamento de alguns destes algoritmos. Especificamente, nosso objetivo é compreender os algoritmos obtidos pela demonstração da cota superior para condutâncias de ordem 2, apresentada por Chung [8], e ordem k > 2, demonstrada por Trevisan [33]. Com relação a este último, apesar da demonstração não exigir que alguns passos do algoritmo sejam implementados de uma única maneira, vamos especificá-los com base na análise dos exemplos em que o aplicamos. Nestes exemplos, observamos que os algoritmos definidos obtiveram um bom desempenho. Também estudamos o resultado apresentado por Wang et. al [35] sobre particionamento de árvores em duas classes e propomos uma possível estratégia para provar a versão estendida deste resultado para k > 2 classes. Parte desta estratégia envolve uma versão do resultado [35] estendido para grafos com peso nos vértices, cuja prova é uma contribuição original deste trabalho.

The clustering problem basically consists of grouping similar data and separating those that are not similarm, and it can be using graphs. Recently, several theorical results have been published on this subject, and some of them provide approximation algorithms that use the spectrum of a matrix associated with a graph to generate a partition to prove these results. In this work, we try to understand how some of these algorithms work. Specifically, our objective is to understand the algorithms obtained for proving an upper bound for partitions into two classes, presented by Chung [8], and into k-classes, presented by Trevisan [33]. Regarding the latter, since the proof does not specify how some steps of the algorithm must be implemented, we will define them based on the analysis of the examples in which we apply it. We observed that the algorithm performed well on this examples. We also studied the result presented by Wang et al. [35] about splitting trees into two classes and we propose a possible strategy to prove an extended version of this result for k > 2 classes. Part of this strategy involves an extension of a result in [35] extended to graphs with weights on vertices, whose proof is an original contribution of this work.