The probability of connectivity in a hyperbolic model of complex networks1. Issue 1 (3rd June 2016)

• Record Type: Journal Article
• Authors: Bode, Michel; Fountoulakis, Nikolaos; Müller, Tobias
• Is Part Of: Random structures & algorithms. Volume 49:Issue 1(2016)
• Page Start: 65
• Page End: 94
• Publication Date: 2016-06-03
• Subjects: random geometric graphs -- complex networks; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20626
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We consider a model for complex networks that was introduced by Krioukov et al. (Phys Rev E 82 (2010) 036106). In this model, N points are chosen randomly inside a disk on the hyperbolic plane according to a distorted version of the uniform distribution and any two of them are joined by an edge if they are within a certain hyperbolic distance. This model exhibits a power‐law degree sequence, small distances and high clustering. The model is controlled by two parameters α and ν where, roughly speaking, α controls the exponent of the power‐law and ν controls the average degree. In this paper we focus on the probability that the graph is connected. We show the following results. For α > 1 2 and ν arbitrary, the graph is disconnected with high probability. For α < 1 2 and ν arbitrary, the graph is connected with high probability. When α = 1 2 and ν is fixed then the probability of being connected tends to a constant f ( ν ) that depends only on ν, in a continuous manner. Curiously, f ( ν ) = 1 for ν ≥ π while it is strictly increasing, and in particular bounded away from zero and one, for 0 < ν < π . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 65–94, 2016