Name
Abstract | ||
|---|---|---|
Complex networks have become increasingly popular for modeling various real-world phenomena. Realistic generative network models are important in this context as they simplify complex network research regarding data sharing, reproducibility, and scalability studies. Random hyperbolic graphs are a very promising family of geometric graphs with unit-disk neighborhood in the hyperbolic plane. Previous work provided empirical and theoretical evidence that this generative graph model creates networks with many realistic features. In this work we provide the first generation algorithm for random hyperbolic graphs with subquadratic running time. We prove a time complexity of O((n(3/2) + m) log n) with high probability for the generation process. This running time is confirmed by experimental data with our implementation. The acceleration stems primarily from the reduction of pairwise distance computations through a polar quadtree, which we adapt to hyperbolic space for this purpose and which can be of independent interest. In practice we improve the running time of a previous implementation (which allows more general neighborhoods than the unit disk) by at least two orders of magnitude this way. Networks with billions of edges can now be generated in a few minutes. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48971-0_40 | ALGORITHMS AND COMPUTATION, ISAAC 2015 |
Keywords | Field | DocType |
Complex networks,Hyperbolic geometry,Efficient range query,Polar quadtree,Generative graph model | Discrete mathematics,Graph,Hyperbolic tree,Computer science,Data sharing,Theoretical computer science,Hyperbolic geometry,Complex network,Generative grammar,Network model,Scalability | Conference |
Volume | ISSN | Citations |
9472 | 0302-9743 | 12 |
PageRank | References | Authors |
0.64 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moritz von Looz | 1 | 30 | 4.11 |
| Henning Meyerhenke | 2 | 522 | 42.22 |
| Roman Prutkin | 3 | 17 | 1.10 |