AF: Small: Efficient Representation of Large Networks

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

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.