Fast generation of dynamic complex networks with underlying hyperbolic geometry

Complex networks have become increasingly popular for modeling real-world phenomena, ranging from web hyperlinks to interactions between people. Realistic generative network models are important in this context as they avoid privacy concerns of real data and simplify complex network research regarding data sharing, reproducibility, and scalability studies. We study a geometric model creating unitdisk graphs in hyperbolic space. Previous work provided empirical and theoretical evidence that this model creates networks with a hierarchical structure and other realistic features. However, the investigated networks were small, possibly due to a quadratic running time of a straightforward implementation. We provide a faster generator for a representative subset of these networks. Our experiments indicate a time complexity of O((n+m) log n) for our implementation and thus confirm our theoretical considerations. To our knowledge our implementation is the first one with subquadratic running time. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree newly adapted to hyperbolic space. We also extend the generator to an alternative dynamic model which preserves graph properties in expectation. Finally, we generate and evaluate the largest networks of this model published so far. Our parallel implementation computes networks with billions of edges on a shared-memory server in a matter of few minutes. A comprehensive network analysis shows that important features of complex networks, such as a low diameter, power-law degree distribution and a high clustering coefficient, are retained over different graph sizes and densities