Visual Analytics of large, dynamic Graphs

Project: Applied Research

Project Details

Abstract

Dynamic graphs arise in many domains, such as cash flow graphs in the finance sector, social networks, customer care centers, transport logistics, communication and energy networks, etc. While traditional static graphs have established themselves as the mathematical model of choice for problems involving relational data, dynamic graphs are relatively new. What sets apart the graphs considered in this project from the graphs that have predominantly been the target of existing techniques is the sheer size of the graphs (readily exceeding 100s of millions or even billions of nodes) and the fact that the graph may undergo topological changes in time. In addition, per-node metadata such as timestamps, geolocation or other information is commonly available. While dynamic graphs have recently received considerable research interest, our understanding of extremely large dynamic graphs is still lacking. This project aims at advancing the field of dynamic graph visualization by making the following contributions. A) new graph layout algorithms that successfully handle the dynamic topology changes in the graph by allowing for incremental updates in the layout (such as, e.g., would fall into the class of procrustean multi-dimensional changes) B) novel graph visualizations going beyond traditional node-link or matrix views (such as, e.g., computing a coverage volume to be visualized by direct volume rendering or iso-contouring instead of traditional rendering approaches) C) efficient and effective methods for data aggregation that convert the dynamic graph into a hierarchical representation and that can provide both overview and detail as the user explores the data (such as spatiotemporal clustering and/or sparse coding approaches) D) new and efficient high-performance rendering algorithms that exploit the data aggregation methods developed in C) to deliver interactive, scalable visualization methods able to cope with 100s of millions of nodes (such as level-of-detail rendering approaches, culling methods to avoid overdraw, etc.) E) new joint layout algorithms that consider a collection of graphs, establish semantic correspondences between nodes across the collection, and seek to preserve the spatial relation between corresponding nodes across the selection. This allows to compare the resulting layouts side-by-side or overlay them, which, in our prior work, has proven itself to be very effective at conveying similarities and differences to the user (such as a layout method the LPI co-authored). F) using the data aggregation methods (C), data models that allow for the classification and semi-automated extraction of irregularities and features in the graph will be developed. The project focusses on dynamic graphs from three different domains. Firstly, dynamic graphs that model financial transactions. This is motivated by a keen interest in the financial sector to automatically spot anomalies such as market manipulations, money laundering, bribery, and income related to trade of illegal substances. However, a mathematical model that would allow extraction of such crucial information from the underlying dynamic transaction graph automatically is still direly amiss. We therefore propose to use the prototypes and methods that will be developed in this project to visually analyze the data in order to form hypothesis and allow for the visual classification of features related to the above anomalies. After hypotheses have been formed, the project will, in a second stage, model the data to a degree that allows for semi-automatic extraction. The methods developed in this project will then, finally, be integrated in dashboard views together with domain experts in order to alert personnel of suspicious behavior. Such tools have a very high potential impact, as they address core pain points of public policy making that are hard to resolve by other means. Since financial transaction data is typically riddled with data sovereignty issues, we will focus on the bitcoin blockchain, recording over a decade of transactions, is arguably the largest dynamic graph stemming from the finance sector in the public domain. Secondly, our co-sponsor Hamad International Airport is interested in understanding people flows. HIA possesses vast and varying anomized data points derived from its beacons/network nodes of connected devices carried by passengers. Such data can be modeled as dynamic graph in various ways. The passenger flow between connections can be modeled as edges and nodes, respectively, or the temporary connections can be understood as dynamic graph in itself. Another source of dynamic graphs that HIA is interested in analyzing are airside movements, aircraft landing sequences and taxing to parking bays/gates. Here, operations have pre-determined time durations, and the amount of data makes unaided pattern detection from naïve visualizations difficult. Identifying patterns of congestion represents a substantial financial value and will help HIA formulate hypotheses on ways to minimize congestions. Thirdly, our co-sponsor Iberdrola QSTP LLC is interested in analyzing communication networks traffic in smart grids. In this context, the topology of the communication graph does not significantly change over time, but the edge weights modeling the transmitted data per communication channel do. Tools to visualize and understand such network congestions will help analyzing and improving grid management efficiency, reliability, and latency of the network. Similarly, Iberdrola QSTR LLC is interested in medium voltage grid energy flow. Replacing the highly dynamic edge weights of the previous problem by energy flow, Iberdrola has hourly load data for 80,000 transformers located in the Spanish energy system. Understanding and combating under-utilizations will result in substantial energy conservations.

Submitting Institute Name

Hamad Bin Khalifa University (HBKU)
Sponsor's Award NumberNPRP13S-0130-200207
Proposal IDEX-QNRF-NPRPS-11
StatusFinished
Effective start/end date15/06/2114/02/24

Collaborative partners

Primary Theme

  • Artificial Intelligence

Primary Subtheme

  • AI - Smart Cities

Secondary Theme

  • Artificial Intelligence

Secondary Subtheme

  • AI - Analytics & Decision Support

Keywords

  • Uncertainty Quantification,Carbonate Reservoirs,Enhanced oil recovery (eor),CO2 injection in hydrocarbon reservoirs,Reservoir characterization
  • None

Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.