• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
Documento
Autor
Nome completo
Diego Silva Cintra
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2019
Orientador
Banca examinadora
Oliveira, Maria Cristina Ferreira de (Presidente)
Chalco, Jesús Pascual Mena
Eler, Danilo Medeiros
Minghim, Rosane
Título em português
Visualização exploratória de grafos bipartidos com o paradigma multinível
Palavras-chave em português
Grafos bipartidos
Paradigma multinível
Sumarização de grafos
Visualização
Resumo em português
O paradigma multinível tem sido utilizado na resolução de problemas de otimização combinatória em grafos. Ele opera gerando uma hierarquia de grafos contraídos e resolvendo o problema em uma versão reduzida do grafo original, o que reduz o espaço de soluções e permite utilizar um algoritmo cujo tempo de execução seria inviável no grafo original. Recentemente, foi proposto um arcabouço multinível flexível para a solução de problemas em grafos bipartidos, o qual admite vários parâmetros de entrada. Essa dissertação apresenta uma nova metáfora visual que auxilia na interpretação do resultado de executar o paradigma multinível em um grafo bipartido e na avaliação do impacto de diferentes escolhas dos parâmetros nos resultados. O objetivo é ilustrar como a nova metáfora associada ao paradigma multinível apoia tarefas analíticas em grafos bipartidos. Para validar este objetivo um sistema foi desenvolvido como prova de conceito, denominado MObViewer, que além da nova metáfora visual utiliza visualizações adicionais para auxiliar nas tarefas analíticas. Dois tipos de estudos de caso foram conduzidos para validar o MObViewer. O primeiro considera questões analíticas sobre o paradigma multinível elaboradas em conjunto com um especialista, e respondidas considerando grafos sintéticos, construídos em um ambiente controlado. Já o segundo consiste em uma investigação exploratória sobre grafos bipartidos que modelam dados do mundo real. Os resultados mostram que a nova metáfora visual auxilia a identificação do impacto da alteração dos parâmetros de entrada do paradigma multinível e ilustram como a integração entre visualização e o arcabouço multinível pode apoiar a visualização exploratória de grafos bipartidos.
Título em inglês
Visual exploration in bipartite graphs with the multilevel paradigm
Palavras-chave em inglês
Bipartite graphs
Graph summarization
Multilevel paradigm
Visualization
Resumo em inglês
The multilevel paradigm has been used in the resolution of combinatorial optimization problems in graphs. It creates a hierarchy of coarsened graphs and solves the problem in a coarsened version of the original graph, which reduces the solution space and allows to use an algorithm whose initial complexity would be cost-prohibitive in the original graph. Recently, a flexible multilevel paradigm framework was proposed for problem-solving in bipartite graphs, which admits several input parameters. This dissertation presents a novel visual metaphor which aids to interpret the result of executing the multilevel paradigm in a bipartite graph and the impact assessment of different input choices in the results. The objective is to show how a novel metaphor associated with the multilevel paradigm supports analytic tasks in bipartite graphs. To evaluate this objective, a system was developed as a proof-of-concept, dubbed MObViewer, which besides using the novel visual metaphor uses additional visualizations to aid in analytic tasks. Two types of case studies were conducted to evaluate MObViewer. The first considers analytic questions about the multilevel paradigm elaborated with an expert, answered considering synthetic graphs, created in a controlled environment. The second consists of an exploratory investigation of real-world data modeled as bipartite graphs. The results show that the new visual metaphor aids in identifying the impact of altering input parameters of the multilevel paradigm and illustrate how the integration between visualization and framework can support in the visual exploration of bipartite graphs.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
DiegoSilvaCintra.pdf (9.87 Mbytes)
Data de Publicação
2019-11-05
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2020. Todos os direitos reservados.