Visualização de grandes grafos apoiada pelo paradigma multinível e aglomeração de arestas

Resumo

A visualização de grafos e redes é um problema altamente relevante no cenário atual da pesquisa em Visualização de Informação, uma vez que muitos dados gerados por problemas do mundo real podem ser modelados por tais estruturas. Pesquisadores atuando na área vêm propondo técnicas de visualização de grafos que viabilizem a análise exploratória desse tipo de dado e facilitem a sua interpretação por usuários. Entretanto, a maior parte das técnicas e soluções existentes apresenta sérias limitações em grafos de grande escala. Muitas estratégias que buscam tratar esse problema criam alguma representação condensada do grafo, a qual é renderizada utilizando estratégias convencionais de desenho. Esses processos de compressão podem ser aplicados tanto ao conjunto de vértices como ao conjunto de arestas que descrevem seus relacionamentos. No caso das arestas, as técnicas denominadas de edge bundling vêm se tornando bastante populares. No caso dos vértices, técnicas têm sido exploradas que se aproveitam de propriedades do grafo para extrair hierarquias, ou comunidades. Entretanto, as soluções existentes mostram-se pouco flexíveis ou são aplicáveis a cenários específicos.O paradigma multinível é uma estratégia de particionamento utilizada para detecção de comunidades sobrepostas em grafos de larga escala, e que gera representações do mesmo em diferentes níveis de refinamento. Neste projeto, pretendemos aplicar este paradigma, combinado com técnicas de edge bundling, para gerar visualizações de grandes grafos. O objetivo é desenvolver uma solução que se mostre adequada para apoiar tarefas de visualização exploratória, i.e., em que analistas desejam navegar na representação visual do grafo com o objetivo de identificar e investigar padrões de conectividade relevantes aos seus nós e/ou arestas e dados associados. Nossa hipótese é que uma visualização apoiada no paradigma multinível associado a técnicas de bundling de arestas oferece uma solução flexível para apoiar tarefas exploratórias sobre grafos. O paradigma multinível é uma solução eficiente para agregação e refinamento gradual do grafo, e permite a recuperação precisa das informações relativas à sua topologia, em qualquer nível do refinamento. O bundling das arestas, por sua vez, contribui para reduzir a sobreposição de linhas, enfatizando as estruturas relevantes. A combinação de ambas as estratégias deve favorecer a criação de representações visuais capazes de viabilizar tarefas de navegação exploratória em dados relacionais representados por grafos de larga escala. (AU)