Full text
| |
| Author(s): |
Diego Silva Cintra
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Carlos. |
| Institution: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Defense date: | 2019-08-08 |
| Examining board members: |
Maria Cristina Ferreira de Oliveira;
Jesús Pascual Mena Chalco;
Danilo Medeiros Eler;
Rosane Minghim
|
| Advisor: | Maria Cristina Ferreira de Oliveira |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 16/25107-0 - Large scale graph visualization supported by a multilevel paradigm and edge bundling |
| Grantee: | Diego Silva Cintra |
| Support Opportunities: | Scholarships in Brazil - Master |