• 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
 
 
Disertación de Maestría
DOI
Documento
Autor
Nombre completo
Diego Silva Cintra
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2019
Director
Tribunal
Oliveira, Maria Cristina Ferreira de (Presidente)
Chalco, Jesús Pascual Mena
Eler, Danilo Medeiros
Minghim, Rosane
Título en portugués
Visualização exploratória de grafos bipartidos com o paradigma multinível
Palabras clave en portugués
Grafos bipartidos
Paradigma multinível
Sumarização de grafos
Visualização
Resumen en 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 en inglés
Visual exploration in bipartite graphs with the multilevel paradigm
Palabras clave en inglés
Bipartite graphs
Graph summarization
Multilevel paradigm
Visualization
Resumen en 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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
DiegoSilvaCintra.pdf (9.87 Mbytes)
Fecha de Publicación
2019-11-05
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.