KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast generation of dynamic complex networks with underlying hyperbolic geometry

von Looz, Moritz; Staudt, Christian L.; Meyerhenke, Henning; Roman Prutkin

Complex networks have become increasingly popular for modeling real-world phenomena, ranging from web hyperlinks to interactions between people. Realistic generative network models are important in this context as they avoid privacy concerns of real data and simplify complex network research regarding data sharing, reproducibility, and scalability studies. We study a geometric model creating unitdisk graphs in hyperbolic space. Previous work provided empirical and theoretical evidence that this model creates networks with a hierarchical structure and other realistic features. However, the investigated networks were small, possibly due to a quadratic running time of a straightforward implementation. We provide a faster generator for a representative subset of these networks. Our experiments indicate a time complexity of O((n+m) log n) for our implementation and thus confirm our theoretical considerations. To our knowledge our implementation is the first one with subquadratic running time. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree newly adapted to hyperbolic space. W ... mehr

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000043881
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2014
Sprache Englisch
Identifikator ISSN: 2190-4782
KITopen-ID: 1000043881
Verlag KIT, Karlsruhe
Umfang 13 S.
Serie Karlsruhe Reports in Informatics ; 2014,14
Schlagworte complex networks, hyperbolic geometry, generative model, network analysis, polar quadtree
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page