Clusterização Espectral Utilizando a Matriz Laplaciana sem Sinal Normalizada

Resumo

Clusters são sistemas organizados que consistem em conjuntos de elementos interconectados e que compartilham características ou funções semelhantes, presentes em diversas áreas como a tecnologia, a indústria, a biologia e o meio social. Assim, compreender a estrutura, as interações e as propriedades desses agrupamentos é fundamental para otimizar o desempenho dos sistemas e promover a eficiência em suas respectivas áreas. O crescente interesse da comunidade científica pelo estudo dos clusters reflete a importância de desvendar os mecanismos que regem essas interações e que possibilitam o aprimoramento das estratégias de gerenciamento e desenvolvimento de sistemas complexos. Para obter os clusters, é necessário modelar as redes a serem trabalhadas. Isso pode ser feito por meio da Teoria dos Grafos. Nesse contexto, a clusterização espectral surge como uma abordagem fundamentada na análise espectral de matrizes associadas ao grafo, permitindo a identificação de agrupamentos. Os dados são representados por um grafo G = (V(G), E(G)), onde V(G) é o conjunto de vértices, que representam os elementos individuais, e E(G) é o conjunto de arestas, que indica as relações entre esses elementos. A estrutura do grafo pode ser representada por diversas matrizes como por exemplo a matriz de adjacência, A(G), cuja entrada a_ij assume o valor 1 se existir uma aresta entre os vértices v_i e v_j, e 0 caso contrário, e a matriz diagonal dos graus, D(G), onde o elemento diagonal d(v_i) representa o número de arestas incidentes em v_i. Utilizando as matrizes A(G) e D(G), definem-se, respectivamente, a matriz Laplaciana e a matriz Laplaciana sem sinal como: L(G) = D(G) - A(G) e Q(G) = D(G) + A(G). Essas matrizes desempenham um papel importante quando se fala em clusterização espectral, pois seus autovalores e autovetores fornecem informações essenciais para a identificação de comunidades. A partir dessas definições, tem-se a matriz Laplaciana normalizada: L_sym = I - D^-1/2AD^-1/2, que também é utilizada em algoritmos de clusterização. Por outro lado, a matriz Laplaciana sem sinal normalizada é definida como: Q_sym = I + D^-1/2AD^-1/2, não sendo explorada na literatura, e sua aplicação em técnicas de clusterização permanece pouco investigada. Neste contexto, o objetivo deste trabalho é investigar a utilização da matriz Laplaciana sem sinal normalizada para a obtenção de uma clusterização, analisando o seu processo e a obtenção dos resultados. Ao final do estudo, será realizada uma comparação entre os resultados obtidos com essa abordagem e os resultados de um método já estabelecido que também emprega a matriz Laplaciana sem sinal. A comparação tomará como base a modularidade e o Rand Index. [...]