EUVIMEDEUVIMED entdecken
Crossref

The diameter of KPKVB random graphs

Tobias Müller, Merlijn Staps

Advances in Applied Probability · 2019-06 · 51 (2) · 358-377

DOI: 10.1017/apr.2019.23 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Applied Probability, online erschienen am 07.08.2019. Verfasst von Tobias Müller und 1 weiteren Autor:innen. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 17 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider a random graph model that was recently proposed as a model for complex networks by Krioukov et al. (2010). In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has previously been shown that this model has various properties associated with complex networks, including a power-law degree distribution and a strictly positive clustering coefficient. The model is specified using three parameters: the number of nodes N , which we think of as going to infinity, and $\alpha, \nu > 0$ , which we think of as constant. Roughly speaking, $\alpha$ controls the power-law exponent of the degree sequence and $\nu$ the average degree. Earlier work of Kiwi and Mitsche (2015) has shown that, when $\alpha \lt 1$ (which corresponds to the exponent of the power law degree sequence being $\lt 3$ ), the diameter of the largest component is asymptotically almost surely (a.a.s.) at most polylogarithmic in N . Friedrich and Krohmer (2015) showed it was a.a.s. $\Omega(\log N)$ and improved the exponent of the polynomial in $\log N$ in the upper bound. Here we show the maximum diameter over all components is a.a.s. $O(\log N),$ thus giving a bound that is tight up to a multiplicative constant.

Zitieren

APA

Müller, T., & Staps, M. (2019). The diameter of KPKVB random graphs. Advances in Applied Probability, 51(2), 358-377. https://doi.org/10.1017/apr.2019.23

Vancouver

Müller T, Staps M. The diameter of KPKVB random graphs. Advances in Applied Probability. 2019;51(2):358-377. doi:10.1017/apr.2019.23

BibTeX
@article{Mller2019,
  author = {Müller, Tobias and Staps, Merlijn},
  title = {The diameter of KPKVB random graphs},
  journal = {Advances in Applied Probability},
  year = {2019},
  volume = {51},
  number = {2},
  pages = {358--377},
  doi = {10.1017/apr.2019.23}
}
Kostenlos starten →