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.

Sorry, the requested view was not found.

The technical reason is: No template was found. View could not be resolved for action "view" in class "AcademicPuma\ExtBibsonomyCsl\Controller\DocumentController".

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.

Sorry, the requested view was not found.

The technical reason is: No template was found. View could not be resolved for action "view" in class "AcademicPuma\ExtBibsonomyCsl\Controller\DocumentController".

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.

Sorry, the requested view was not found.

The technical reason is: No template was found. View could not be resolved for action "view" in class "AcademicPuma\ExtBibsonomyCsl\Controller\DocumentController".

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. 

Sorry, the requested view was not found.

The technical reason is: No template was found. View could not be resolved for action "view" in class "AcademicPuma\ExtBibsonomyCsl\Controller\DocumentController".