Interactive visualization and processing of large graphs

• Grant number: 11/13724-1
• Support Opportunities: Regular Research Grants
• Start date: January 01, 2013
• End date: December 31, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: José Fernando Rodrigues Júnior
• Grantee: José Fernando Rodrigues Júnior
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• City of the host institution: São Carlos

Abstract

Graphs define complex data present in many research fields, so that extracting useful information from a graph structure can provide significant gains for various applications. However, new communications and monitoring technologies have produced graphs whose magnitudes hinder their computation and analysis. Among the processes used to handle such graphs is the hierarchical partitioning; according to this methodology, the vertices of a graph can be grouped recursively, determining a hierarchy, according to the relationships defined by its own edges. Still, the current data structures used for this computation are based on primary memory, limiting the possibilities of using a scarce resource compared to the volumes of data. Therefore, this project aims at the research and development of a new methodology for representing hierarchically partitioned graphs. The new methodology shall allow the processing of graphs stored on disk while allowing it to answer to connectivity queries over the original graph and over the partitions of the hierarchical representation. As a proof of concept, the proposed innovation will be applied to a system of multi-resolution visualization of graphs called GMine. The new approach will allow alternatives less subject to the cardinality of these sets of data. (AU)