On the largest component of a hyperbolic model of complex networks (Q490412)

Summary: We consider a model for complex networks that was introduced by \textit{D. Krioukov} et al. [``Hyperbolic geometry of complex networks'', Phys. Rev. E 82, 036106 (2010; \url{doi:10.1103/PhysRevE.82.036106})]. 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 \textit{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\).