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.