Penschuck, Manuel
Generating Practical Random Hyperbolic Graphs in NearLinear Time and with SubLinear Memory
Abstract
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 wellaccepted 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 powerlaw 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^{1alpha}*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 speedup 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.
BibTeX  Entry
@InProceedings{penschuck:LIPIcs:2017:7621,
author = {Manuel Penschuck},
title = {{Generating Practical Random Hyperbolic Graphs in NearLinear Time and with SubLinear Memory}},
booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)},
pages = {26:126:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770361},
ISSN = {18688969},
year = {2017},
volume = {75},
editor = {Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7621},
URN = {urn:nbn:de:0030drops76218},
doi = {10.4230/LIPIcs.SEA.2017.26},
annote = {Keywords: Random hyperbolic graph generator, streaming algorithm}
}
07.08.2017
Keywords: 

Random hyperbolic graph generator, streaming algorithm 
Seminar: 

16th International Symposium on Experimental Algorithms (SEA 2017)

Issue date: 

2017 
Date of publication: 

07.08.2017 