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

Abstract

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.