Contribution
The first rigorous treatment of Krioukov et al.’s hyperbolic random graph. Before it, the degree law and the clustering were shown by a large-distance approximation and simulations (LIT-865); this paper proves both, for the threshold model.
Key results
- Theorem 2.1. E[c] = Θ(1) and c = (1 + o(1))E[c] with high probability, c the average of the local clustering coefficients (a vertex of degree below 2 counts as 0).
- Theorem 2.2. With high probability, for 0 ≤ k ≤ n^δ′ the fraction of vertices of degree exactly k is (1 + o(1)) times (2αe^(−αC)/k!) (2α/(π(α − 1/2)))^(2α) (Γ(k − 2α) − ∫₀^ξ t^(k−2α−1)e^(−t) dt); for larger k up to about n^(1/(2α)), the fraction of degree at least k is (1 + o(1)) (2α/(π(α − 1/2)))^(2α) e^(−αC) k^(−2α). Since Γ(k − 2α)/k! = Θ(k^(−2α−1)), the number of vertices of degree k is (1 + o(1)) c_{α,C} k^(−2α−1) n: a power law with exponent 2α + 1.
- Theorems 2.3–2.4. Average degree (1 + o(1)) 2α²e^(−C/2)/(π(α − 1/2)²); maximum degree n
Method
The ball of radius R around a point at radius r subtends an angle θ_r(y) = 2e^((R−r−y)/2)(1 + Θ(e^(R−r−y))) at radius y (Lemma 3.1), from which the measure of the neighbourhood of a vertex at radius r is (2α/(π(α − 1/2))) e^(−r/2)(1 ± O(e^(−(α−1/2)r) + e^(−r))) (Lemma 3.2): the expected degree falls as e^(−r/2), the large-distance relation of LIT-865 now with its error bounded. Concentration comes from an Azuma–Hoeffding inequality with a bad event (Theorem 4.1), applied only to vertices far from the centre, whose degrees are at most c n^(1−β) except with probability e^(−Ω(n^(1−β))) (Lemma 4.2). The clustering lower bound counts only triangles among outer vertices.
Limitations
- Temperature zero only. The soft model with a distance-dependent connection probability is mentioned and not treated, so nothing here bears on clustering as a function of temperature.
- Curvature fixed at −1. α here plays the role of α/ζ in LIT-865.
- A lower bound for clustering, not a limit. Convergence to a constant was left open (later settled by other authors, not held).
Bearing on the record
Meets the T = 0 half of THEORY-188’s promote_when as a statement: the degree exponent 2α/ζ + 1 (with ζ = 1) and non-vanishing clustering are theorems of the exact model, the large-distance approximation’s error bounded by Lemmas 3.1–3.2. Because the proofs were only followed in outline, the record holds the statements, not a check of them.