Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

The Hyperbolic Geometry of Networks

This site provides a platform for the research project on scale-free networks and their relation to the hyperbolic space, of the HPI's Algorithm Engineering group lead by Tobias Friedrich.

Description

The main difference between the Euclidean geometry and the hyperbolic geometry is the expansion of space. In the hyperbolic geometry space expands exponentially, and thus much faster than in the Euclidean geometry, where space expands polynomially. As a result, distances in the hyperbolic space behave in an interesting way: It is possible to have a certain area be geometrically close to other areas that are themselves rather far apart. In recent years it was observed that this property is intrinsic to many real-world networks: In a social network a famous person can connect to many people which are mostly not connected themselves.

In our research group we study this relation between networks and the hyperbolic space in two ways. On the one hand, one can assume that a network has an underlying hyperbolic geometry and derive properties or analyze how algorithms behave on such a network. On the other hand, one can embed a network into the hyperbolic space and utilize the geometry for different applications.

Analyzing Networks with an Underlying Hyperbolic Geometry

Many real-world networks share common properties like a power-law degree distribution, small diameter, and high clustering. Since all of these properties emerge naturally from the hyperbolic geometry, Hyperbolic Random Graphs are used to model such networks. Hyperbolic random graphs are obtained by randomly distributing nodes in a hyperbolic disc and connecting any two whose hyperbolic distance exceeds a certain threshold.

We showed that the diameter of a hyperbolic random graph is poly-logarithmic with high probability. Additionally, we determined the expected number of k-cliques and the size of the largest clique, and showed that the largest clique can be found in polynomial running time, if the underlying geometry of the network is known. Moreover, we proved that, with high probability, vertex cover can be solved in polynomial time on hyperbolic random graphs, even if the underlying geometry is not known. Furthermore, we showed that hyperbolic random graphs have balanced separator hierarchies with comparatively small separators, and small treewidth. From this we derived a polynomial-time approximation scheme for independent set and showed that maximum matchings can be computed faster on hyperbolic random graphs than when using the fastest known algorithm for general graphs. An analysis of the behavior of the bidirectional breadth-first search on hyperbolic random graphs yielded that with high probability the shortest path between two nodes can be found in sub-linear running time, even if the underlying geometry of the network is not known. 

This project includes research conducted together with our students. For example, the behavior of the bidirectional breadth-first search on hyperbolic random graphs was analyzed in a master project together with Cedric Freiberger, Felix Montenegro-Retana and Marianne Thieffry.

[ 2020 ] [ 2018 ] [ 2016 ] [ 2015 ]

2020 [ nach oben ]

  • Solving Vertex Cover in P... - Download
    Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian Solving Vertex Cover in Polynomial Time on Hyperbolic Random GraphsSymposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14
     

2018 [ nach oben ]

  • Cliques in Hyperbolic Ran... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random GraphsAlgorithmica 2018: 2324–2344
     
  • On the diameter of hyperb... - Download
    Friedrich, Tobias; Krohmer, Anton On the diameter of hyperbolic random graphsSIAM Journal on Discrete Mathematics 2018: 1314–1334
     
  • Efficient Shortest Paths ... - Download
    Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryInternational Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1–20:14
     

2016 [ nach oben ]

  • Hyperbolic Random Graphs:... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Hyperbolic Random Graphs: Separators and TreewidthEuropean Symposium on Algorithms (ESA) 2016: 15:1–15:16
     

2015 [ nach oben ]

  • On the Diameter of Hyperb... - Download
    Friedrich, Tobias; Krohmer, Anton On the Diameter of Hyperbolic Random GraphsInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 614–625
     
  • Cliques in Hyperbolic Ran... - Download
    Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random GraphsInternational Conference on Computer Communications (INFOCOM) 2015: 1544–1552
     

Embedding Networks into the Hyperbolic Space

The goal of embedding a network into the hyperbolic space is to assign a coordinate to each node in the network, such that the resulting positioning can be utilized in a certain way.

