| Autor: |
von Looz, Moritz, Özdayi, Mustafa, Laue, Sören, Meyerhenke, Henning |
| Rok vydání: |
2016 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
