TRIPODS+X:RES:Collaborative Research: Multi-Level Graph Representation for Exploring Big Data

点击翻译按钮获取中文摘要

Working with social, topical, financial, transportation, biological, and other networks requires a better understanding of their structure and properties. Standard network visualizations of such large real-world networks often resemble hairballs that provide little actionable insight. This project aims to design, implement, and deploy efficient algorithms for multi-level network representations that support interactive exploration by general audiences. Using the familiar Google map metaphor, these algorithms will make it easy to identify important nodes, major pathways, and clusters across multiple levels. Unlike existing methods for visualizing multi-level networks based on meta-nodes and meta-edges, the new visualizations will provide real nodes (prototypes) and real paths (backbones) for each level, similar to geographic maps that show real cities and real roads at every level of detail.The proposed work contributes to graph algorithms by designing and implementing novel and efficient algorithms for interactive analysis and visualization of large, multi-level networks, information visualization with new methods for multi-level network visualization based on the familiar map metaphor, and science mapping standards by providing effective means to explore and use large-scale, multi-level science maps of our collective scholarly knowledge as well as workforce needs. The first goal is to design efficient algorithms for computing Multi-Level Graph Spanners (MLGS) in support of visual analytics tasks for large network exploration, navigation, and communication. The second goal is to utilize the MLGS representation in the context of network analysis and visualization by building a novel online visualization service for interacting with large networks, which combines the MLGS approach with clustering, layout and map-like visualization. The third goal is to develop a new approach for science and workforce classification, lookup, and topical mapping service by applying the MLGS approach to the Web of Science publication data (64 million publications and 1 billion citations) to compute a multi-level map of scientific development. The fourth goal is to validate the new algorithms and visualizations by evaluating both the algorithms and the system using quantitative and qualitative metrics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.