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

• Grant number: 16/25107-0
• Support Opportunities: Scholarships in Brazil - Master
• Start date: April 01, 2017
• End date: July 31, 2018
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Maria Cristina Ferreira de Oliveira
• Grantee: Diego Silva Cintra
• Host 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)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

CINTRA, DIEGO S.; VALEJO, ALAN; LOPES, ALNEU A.; OLIVEIRA, MARIA CRISTINA F.; KERREN, A; HURTER, C; BRAZ, J. Visualization to Assist Interpretation of the Multilevel Paradigm in Bipartite Graphs. VISAPP: PROCEEDINGS OF THE 15TH INTERNATIONAL JOINT CONFERENCE ON COMPUTER VISION, IMAGING AND COMPUTER GRAPHICS THEORY AND APPLICATIONS, VOL 4: VISAPP, v. N/A, p. 8-pg., 2020-01-01. (16/25107-0, 17/05838-3)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

CINTRA, Diego Silva. Visual exploration in bipartite graphs with the multilevel paradigm. 2019. Master's Dissertation - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.