Agrupamentos Múltiplos Não-Redundantes em Grafos com Atributos

Muitos algoritmos de agrupamento em grafo destinam-se a gerar uma única partição (agrupamento) dos dados. No entanto, um mesmo conjunto de dados pode produzir diferentes agrupamentos. De uma perspectiva exploratória, dado um conjunto de dados, a possibilidade de se gerar agrupamentos alternativos e não-redundantes é importante para a compreensão dos dados. Cada um desses agrupamentos poderia proporcionar um ponto de vista diferente sobre esses dados. Muitas áreas demandam a exploração de diversas soluções de agrupamento, como a área de marketing em redes sociais. É nesse contexto que esse trabalho se insere, apresentando um novo algoritmo para gerar agrupamentos múltiplos a partir de um grafo com atributos. Nesse tipo de grafo, cada vértice está associado a uma n-tupla de atributos (por exemplo, em uma rede social, os usuários têm interesses, sexo, idade, etc.). A abordagem concebida adiciona arestas artificiais entre vértices semelhantes do grafo utilizando a similaridade entre os atributos, o que resulta em um grafo com atributos aumentado. Em seguida, é aplicado um algoritmo de agrupamento nesse novo grafo. Dessa maneira, diversos agrupamentos são gerados utilizando diferentes combinações de atributos. Os resultados experimentais indicam que a abordagem é eficaz na tarefa de produzir agrupamentos múltiplos em grafos com atributos. No entanto, o problema não é apenas produzir os agrupamentos múltiplos, mas produzi-los de maneira que não sejam redundantes. Nesse cenário, esse trabalho também contribui com um novo algoritmo para selecionar os top-k agrupamentos não-redundantes. Resultados experimentais utilizando uma rede social online real e uma rede de co-autoria mostram a eficácia dos algoritmos propostos.