Uma proposta para a formalização do problema de clusterização em grafos

Abstract

Resumo: A possibilidade de agrupar dados para descobrir padrões e correlações interessantes é muito importante em diversas áreas do conhecimento. Essa tarefa pode ser realizada de forma automática através dos métodos de clusterização. Quando os dados apresentam uma estrutura de grafos, como no caso de redes sociais, esse processo é chamado clusterização em grafos. A importância da clusterização em grafos em diversas áreas levou vários cientistas a desenvolver algoritmos paralelamente. Por isso, os artigos apresentam assunções que muitas vezes são incompatíveis, resultando em uma falta de consenso sobre quais as propriedades que caracterizam o resultado de um procedimento de clusterização em um grafo específico. Isto é, não há uma fundamentação teórica para caracterização do que seria uma solução válida para um determinado grafo. Esse trabalho propõe uma definição formal do problema de clusterização em grafos. É desejável que essa formalização seja robusta o suficiente para descrever o problema resolvido por uma grande parte dos algoritmos de clusterização em grafos. Nesse trabalho, o problema de clusterização em grafos é descrito como o problema de encontrar uma solução que satisfaça um conjunto de restrições e que minimize uma função objetivo. O conjunto de restrições e a função objetivo são utilizados para definir quais a características desejáveis da solução de clusterização natural. Com isso, é mostrado que essa formalização engloba vários algoritmos de clusterização em grafos. Por fim, é apresentada uma solução geral exaustiva para o problema proposto. Como essa solução é muito custosa, esse trabalho propõe combinações das características do conjunto de restrições e da função objetivo a fim de reduzir o espaço de busca do algoritmo que é solução geral do problema.