License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.21
URN: urn:nbn:de:0030-drops-111424
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11142/
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Friedrich, Tobias ; Katzmann, Maximilian ; Meyer, Ulrich ; Penschuck, Manuel ; Weyand, Christopher

Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs

pdf-format:
LIPIcs-ESA-2019-21.pdf (0.7 MB)

Abstract

Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent beta, and high clustering that can be controlled via the temperature T.
We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to T = 0. We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation.
Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify the desired expected average degree as input.
Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.

BibTeX - Entry

@InProceedings{blsius_et_al:LIPIcs:2019:11142,
  author =	{Thomas Bl{\"a}sius and Tobias Friedrich and Maximilian Katzmann and Ulrich Meyer and Manuel Penschuck and Christopher Weyand},
  title =	{{Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11142},
  URN =		{urn:nbn:de:0030-drops-111424},
  doi =		{10.4230/LIPIcs.ESA.2019.21},
  annote =	{Keywords: hyperbolic random graphs, geometric inhomogeneous random graph, efficient network generation}
}

Keywords: hyperbolic random graphs, geometric inhomogeneous random graph, efficient network generation
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI