On the largest component of a hyperbolic model of complex networks

Michel Bode, Nikolaos Fountoulakis, Tobias Müller

Research output: Contribution to journalArticleAcademicpeer-review

63 Downloads (Pure)

Abstract

We consider a model for complex networks that was introduced by Krioukov et al. In this model, N points are chosen randomly inside a disk on the hyperbolic plane and any two of them are joined by an edge if they are within a certain hyperbolic distance. The N points are distributed according to a quasi-uniform distribution, which is a distorted version of the uniform distribution. The model turns out to behave similarly to the well-known Chung-Lu model, but without the independence between the edges. Namely, it exhibits a power-law degree sequence and small distances but, unlike the Chung-Lu model and many other well-known models for complex networks, it also exhibits clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power-law and ν controls the average degree. The present paper focuses on the evolution of the component structure of the random graph. We show that (a) for α > 1 and ν arbitrary, with high probability, as the number of vertices grows, the largest component of the random graph has sublinear order; (b) for α < 1 and ν arbitrary with high probability there is a "giant" component of linear order, and (c) when α = 1 then there is a non-trivial phase transition for the existence of a linear-sized component in terms of ν.

Original languageEnglish
Article number#P3.24
Pages (from-to)1-46
Number of pages46
JournalElectronic Journal of Combinatorics
Volume22
Issue number3
DOIs
Publication statusPublished - 14 Aug 2015

Keywords

  • Component structure
  • Giant component
  • Phase transition
  • Random graphs on the hyperbolic plane

Fingerprint

Dive into the research topics of 'On the largest component of a hyperbolic model of complex networks'. Together they form a unique fingerprint.

Cite this