Name
Abstract | ||
|---|---|---|
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 unit-disk 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^{3/2}+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. We also extend the generator to an alternative dynamic model which preserves graph properties in expectation. Finally, we generate and evaluate the largest networks of this model published so far. Our implementation computes networks with billions of edges in less than an hour. A comprehensive network analysis shows that important features of complex networks, such as a low diameter, power-law degree distribution and a high clustering coefficient, are retained over different graph sizes and densities. |
Year | Venue | Field |
|---|---|---|
2015 | arXiv: Data Structures and Algorithms | Combinatorics,Graph property,Computer science,Algorithm,Theoretical computer science,Complex network,Degree distribution,Clustering coefficient,Time complexity,Network model,Quadtree,Scalability |
DocType | Volume | Citations |
Journal | abs/1501.03545 | 5 |
PageRank | References | Authors |
0.46 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moritz von Looz | 1 | 30 | 4.11 |
| Christian L. Staudt | 2 | 69 | 5.25 |
| Henning Meyerhenke | 3 | 522 | 42.22 |
| Roman Prutkin | 4 | 17 | 1.10 |