EUVIMEDEUVIMED entdecken
Crossref

On the Diameter of Hyperbolic Random Graphs

Tobias Friedrich, Anton Krohmer

SIAM Journal on Discrete Mathematics · 2018-01 · 32 (2) · 1314-1334

DOI: 10.1137/17m1123961 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 12.06.2018. Verfasst von Tobias Friedrich und 1 weiteren Autor:innen. Die Arbeit wurde bisher 32-mal zitiert (Crossref) und nennt 37 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the Internet can be mapped to a hyperbolic space such that geometric greedy routing is close to optimal [M. Bogun͂á, F. Papadopoulos, and D. Krioukov, Nature Commun., 1 (2010), pp. 1--62]. This observation has pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power law degree distribution with controllable exponent $\beta$ and show high clustering [L. Gugelmann, K. Panagiotou, and U. Peter, Proceedings of the 39 th International Colloquium on Automata, Languages and Programming, 2012, pp. 573--585]. For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is $\mathcal{O}((\log n)^{32/((3-\beta)(5-\beta)) + 1})$ [M. Kiwi and D. Mitsche, Proceedings of ANALCO, 2015, pp. 26--39]. We present two much simpler proofs for an improved upper bound of $\mathcal{O}((\log n)^{2/(3-\beta)})$ and a lower bound of $\Omega(\log n)$. If $\beta > 3$, we show that the latter bound is tight by proving an upper bound of $\mathcal{O}(\log n)$ for the diameter.

Förderung

  • Deutsche Forschungsgemeinschaft

Zitieren

APA

Friedrich, T., & Krohmer, A. (2018). On the Diameter of Hyperbolic Random Graphs. SIAM Journal on Discrete Mathematics, 32(2), 1314-1334. https://doi.org/10.1137/17m1123961

Vancouver

Friedrich T, Krohmer A. On the Diameter of Hyperbolic Random Graphs. SIAM Journal on Discrete Mathematics. 2018;32(2):1314-1334. doi:10.1137/17m1123961

BibTeX
@article{Friedrich2018,
  author = {Friedrich, Tobias and Krohmer, Anton},
  title = {On the Diameter of Hyperbolic Random Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2018},
  volume = {32},
  number = {2},
  pages = {1314--1334},
  doi = {10.1137/17m1123961}
}
Kostenlos starten →