This is the peer reviewed version of the following article: Bode, M., Fountoulakis, N. and Müller, T. (2016), The probability of connectivity in a hyperbolic model of complex networks. Random Struct. Alg., 49: 65-94. , which has been published in final form at doi: 10.1002/rsa.20626 . This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving Unless a licence is specified above, all rights (including copyright and moral rights) in this document are retained by the authors and/or the copyright holders. The express permission of the copyright holder must be obtained for any use of this material other than for purposes permitted by law. • Users may freely distribute the URL that is used to identify this publication. • Users may download and/or print one copy of the publication from the University of Birmingham research portal for the purpose of private study or non-commercial research. • User may use extracts from the document in line with the concept of 'fair dealing' under the Copyright, Designs and Patents Act 1988 (?) • Users may not further distribute the material nor use it for the purposes of commercial gain. Where a licence is displayed above, please note the terms and conditions of the licence govern your use of this document. When citing, please reference the published version. While the University of Birmingham exercises care and attention in making items available there are rare occasions when an item has been uploaded in error or has been deemed to be commercially or otherwise sensitive. If you believe that this is the case for this document, please contact UBIRA@lists.bham.ac.uk providing details and we will remove access to the work immediately and investigate. Abstract We consider a model for complex networks that was introduced by Krioukov et al. [11] . 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 < ν < π.
Furthermore, in REF it was shown that for α < 1/2 the graph is connected a.a.s., whereas for α = 1/2 the probability of being connected tends to 1 if ν ≥ π, and the probability of being connected is otherwise a monotone increasing function in ν that tends to 0 as ν tends to 0.
The probability of connectivity in a hyperbolic model of complex networks
Random Struct. Algorithms
Random Struct. Algorithms
Mathematics Computer Science