Generating massive complex networks with hyperbolic geometry faster in practice

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