Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Ω(n2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.

More of our reasearch about the hyperbolic geometry of networks can be found here.

Downloads

Algorithm

You can checkout the code from BitBucket. Installation instructions can be found in the readme.

Datasets

The embedding from the paper; along with other embeddings. The (un-embedded) graphs were taken from the SNAP graph database