Clustering in a hyperbolic model of complex networks

Nikolaos Fountoulakis, Pim van der Hoorn, Tobias Müller, and Markus Schepers
Electronic Journal of Probability
Volume 26 (2021), paper no. 13, 132 pp.
January 25, 2021


In this paper we consider the clustering coefficient, and clustering function in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most at a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, “short distances” and a non vanishing clustering coefficient. The model is specified using three parameters: the number of nodes n, which we think of as going to infinity, and α, ν > 0, which we think of as constant. Roughly speaking, the parameter α controls the power law exponent of the degree sequence and ν the average degree.Here we show that the clustering coefficient tends in probability to a constantγ that we give explicitly as a closed form expression in terms of α, ν and certain special functions. This improves earlier work by Gugelmann et al., who proved that the clustering coefficient remains bounded away from zero with high probability, but left open the issue of convergence to a limiting constant. Similarly, we are able to show that c(k), the average clustering coefficient over all vertices of degree exactly k, tends in probability to a limit γ(k) which we give explicitly as a closed form expression in terms of α, ν and certain special functions. We are able to extend this last result also to sequences (kn)n where kn grows as a function of n. Our results show thatγ(k) scales differently, as k grows, for different ranges of α. More precisely, the reexists constants cα,ν depending on α and ν, such that as k → ∞, γ(k) ∼ cα,ν · k2−4αif12 < α < 34, γ(k) ∼ cα,ν · log(k) · k−1if α =34and γ(k) ∼ cα,ν · k−1 when α > 34. These results contradict a claim of Krioukov et al., which stated that γ(k) should alway sscale with k−1as we let k grow.

Related publications