Based on:
M. von Looz, H. Meyerhenke, R. Prutkin: Generating Random Hyperbolic Graphs in Subquadratic Time. To appear in Proc. 26th International Symposium on Algorithms and Computation (ISAAC 2015).
Introduction
Complex networks have become increasingly popular for modeling various real-world phenomena.
Realistic generative network models are important in this context as they simplify complex
network research regarding data sharing, reproducibility, and scalability studies.
Random hyperbolic graphs are a very promising family of geometric graphs with unit-disk
neighborhood in the hyperbolic plane.
Previous work provided empirical and theoretical evidence that this generative graph model
creates networks with many realistic features.
In our recent work we provide the first generation algorithm for random hyperbolic graphs
with subquadratic running time.
We prove a time complexity of \(O((n^{3/2}+m) \log n)\) with high probability for the generation process.
Generation Algorithm
In the generative model, vertices are generated as points in polar coordinates \((\phi, r)\) on a disk of radius \(R\) in the hyperbolic plane with curvature \(-\zeta^2\).
Any two vertices \(u\) and \(v\) are connected by an edge if their hyperbolic distance \(\mathrm{dist}_{\mathcal{H}}(u,v)\) is below \(R\).
(A more general model with non-deterministic edges exists, but is not considered in this implementation. An extended implementation for the general model is available on request.)
Native representation of a hyperbolic random graph, as specified in a paper of Krioukov et al..
We choose a vertex \(u\) (the bold blue vertex) and add edges \((u,v)\) for all vertices \(v\) where \(\mathrm{dist}_{\mathcal{H}}(u,v) \leq 0.2\cdot R\).
The neighborhood of \(u\) then consists of vertices within a hyperbolic circle (marked in blue).
A straightforward implementation would iterate over all point pairs to generate the graph, leading to a quadratic time complexity.
Instead, we use the Poincaré disk model to map the hyperbolic plane into the Euclidean unit disk.
This model of hyperbolic space maps hyperbolic circles to Euclidean circles, the neighborhood of a vertex is then an Euclidean circle with a moved center:
The center of the Euclidean circle is marked with \(\times\).
Getting all points that are in an Euclidean circle can be modeled as a range query and we can use a polar quadtree on the Poincaré disk to reduce the time complexity of this query.
Part from a polar quadtree
Publication and Implementation
The corresponding article is due to appear in the proceedings of 26th Int'l Symp. on Algorithms and Computation(ISAAC 2015). More material is available in the preprint on arxiv.
The implementation is available on the Dev branch of NetworKit, our network analysis framework.
Experimental results
Even large networks with 10 million vertices and a billion edges can be generated in a couple of minutes:
Comparison of running times to generate networks with \(10^4-10^7\) vertices and varying number of edges.
The lines illustrate the theoretical fit, using the equation \(T(n,m) = \left(\left(3.8\cdot10^{-7} n + 1.14\cdot10^{-9} n^{3/2} + 1.38\cdot10^{-8}m\right) \log \ n\right) \mathit{sec}\).
