Law of large numbers for the largest component in a hyperbolic model of complex networks

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Univ Utrecht

Abstract

We consider the component structure of a recent model of random graphs on the
hyperbolic plane that was introduced by Krioukov et al. The model exhibits a power law degree sequence, small distances and clustering, features that are associated with so-called complex networks. The model is controlled by two parameters \alpha and \nu where, roughly speaking, \alpha controls the exponent of the power law and \nu controls the average degree. Refining earlier results, we are able to show a law of large numbers for the largest component. That is, we show that the fraction of points in the largest component tends
in probability to a constant c that depends only on \alpha and \nu, while all other components are sub-linear. We also study how c depends on \alpha and \nu. To deduce our results, we introduce a local approximation of the random graph by a continuum percolation model on the real plane that may be of independent interest.

Details

Original languageEnglish
Pages (from-to)607-650
Number of pages38
JournalAnnals of Applied Probability
Volume28
Issue number1
Publication statusPublished - 3 Mar 2018

Keywords

  • random graphs, hyperbolic plane, giant component, law of large numbers