The Hyperbolic Geometry of Networks

网络的双曲几何

• 批准号: 390859508
• 负责人: Professor Dr. Tobias Friedrich, Ph.D.
• 金额: --
• 依托单位: Institut für Theoretische Informatik (ITI)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/390859508?language=en
• 关键词: Hyperbolic; Geometry; 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.

网络科学的驱动力是大型现实世界网络具有哪些属性以及我们如何通过算法来利用它们。双曲几何与复杂网络有着意想不到的联系，已被证明是这方面的有用工具。 This connection works in both directions:Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks.双曲随机图是通过在双曲平面中选择随机点并连接几何上接近的点对来获得的。由此产生的网络与大型现实世界网络共享许多结构属性。因此，它们非常适合在更现实的环境中进行算法分析。另一方面，从现实世界的网络开始，双曲几何非常适合度量嵌入。网络的顶点可以映射到该几何中的点，使得几何距离类似于图距离。这种嵌入具有多种算法应用，从基于高效几何算法的近似到仅使用双曲坐标进行导航决策的贪婪路由。我们的目标是更好地理解大型现实世界网络和双曲几何之间的关系。为了涵盖这种连接的两个方向，我们想要研究双曲随机图的属性以及现实世界网络到双曲空间的嵌入。此外，我们希望通过开发在双曲随机图上表现良好的算法来利用这些结构见解，进而在现实世界网络上根据经验表现良好。