• 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
 
 
Master's Dissertation
DOI
Document
Author
Full name
Diego Silva Cintra
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2019
Supervisor
Committee
Oliveira, Maria Cristina Ferreira de (President)
Chalco, Jesús Pascual Mena
Eler, Danilo Medeiros
Minghim, Rosane
Title in Portuguese
Visualização exploratória de grafos bipartidos com o paradigma multinível
Keywords in Portuguese
Grafos bipartidos
Paradigma multinível
Sumarização de grafos
Visualização
Abstract in Portuguese
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.
Title in English
Visual exploration in bipartite graphs with the multilevel paradigm
Keywords in English
Bipartite graphs
Graph summarization
Multilevel paradigm
Visualization
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
DiegoSilvaCintra.pdf (9.87 Mbytes)
Publishing Date
2019-11-05
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2021. All rights reserved.