NeTS: Small: New Directions in Network Dimensionality Reduction for Routing and Beyond

计算机网络中的许多重要问题依赖于网络图的观察性质——通过测量真实网络而得到的图。这些包括路由器网络、自治系统、无线节点和社会关系。不幸的是，尽管现在有了大量的详细数据，但人们对这样的图仍然知之甚少，部分原因是图数据的高维性。该项目正在开发网络图降维的新方法和应用。我们的出发点是最近的一项工作，它说明了双曲几何在这个问题上的作用。因此，该项目有三个目标：通过在双曲空间中嵌入网络图来开发新的降维方法；发现双曲嵌入在各种网络图中的适用性并应用双曲嵌入来解决实际的网络问题。研究的问题之一是寻找新的路由方法，将贪婪路由的简单性与路径的高成功率和效率的理想特性结合起来。该项目的成果将为社区创造独特的软件工具，促进其他人在这一领域的研究；它将揭示对网络很重要的图的属性；它还将开发可能用于未来网络的路由新方法。该项目将为两名研究生提供培训，其成果将以出版物和免费分发软件的形式传播。

Many important problems in computer networking depend on the observed properties of network graphs --- graphs obtained by measuring real network. These include networks of routers, autonomous systems, wireless nodes, and social relationships. Unfortunately, despite the explosion of detailed data now available, such graphs are still poorly understood, in part because of the high dimensionality of graph data. The project is developing new methods for, and applications of, dimensionality reduction of network graphs. The starting point is recent work by illustrating the power of hyperbolic geometry for the problem. Accordingly, the project has three goals: developing new methods for dimensionality reduction by embedding network graphs in hyperbolic spaces; discovering the applicability of hyperbolic embedding for a wide range of network graphs; and applying hyperbolic embedding to address practical networking questions. Among the problems being investigated is finding new methods for routing that combine the simplicity of greedy routing with the desirable properties of high success rate and efficiency of paths. The project's results will create unique software tools for the community, facilitating research in this area by others; it will shed new light on the properties of graphs that are important to networking; and it will develop new methods for routing that may be used in future networks. This project will provide training for two graduate students and its results will be disseminated in the form of both publications and freely distributed software.