Generating massive complex networks with hyperbolic geometry faster in practice

von Looz M., Ozdayi M. S. , Laue S., Meyerhenke H.

IEEE High Performance Extreme Computing Conference (HPEC), Massachusetts, United States Of America, 13 - 15 September 2016 identifier

  • Publication Type: Conference Paper / Full Text
  • City: Massachusetts
  • Country: United States Of America


Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. The commonly used graph-based benchmark model R-MAT has some drawbacks concerning realism and the scaling behavior of network properties. A complex network model gaining considerable popularity builds random hyperbolic graphs, generated by distributing points within a disk in the hyperbolic plane and then adding edges between points whose hyperbolic distance is below a threshold. We present in this paper a fast generation algorithm for such graphs. Our experiments show that our new generator achieves speedup factors of 3-60 over the best previous implementation. One billion edges can now be generated in under one minute on a shared-memory workstation. Furthermore, we present a dynamic extension to model gradual network change, while preserving at each step the point position probabilities.