Busca avançada
Ano de início
Entree

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

Processo: 16/25107-0
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de abril de 2017
Vigência (Término): 31 de julho de 2018
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
Pesquisador responsável:Maria Cristina Ferreira de Oliveira
Beneficiário:Diego Silva Cintra
Instituição-sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
Assunto(s):Visualização de informação

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.