Generating practical random hyperbolic graphs in near-linear time and with sub-linear memory

  • Random graph models, originally conceived to study the structure of networks and the emergence of their properties, have become an indispensable tool for experimental algorithmics. Amongst them, hyperbolic random graphs form a well-accepted family, yielding realistic complex networks while being both mathematically and algorithmically tractable. We introduce two generators MemGen and HyperGen for the G_{alpha,C}(n) model, which distributes n random points within a hyperbolic plane and produces m=n*d/2 undirected edges for all point pairs close by; the expected average degree d and exponent 2*alpha+1 of the power-law degree distribution are controlled by alpha>1/2 and C. Both algorithms emit a stream of edges which they do not have to store. MemGen keeps O(n) items in internal memory and has a time complexity of O(n*log(log n) + m), which is optimal for networks with an average degree of d=Omega(log(log n)). For realistic values of d=o(n / log^{1/alpha}(n)), HyperGen reduces the memory footprint to O([n^{1-alpha}*d^alpha + log(n)]*log(n)). In an experimental evaluation, we compare HyperGen with four generators among which it is consistently the fastest. For small d=10 we measure a speed-up of 4.0 compared to the fastest publicly available generator increasing to 29.6 for d=1000. On commodity hardware, HyperGen produces 3.7e8 edges per second for graphs with 1e6 < m < 1e12 and alpha=1, utilising less than 600MB of RAM. We demonstrate nearly linear scalability on an Intel Xeon Phi.

Download full text files

Export metadata

Metadaten
Author:Manuel PenschuckGND
URN:urn:nbn:de:hebis:30:3-444830
DOI:https://doi.org/10.4230/LIPIcs.SEA.2017.26
ISBN:978-3-95977-036-1
ISSN:1868-8969
Parent Title (German):16th International Symposium on Experimental Algorithms (SEA 2017) ; Leibniz International Proceedings in Informatics (LIPIcs) ; 75
Publisher:Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication:Dagstuhl
Document Type:Conference Proceeding
Language:English
Year of Completion:2017
Year of first Publication:2017
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2017/10/29
Tag:random hyperbolic graph generator; streaming algorithm
Page Number:21
HeBIS-PPN:424198932
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License LogoCreative Commons - Namensnennung 4.0