AF: Small: Efficient Representation of Large Networks

现代计算机科学已经见证了其最重要的网络规模的急剧膨胀。代表互联网的图表现在有大约100亿个节点，最流行的社交网络有几十亿活跃用户，这些都伴随着大数据基因组学、大规模神经网络等的兴起。用于图分析的经典算法，可能在过去几十年的网络上工作，通常太慢或成本太高，无法用于现代图。需要更便宜、更快、更容易获得的图分析方法。一种流行的方法是通过图形草图的方法，它小心地用小得多的“草图”代替大的图形，这样可以有效地分析原始的图形，而准确性只有很小的损失。该项目解决了一系列悬而未决的数学和算法挑战，这些挑战是绘制基于距离的图形属性的核心，例如最短路径或可达性。三个主要目标是：(i)确定图形扳手的有效性，图形扳手是最短路径距离的草图，在机器人、分布式计算和电路设计等领域获得了成功的应用；（ii）对较复杂的数据结构结构能否优于较简单的绘制方法（如绘制子图）的绘制问题进行分类；（iii）找到最相关的图的结构参数，如扩展，公路尺寸等，这些参数控制了构建该图草图的难度。在技术方面，本项目借鉴了图算法、极值图论和结构图论、信息论和离散几何的方法。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern computer science has seen a dramatic blowup in the size of its most important networks. Graphs representing the internet now have around 10 billion nodes, the most popular social networks have a few billion active users, and these come alongside the rise of big-data genomics, massive neural networks, etc. Classical algorithms for graph analysis, which may have worked on networks from previous decades, are often far too slow or costly to be used on modern graphs. There is need for cheaper, faster, and more accessible methods for graph analysis.A popular way forward is by the method of graph sketching, which carefully replaces large graphs with much smaller ``sketches'' that can be efficiently analyzed in place of the original, with only minor losses in accuracy. This project addresses a series of unanswered mathematical and algorithmic challenges at the heart of sketching distance-based properties of graphs, such as shortest paths or reachability. Three primary goals are: (i) to determine the efficacy of graph spanners, which are sketches of shortest path distances and which have enjoyed successful applications in areas like robotics, distributed computing, and circuit design; (ii) to classify the sketching problems for which more involved constructions of data structures can or cannot outperform simpler sketching methods like taking subgraphs; and (iii) to find the most relevant structural parameters of graphs, like expansion, highway dimension, etc. that control the difficulty of building a sketch of that graph. On the technical side, this project draws on methods from graph algorithms, extremal and structural graph theory, information theory, and discrete geometry.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.