On the largest component of a hyperbolic model of complex networks

Michel Bode¹ ; Nikolaos Fountoulakis¹ ; Tobias Müller²

¹School of Mathematics University of Birmingham United Kingdom
²Mathematical Institute Utrecht University The Netherlands

The electronic journal of combinatorics, Tome 22 (2015) no. 3

Résumé

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 $\alpha$ and $\nu$ where, roughly speaking, $\alpha$ controls the exponent of the power-law and $\nu$ controls the average degree. The present paper focuses on the evolution of the component structure of the random graph. We show that (a) for $\alpha > 1$ and $\nu$ arbitrary, with high probability, as the number of vertices grows, the largest component of the random graph has sublinear order; (b) for $\alpha < 1$ and $\nu$ arbitrary with high probability there is a "giant" component of linear order, and (c) when $\alpha=1$ then there is a non-trivial phase transition for the existence of a linear-sized component in terms of $\nu$. A corrigendum was added to this paper 29 Dec 2018.

Détail

DOI : 10.37236/4958

Classification : 05C80, 05C82
Mots-clés : random graphs, hyperbolic plane, giant component