CAREER: Sublinear Graph Algorithms: New Insights for Foundational Problems

图是表示数据之间关系的最自然的方式之一，并被用来为各种各样的环境建模：社交网络、通信基础设施、金融市场的互连、代谢过程和人类大脑的连接，等等。长期以来，处理此类图表一直是计算机科学研究的基石，但大数据的兴起带来了独特的计算挑战，因为这些应用程序中的图表规模远远超过了可用的计算能力。这个项目的目标是开发一个处理海量图形的新工具包。该项目在大数据分析中研究了一系列新的研究问题，开发的新工具可以应用于基础优化问题，如最短路径和匹配，这些问题是计算机科学、社会网络、生物学和计算经济学应用的核心。对基础问题的关注使该项目能够将来自不同背景的本科生和研究生聚集在一起。除了博士指导和高中推广外，该教育计划还包括为本科生提供研究机会，并在罗格斯大学开设一门关于次线性图算法的新课程。这个项目集中在处理大量图形的三个主要挑战上。首先，这样的图形太大，计算机内存无法容纳，因此必须动态压缩数据。其次，单台计算机处理图形的时间太长，因此计算分布在许多机器上。第三，在许多应用程序中，底层图随着时间的推移而变化，有必要在本地响应这些变化。该项目开发了解决每个单独挑战的新工具。同时，该项目引入了将这些不同挑战的研究联系起来的通用框架，并导致能够同时克服广泛障碍的工具。更具体地说，统一上述挑战的是需要从小区域计算的局部信息推断整个图的全局信息。例如，能否从图的一个小的随机样本中检测到过载的顶点？如何将不同区域的最短路径拼接在一起，形成从图一端到另一端的路径？如何压缩图以只保留最相关的边？通过回答这些和相关的问题，该研究将有助于将激励应用扩展到更大的尺度，并将导致对图结构的新的数学见解。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs are one of the most natural ways to represent relationships between data and are used to model a wide variety of settings: social networks, the communication infrastructure, the interconnections of financial markets, metabolic processes, and the wiring of the human brain, to name a few. Processing such graphs has long been a cornerstone of computer science research, but the rise of big data poses unique computational challenges, as the scale of the graphs in these applications has far outpaced available computing power. The goal of this project is to develop a new toolkit for processing massive graphs. This project studies a novel set of research questions in the analysis of big data, and the new tools developed can be applied to foundational optimization problems such as shortest paths and matching that are central to applications in computer science, social networks, biology, and computational economics. The focus on foundational problems allows the project to bring together undergraduate and graduate students from a wide range of backgrounds. In additional to PhD mentoring and high-school outreach, the education plan includes research opportunities for undergraduates and the development of a new course in sublinear graph algorithms at Rutgers University.This project centers on three major challenges to processing massive graphs. The first is that such graphs are too large to fit in the memory of a computer, so the data must be compressed on the fly. The second is that it would take too long for a single computer to process the graph, so the computation is distributed over many machines. The third that is that in many applications the underlying graph is changing over time and it is necessary to respond to these changes locally. The project develops novel tools for tackling each individual challenge. At the same time, the project introduces general frameworks that connect the studies of these different challenges and lead to tools that can overcome a broad set of obstacles simultaneously. More specifically, what unifies the above challenges is the need to extrapolate global information about the entire graph from local information computed in small regions. For example, can one detect overloaded vertices from a small random sample of the graph? How can shortest paths in different regions be patched together to form a path from one end of the graph to another? How can a graph be compressed to only retain the most relevant edges? By answering these and related questions, the research will help extend the motivating applications to significantly larger scales and will lead to new mathematical insights into the structure of graphs.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.