日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

Geometric Inhomogeneous Random Graphs

MPS-Authors
/persons/resource/persons44182

Bringmann,  Karl       
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

1511.00576.pdf
(プレプリント), 337KB

付随資料 (公開)
There is no public supplementary material available
引用

Bringmann, K., Keusch, R., & Lengler, J. (2016). Geometric Inhomogeneous Random Graphs. Retrieved from http://arxiv.org/abs/1511.00576.


引用: https://hdl.handle.net/11858/00-001M-0000-002C-52F3-4
要旨
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.