hide
Free keywords:
cs.SI,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Networking and Internet Architecture, cs.NI
Abstract:
Real-world networks, like social networks or the internet infrastructure,
have structural properties such as their large clustering coefficient 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. However, we do not directly study
hyperbolic random graphs, but replace them by a more general model that we call
\emph{geometric inhomogeneous random graphs} (GIRGs). Since we ignore constant
factors in the edge probabilities, our model is 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 our new model in future theoretical studies.
We prove the following fundamental structural and algorithmic results on
GIRGs. (1) 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 factor $O(\sqrt{n})$, (2) we establish that
GIRGs have a constant clustering coefficient, (3) we show 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.
