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.

Abstract: The possibility of grouping data to discover interesting patterns and correlations is fundamental in many areas of study. This task can be automatically performed through the use of clustering methods. When the data show a graph structure, such as in the case of social networks, this process is called graph clustering. The importance of graph clustering in several areas has led many researchers to develop algorithms in parallel. Therefore, the papers present assumptions that are often incompatible which result in a lack of consensus on the features that characterize the results of a clustering procedure in a specific graph. Thus, there is a lack of a fundamental theory for the characterization of a valid solution for a given graph. This paper proposes a formal definition of the graph clustering problem. It is desirable that this formalization is robust enought in order to address the problem associated with a large number of graph clustering algorithms. In this paper, the graph clustering problem is described as the problem which involves finding a solution that satisfies a given set of constraints and minimizes a given objective function. The set of constraints and the objective function are used to define the desirable characteristics of natural clustering solutions. Thus, it is shown that this formalization is able to encompass various graph clustering algorithms. Finally, it's presented a general exhaustive solution to the aforementioned problem. As this solution is costly, this paper also proposes the combination of the characteristics of the set of constraints and objective function in order to reduce the search space of the algorithm that the general solution to the problem.