CAREER: Scalable Techniques for Visualizing Very Large Graphs

图，也称为网络，是用来表示不同实体之间的结构关系的重要数据结构。图模型在科学应用（如计算分子生物学和生态学）和工业应用（如万维网和社会网络服务）中无处不在。借助先进的计算技术，现实世界的应用程序可以生成前所未有规模的图形数据集，例如全球社交网络，其中大型图形可以包含数十亿或数万亿个顶点（身份）和边（关系）。图形可视化，即创建图形的可视化或图解表示，已被广泛用作一种有效的手段，以方便用户获得图形结构的有意义的概述和捕获感兴趣的区域。然而，仍然缺乏可扩展的可视化解决方案，这些解决方案对于非常大的图形数据集是有效和实用的，并且允许用户及时探索和发现可能的见解。这样的解决方案只能通过对大图形的处理、组织和可视化的整体协调来获得，然而，在之前的大多数图形可视化工作中，这并没有得到充分的研究。该项目寻求通过解决端到端图形可视化管道（包括图形处理、组织和可视化）来确保大型图形可视化的可扩展性和可用性的技术。由于图形作为一种关键的数据模型存在于许多科学和工业应用中，通过与领域专家的拓展活动和合作，本研究开发的图形可视化工具和优化技术可以极大地造福于更广泛的领域和社区。该项目的教育目标是利用现实世界的大型图形可视化来有效地促进学生在理工科学习中的参与度和学习效率。特别是，该项目旨在利用跨学科的协同作用来开发和创新本科和研究生课程，以促进专业和非专业学生的学习。跨学科的图形应用程序将用于加强外展，学生招募和研究机会。在不同学科的教育工作者的参与下，将评估教学效果。该项目将通过利用图形结构属性和计算机系统优化，为非常大的图形开发可扩展的可视化技术。为了实现这一目标，项目有以下目标。首先，开发可扩展的并行聚类方法，从大图中提取具有密集内连接的子图。其次，将设计新的算法，通过根据潜在的访问模式识别和组织子图来解决基本的数据局部性问题，以支持图处理和可视化。第三，将开发结构感知可视化技术，采用分层方式，为用户提供高效和有效的大型图形探索视觉指导。这些结果将改变传统的可视化方法，这些方法还没有准备好处理具有数十亿或数万亿个顶点和边的图形，为现实世界的大规模图形应用提供有效和实用的技术。该项目的研究和教育成果将在主要会议和期刊以及其他形式中传播。项目网站（http://cse.unl.edu/~yu/research/nsf17_graph/）提供了指向项目结果的指针，包括出版物、数据集、软件、演示和教育材料，以及相应的说明。

Graphs, also called networks, are important data structures used to represent structural relationships between different entities. Graph models have been ubiquitously employed in scientific applications (e.g., computational molecular biology and ecology) and industrial applications (e.g., world wide web and social network services). With advanced computing techniques, real-world applications can generate graph datasets of unprecedented scales, such as a worldwide social network, where a large graph can contain billions or trillions of vertices (identities) and edges (relationships). Graph visualization, creating visual or diagrammatic representations of graphs, has been commonly used as an effective means to facilitate users to gain meaningful overviews of graph structures and capture regions of interest. However, there is still a lack of scalable visualization solutions that are efficient and practical for very large graph datasets and allow users to explore and discover possible insights in a timely manner. Such solutions can only be obtained with a holistic coordination of processing, organization, and visualization of large graphs, which however has not been fully investigated in most of the previous graph visualization work. This project seeks techniques to ensure the scalability and the usability of large graph visualization by tackling an end-to-end graph visualization pipeline including graph processing, organization, and visualization. Since graphs exist in many scientific and industrial applications as a critical data model, through the outreach activities and the collaboration with domain experts, graph visualization tools and optimization techniques developed in this research can greatly benefit a broader class of fields and communities. The education objective of this project is to leverage real-world large graph visualization to effectively promote students' engagement and learning efficiency in science and engineering studies. In particular, the project aims to leverage interdisciplinary synergies to develop and renovate undergraduate and graduate courses to facilitate the learning of both major and non-major students. Interdisciplinary graph applications will be used to enhance outreach, student recruitment, and research opportunities. Teaching effectiveness will be assessed with an involvement of educators from different disciplines.The project will develop scalable visualization techniques for very large graphs by exploiting graph structure properties and computer systems optimization. To accomplish this goal, the project has the following objectives. First, scalable parallel clustering methods will be developed to extract sub-graphs with dense intra-connections from large graphs. Second, new algorithms will be designed to address the fundamental data locality problem by identifying and organizing sub-graphs according to their potential access patterns in support of graph processing and visualization. Third, structure-aware visualization techniques, adopting a hierarchical manner, will be developed to provide users an efficient and effective visual guide for large graph exploration. These results will transform conventional visualization methods, which were not ready for handling graphs with billions or trillions of vertices and edges, to efficient and practical techniques for real-world large-scale graph applications. The research and education results from this project will be disseminated in premier conferences and journals and other forms. The project website (http://cse.unl.edu/~yu/research/nsf17_graph/) provides the pointers to the project results, including publications, datasets, software, demos, and educational materials, with the corresponding descriptions.