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

与社会、专题、金融、交通、生物和其他网络一起工作需要更好地了解它们的结构和性质。这种大型现实世界网络的标准网络可视化通常类似于毛球，几乎无法提供可操作的见解。该项目旨在为多级网络表示设计、实现和部署有效的算法，支持普通受众的交互式探索。使用熟悉的谷歌映射比喻，这些算法可以很容易地识别跨多个级别的重要节点、主要路径和集群。与现有的基于元节点和元边缘的多层次网络可视化方法不同，新的可视化方法将为每个层次提供真实的节点（原型）和真实的路径（主干），类似于地理地图在每个细节层次上显示真实的城市和真实的道路。通过设计和实现用于大型多层次网络交互分析和可视化的新颖高效算法，以及基于熟悉的地图隐喻的多层次网络可视化新方法的信息可视化，以及通过提供探索和使用我们集体学术知识和劳动力需求的大规模，多层次科学地图的有效手段，所提出的工作对图形算法做出了贡献。第一个目标是设计高效的算法来计算多层次图形生成器（MLGS），以支持大型网络探索、导航和通信的可视化分析任务。第二个目标是在网络分析和可视化的背景下利用MLGS表示，通过构建一种新的在线可视化服务来与大型网络交互，该服务将MLGS方法与聚类、布局和类似地图的可视化相结合。第三个目标是通过对Web of science出版物数据（6400万份出版物和10亿次引用）应用MLGS方法来计算科学发展的多层次地图，为科学和劳动力分类、查找和专题地图服务开发一种新的方法。第四个目标是通过使用定量和定性指标评估算法和系统来验证新的算法和可视化。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.