Clusterização Espectral utilizando a matriz Laplaciana sem sinal normalizada

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. Para um aprofundamento teórico sobre grafos, recomendamos a leitura de [1]. 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, cujo aprofundamento pode ser feito em [2], 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, conforme discutido em [3]. A partir dessas definições, tem-se a matriz Laplaciana normalizada, dada por L_sym = I −D^-1/2 AD^−1/2, que também é utilizada em algoritmos de clusterização, como apresentado em [4]. Por outro lado, a matriz Laplaciana sem sinal normalizada, definida por Q_sym =I+D^−1/2AD^−1/2, não tem sido 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 a abordagem de clusterização utilizando essa matriz e os resultados de um método já es tabelecido que também emprega a matriz Laplaciana sem sinal. Essa comparação tomará como base a modularidade e o Rand Index, métricas amplamente utilizadas para avaliar a qualidade das clusterizações. Esse comparativo permitirá avaliar as diferenças de desempenho e eficácia entre os dois métodos.

Referências
[1] Samuel Jurkiewicz. Grafos- Uma Introdução. OBMEP, Rio de Janeiro, 2009.
[2] Nair Maria Maia De Abreu, Renata Raposo Del-Vecchio, Cybele Tavares Maia Vinagre, and Dragan Stevanovic. Introdução à Teoria Espectral dos Grafos com Aplicações. SBMAC, São Carlos, SP, 2007.
[3] Juliana Maria de Sousa Costa. Algoritmos espectrais de agrupamento em redes sociais de coautoria. Master’s thesis, Centro Federal de Educação Tecnológica Celso Suckow da Fonseca (CEFET/RJ), 2014. Dissertação de Mestrado. Orientadores: Leonardo Silva de Lima, Rafael Garcia Barbastefano.
[4] D. O. Cardoso, J. D. G. da Silva Junior, C. S. Oliveira, et al. Greedy recursive spectral bisection for modularity-bound hierarchical divisive community detection. Statistics and Computing, 34:145, 2024