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.