Publication: Generating massive complex networks with hyperbolic geometry faster in practice
Loading...
Date
Advisor
Department
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Type
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.
Description
Journal or Series
2016 IEEE High Performance Extreme Computing Conference (HPEC)
ISSN
ISBN
Rights
OPEN
Keywords
ddc:004, FOS: Computer and information sciences, DATA processing & computer science, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), info:eu-repo/classification/ddc/004