Most commonly, networks are embedded for visualization purposes. That is, the goal is to obtain a placement of the nodes that visually reflects certain properties of the network. The exponential expansion of the hyperbolic space makes it well suited to represent hierarchical or tree-like structures, which are observed in many real-world networks. To encapsulate the structure of a given network, it is then preferred to place adjacent nodes close to each other and non-adjacent nodes farther apart. We developed a quasi-linear maximum likelihood estimation algorithm that estimates the positions of the nodes given the adjacency information of the graph. An empirical analysis showed, that when pretending to forget the coordinates of a hyperbolic random graph, our algorithm can rediscover them very well. More details can be found here.

Network embeddings can also be useful to perform greedy or geographic routing. There, the idea is to forward messages through a network, by iteratively sending it to the node that is geometrically closest to the target. It is known that every network can be embedded in the hyperbolic plane, such that geographic routing works without getting stuck in dead ends, by embedding a spanning tree of the graph. We empirically analyzed how the choice of the underlying spanning tree impacts the length of the paths obtained by the geographic routing. Our experiments showed, that one can choose a certain kind of spanning tree, such that the lengths of resulting routing paths are close to the shortest paths in the network. More details can be found here.

[ 2020 ] [ 2018 ] [ 2016 ]

2020 [ nach oben ]

  • Hyperbolic Embeddings for... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic Embeddings for Near-Optimal Greedy RoutingJournal of Experimental Algorithmics (JEA) 2020: 1–18
     

2018 [ nach oben ]

  • Efficient Embedding of Sc... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneIEEE/ACM Transactions on Networking 2018: 920–933
     
  • Hyperbolic Embeddings for... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic Embeddings for Near-Optimal Greedy RoutingAlgorithm Engineering and Experiments (ALENEX) 2018: 199–208
     

2016 [ nach oben ]

  • Efficient Embedding of Sc... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneEuropean Symposium on Algorithms (ESA) 2016: 16:1–16:18
    EATCS Best Paper Award
     

Efficiently Generating Hyperbolic Random Graphs

Their previously mentioned properties and similarity to real-world networks make hyperbolic random graphs a valuable tool in practice. Software designed for large-scale graphs can be tested on differently sized random instances before being deployed and algorithms can be thoroughly benchmarked or tuned for specific structures. This is, because of the flexibility of hyperbolic random graphs to slightly vary one aspect of a network, like average degree, while preserving other properties. For these applications, however, it is necessary that even large instances of this random graph model can be generated very efficiently.

In recent years, different algorithmic approaches were developed to speed up the generation process. Together with the University of Frankfurt, we built a generator capable of generating graphs with ten million edges in under a second on commodity hardware. Experiments show that our generator is the fastest sequential implementation thus far. The software is open source and available on GitHub.

[ 2019 ]

2019 [ nach oben ]

  • Efficiently Generating Ge... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
    EATCS Best Paper Award
     

Other Graph Models

Despite our focus on hyperbolic random graphs we are also interested in other graph models. In order to evaluate how well a graph model can represent certain aspects of real-world networks, we proposed a machine learning based evaluation approach. An empirical analysis of over 200 networks showed that our technique can be used to uncover weaknesses of certain graph models, i.e., properties of real-world networks that a graph model can not represent well. 

[ 2024 ] [ 2022 ] [ 2019 ] [ 2018 ]

2024 [ nach oben ]

  • Robust Parameter Fitting ... - Download
    Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
    ArXiv preprint
     

2022 [ nach oben ]

  • What’s Wrong with Deep ... - Download
    Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
     

2019 [ nach oben ]

  • From Graph Theory to Netw... - Download
    Friedrich, Tobias From Graph Theory to Network Science: The Natural Emergence of HyperbolicitySymposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
     

2018 [ nach oben ]

  • Towards a Systematic Eval... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, Jonathan Towards a Systematic Evaluation of Generative Network ModelsWorkshop on Algorithms and Models for the Web Graph (WAW) 2018: 99–114