Geometric Inhomogeneous Random Graphs

摘要: 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 focus literature on theoretical models for real-world shifted from classic without geometry, Chung-Lu random graphs, to modern geometry-based models, hyperbolic graphs. With this paper we contribute analysis these modern, more realistic graph models. However, do not directly study but replace them by a general model call \emph{geometric inhomogeneous graphs} (GIRGs). Since ignore constant factors edge probabilities, our technically simpler (specifically, avoid cosines), while preserving qualitative behaviour and suggest graphs new future studies. We prove following fundamental algorithmic results GIRGs. (1) We provide sampling algorithm generates expected linear time, improving best-known factor $O(\sqrt{n})$, (2) establish GIRGs coefficient, (3) show small separators, i.e., it suffices delete sublinear number edges break giant component into two pieces, (4) how compress using bits.