The Hyperbolic Geometry of Networks

网络科学是由这样一个问题驱动的：大型现实世界的网络具有哪些属性，以及我们如何通过算法来利用它们。双曲几何，与复杂网络的意想不到的联系，已被证明是这方面的一个有用的工具。这种联系在两个方向上都起作用：双曲几何构成了现实世界网络的自然和解释性模型的基础。双曲随机图是通过在双曲平面上随机选择点，并将几何上接近的点对连接起来而得到的。由此产生的网络与现实世界中的大型网络共享许多结构属性。因此，它们非常适合在更现实的环境中进行算法分析。在另一个方向上，从现实世界的网络开始，双曲几何非常适合度量嵌入。网络的顶点可以映射到这个几何图形中的点，这样几何距离就类似于图的距离。这种嵌入有各种各样的算法应用，从基于高效几何算法的近似到仅使用双曲坐标进行导航决策的贪婪路由。我们的目标是更好地理解现实世界中的大型网络和双曲几何之间的关系。为了涵盖这种联系的两个方向，我们想要研究双曲随机图的性质以及将现实世界的网络嵌入到双曲空间中。此外，我们希望通过开发可证明在双曲随机图上表现良好的算法来利用这些结构洞察力，进而在现实世界的网络上表现良好。

Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. Hyperbolic geometry, with its unexpected connection to complex networks, has proven to be a useful tool in this regard. This connection works in both directions:Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties with large real-world networks. They are thus well suited for algorithmic analyses in a more realistic setting.In the other direction, starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.Our goal is to better understand the relationship between large real-world networks and hyperbolic geometry. To cover both directions of this connection, we want to study properties of hyperbolic random graphs as well as embeddings of real-world networks into hyperbolic space. Moreover, we want to exploit these structural insights by developing algorithms that perform provably well on hyperbolic random graphs and, in turn, empirically well on real-world networks.