Large scale graph visualization supported by a multilevel paradigm and edge bundling

• Grant number: 16/25107-0
• Support type: Scholarships in Brazil - Master
• Effective date (Start): April 01, 2017
• Effective date (End): July 31, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal researcher: Maria Cristina Ferreira de Oliveira
• Grantee: Diego Silva Cintra
• Home Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Graph and network visualization is a highly relevant problem in the current research scenario in Information Visualization, since many data sets resulting from real world problems are described by such structures. Researchers in the field have proposed graph drawing techniques to support exploration and analysis of this kind of data and facilitate user interpretation. Nevertheless, most techniques and solutions proposed so far face severe limitations when handling large scale graphs. Many strategies to handle the problem create condensed graph representations, which are combined with some standard graph drawing technique. Such a compression can be applied both to the set of vertices or to the set of edges that describe their relationships. For the edges, the so-called edge bundling techniques are very popular. As for the vertices, techniques that take advantage of graph properties to extract hierarchies, or communities, have been explored, but current solutions have limited flexibility or are application specific.The multilevel paradigm is a partitioning technique for overlapping community detection in large scale graphs, which generate multiple representations of the graph at different refinement levels. In this project, we intend to apply this paradigm, in combination with edge bundling techniques, to create visualizations of large graphs. Our goal is to develop a graph visualization solution suitable for exploratory scenarios, i.e., in which analysts wish to navigate in the visual representation in order to identify and investigate relevant connectivity patterns in edges and/or vertices and their associated data.Our hypothesis is that a visualization integrated with the multilevel paradigm and edge bundling techniques can provide a flexible solution to support exploratory tasks on large scale graphs. The multilevel paradigm is an efficient solution for gradual aggregation and refinement of graphs, and allows precise recovery of topological information at any refinement level. The edge bundling, in turn, reduces line overlapping and emphasizes relevant structures. The combination of both strategies should support visual representations capable of supporting exploratory navigation tasks in relational data represented by large scale graphs. (AU)