AF: Small: Efficient Representation of Large Networks

AF：小型：大型网络的高效表示

• 批准号: 2153680
• 负责人: Gregory Bodwin
• 金额: $ 60万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-04-15 至 2025-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2153680&HistoricalAwards=false
• 关键词: AF; Small; Efficient; Representation; Large

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.

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

项目成果

An Alternate Proof of Near-Optimal Light Spanners

近乎最优的光扳手的替代证明

• 发表时间: 2024
• 期刊: Proceedings of SOSA (Symposium on Simplicity in Algorithms
• 作者: Bodwin, G

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

针对有限度边缘故障的容错扳手：线性更多故障，几乎免费

• 发表时间: 2024
• 期刊: Proceedings of SODA (Symposium on Discrete Algorithms
• 作者: Bodwin, G;Haepler, B;Parter, M
• 通讯作者: Parter, M

Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier

民俗采样是精确 Hopsets 的最佳选择：确认 ân 障碍

• 发表时间: 2023
• 期刊: Proceedings of FOCS (Foundations of Computer Science
• 作者: Bodwin, G;Hoppenworth, G
• 通讯作者: Hoppenworth, G

Bridge Girth: A Unifying Notion in Network Design

桥梁周长：网络设计中的统一概念

• 发表时间: 2023
• 期刊: Proceedings of FOCS (Foundations of Computer Science
• 作者: Bodwin, G;Trabelsi, O;Hoppenworth, G
• 通讯作者: Hoppenworth, G

New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

无分层障碍物产品的新加法扳手下限

• DOI: 10.1109/focs54457.2022.00079
• 发表时间: 2022
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
• 作者: Bodwin, Greg;Hoppenworth, Gary
• 通讯作者: Hoppenworth, Gary