1 Search Results for "Keusch, Ralph"

Document

DOI: 10.4230/LIPIcs.ESA.2017.20

Sampling Geometric Inhomogeneous Random Graphs in Linear Time

Authors: Karl Bringmann, Ralph Keusch, and Johannes Lengler

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

Real-world networks, like social networks or the internet infrastructure, have structural properties such as large clustering coefficients that can best be described in terms of an underlying geometry. This is why the focus of the literature on theoretical models for real-world networks shifted from classic models without geometry, such as Chung-Lu random graphs, to modern geometry-based models, such as hyperbolic random graphs. With this paper we contribute to the theoretical analysis of these modern, more realistic random graph models. Instead of studying directly hyperbolic random graphs, we introduce a generalization that we call geometric inhomogeneous random graphs (GIRGs). Since we ignore constant factors in the edge probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic cosines), while preserving the qualitative behaviour of hyperbolic random graphs, and we suggest to replace hyperbolic random graphs by this new model in future theoretical studies. We prove the following fundamental structural and algorithmic results on GIRGs. (1) As our main contribution we provide a sampling algorithm that generates a random graph from our model in expected linear time, improving the best-known sampling algorithm for hyperbolic random graphs by a substantial factor O(n^0.5). (2) We establish that GIRGs have clustering coefficients in Omega(1), (3) we prove that GIRGs have small separators, i.e., it suffices to delete a sublinear number of edges to break the giant component into two large pieces, and (4) we show how to compress GIRGs using an expected linear number of bits.

Cite as

Karl Bringmann, Ralph Keusch, and Johannes Lengler. Sampling Geometric Inhomogeneous Random Graphs in Linear Time. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2017.20,
  author =	{Bringmann, Karl and Keusch, Ralph and Lengler, Johannes},
  title =	{{Sampling Geometric Inhomogeneous Random Graphs in Linear Time}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.20},
  URN =		{urn:nbn:de:0030-drops-78396},
  doi =		{10.4230/LIPIcs.ESA.2017.20},
  annote =	{Keywords: real-world networks, random graph models, sampling algorithms, compression algorithms, hyperbolic random graphs}
}

Refine by Author
1 Bringmann, Karl
1 Keusch, Ralph
1 Lengler, Johannes

Refine by Classification

Refine by Keyword
1 compression algorithms
1 hyperbolic random graphs
1 random graph models
1 real-world networks
1 sampling algorithms

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Keusch, Ralph"

Sampling Geometric Inhomogeneous Random Graphs in Linear Time

Abstract

Cite as

Thanks for your feedback!

Could not send message