Source-linked AI summary
Random Hyperbolic Graphs: Degree Sequence and Clustering
Luca Gugelmann, Konstantinos Panagiotou, Ueli Peter
TL;DR
The paper addresses the gap between realistic network models and mathematically tractable ones. It rigorously analyzes random hyperbolic graphs, deriving degree-distribution asymptotics and concentration results and proving a constant clustering lower bound. The findings establish power-law degrees through the maximum degree and nonvanishing clustering within the studied model.
Problem
Existing network models often reproduce real-world properties without rigorous analysis, or are tractable without adequately reproducing those properties.
Method
The paper initiates rigorous analysis of random hyperbolic graphs through degree-distribution asymptotics, large-deviation bounds, and clustering-coefficient analysis.
Results
The analysis confirms a power-law degree sequence up to the maximum degree and proves a constant lower bound for clustering, with small probabilities for large deviations.
Takeaways & Limitations
Random hyperbolic graphs provide a rigorously supported model combining scale-free degree behavior and nonvanishing clustering.
Takeaways & Limitations
The paper focuses on degree distribution and clustering; giant-component diameter and greedy routing are left for future work.
Abstract
from arXiv · showhide
In the last decades, the study of models for large real-world networks has been a very popular and active area of research. A reasonable model should not only replicate all the structural properties that are observed in real world networks (for example, heavy tailed degree distributions, high clustering and small diameter), but it should also be amenable to mathematical analysis. There are plenty of models that succeed in the first task but are hard to analyze rigorously. On the other hand, a multitude of proposed models, like classical random graphs, can be studied mathematically, but fail in creating certain aspects that are observed in real-world networks. Recently, Papadopoulos, Krioukov, Boguna and Vahdat [INFOCOM'10] introduced a random geometric graph model that is based on hyperbolic geometry. The authors argued empirically and by some preliminary mathematical analysis that the resulting graphs have many of the desired properties. Moreover, by computing explicitly a maximum likelihood fit of the Internet graph, they demonstrated impressively that this model is adequate for reproducing the structure of real graphs with high accuracy. In this work we initiate the rigorous study of random hyperbolic graphs. We compute exact asymptotic expressions for the expected number of vertices of degree k for all k up to the maximum degree and provide small probabilities for large deviations. We also prove a constant lower bound for the clustering coefficient. In particular, our findings confirm rigorously that the degree sequence follows a power-law distribution with controllable exponent and that the clustering is nonvanishing.
1 Introduction
The paper motivates random hyperbolic graphs as mathematically tractable models intended to reproduce key real-world network properties, then initiates their rigorous analysis. It establishes results on clustering, degree distributions, and large deviations while connecting the model to empirical Internet-network structure.
- Modeling requirements: Accurate network models should reproduce salient real-world features while remaining mathematically tractable and useful for large-scale simulation.The introduction contrasts empirically realistic but difficult models with analytically tractable models that fail to reproduce observed properties.
- Network properties: Real-world networks commonly exhibit small-world structure, power-law degree distributions, and substantial clustering.The passages describe low graph diameter or average path length, scale-free degree sequences, and clustering coefficients often reaching tens of percent.
- Hyperbolic model: Random hyperbolic graphs assign virtual coordinates in hyperbolic space and connect vertices according to their geometric relationships.The model was introduced as a hyperbolic alternative to Euclidean embeddings and was shown empirically to generate scale-free topologies with high clustering.
- Empirical motivation: Maximum-likelihood embedding of the Internet graph produced strong greedy-routing performance, connecting 97% of vertex pairs with average stretch around 1.1.The reported routing performance remained strong even when a fraction of nodes failed.
- Contributions: This work rigorously proves nonvanishing clustering, a power-law degree distribution through the maximum degree, and small probabilities for large deviations.The authors present these results as establishing both desired network properties and concentration sufficient to support experimental validation.
- Novelty: The model is presented as the first rigorous random-graph model known to satisfy both power-law degree behavior and large clustering.The introduction also emphasizes that the scale-free behavior extends up to the maximum degree, beyond results limited to constant or polynomially large degrees.
2 Model & Results
The paper defines random hyperbolic graphs by placing vertices in a hyperbolic disk and connecting sufficiently close pairs, then rigorously analyzes clustering and degree distributions. It proves nonvanishing clustering, power-law degrees, average-degree asymptotics, and maximum-degree bounds under α > 1/2.
- Model: Two vertices are connected exactly when their hyperbolic distance is at most R.The model is a hyperbolic random geometric graph defined through distance thresholding.
- Model: Random hyperbolic graphs use the native hyperbolic representation, with vertices assigned polar coordinates in a disk of radius R = 2 log n + C.The radial coordinates follow a density proportional to α sinh(αr), with α > 1/2.
- Model: α > 1/2 ensures a bounded average degree, whereas α ≤ 1/2 makes the degree sequence too heavy-tailed for this property.The average degree depends on α and C only under the stated parameter restriction.
- Results: A constant lower bound for the global clustering coefficient holds with high probability.This is the paper’s first clustering theorem for Gα,C(n).
- Results: Sharp bounds are established for the number of vertices of degree k, including exact asymptotics across the relevant degree range.The results cover degrees through a polynomial range specified by δ and δ′, and include tail bounds.
- Results: The degree sequence follows a power law with exponent 2α + 1 > 2, while the average degree is (1+o(1)) 2α^2e^−C/2 and the maximum degree is bounded with high probability.The paper also notes that these results confirm earlier findings and focuses on degree distribution and clustering rather than diameter or greedy routing.
3 Properties of the Model
This section develops geometric and measure estimates for the native representation of hyperbolic random graphs. These estimates characterize connection regions and show how their measures vary with radial position and distance.
- Connection regions: A vertex at (θ, r) connects to vertices within hyperbolic distance R, represented by an intersection of hyperbolic balls.The relevant connection region is integrated over radial coordinates and the angular interval satisfying the distance constraint.
- Measure estimates: The measure of an intersection of balls is computed by integrating the radial density over the admissible angular range.Symmetry reduces the angular integration to the interval from −θr(y) to θr(y).
- Measure estimates: The technical lemmas provide almost tight bounds on θr(y) and precise estimates for combinations of hyperbolic balls.These estimates are used repeatedly in later calculations of connection-region measures.
- Radial effects: For the intersection of a vertex's connection ball with the disk, the measure is asymptotically related to e^−r/2, linking radial position to expected degree.The degree of a vertex is described as binomial with this measure as its success probability, so smaller r corresponds to larger expected degree.
- Radial effects: A ball around a point has greater measure when its center is closer to the disk center.The proof establishes this monotonicity by showing that the admissible angular range increases as the radial position decreases.
4 Proofs of the Main Results
The proofs control clustering and degree statistics by restricting attention to well-behaved outer vertices, bounding coordinate effects, and applying concentration inequalities. This yields a constant clustering lower bound, concentrated degree counts, and a high-probability upper bound on maximum degree.
- Proof strategy: Azuma-Hoeffding-type concentration is applied after establishing Lipschitz bounds outside a bad event whose probability is at most e^-Ω(n1−β).The bad event is that an outer vertex has degree at least cn1−β.
- Proof strategy: The proof partitions vertices into inner and outer sets, then restricts target quantities to outer vertices and neighbors with sufficiently large radial coordinates.This makes coordinate changes have bounded influence because the relevant vertices have controlled degrees.
- Clustering coefficient: Theorem 2.1 obtains a constant lower bound on the global clustering coefficient with high probability by showing E[Y] = Θ(n) and concentrating Y.The proof interprets Y through the probability that two randomly chosen neighbors are connected and uses geometric ball intersections.
- Degree sequence: The degree-sequence proof shows that, for every k in the considered range, Dk(β) = (1+o(1))E[Dk(β)] with probability at least 1−e−nΩ(1).The argument partitions vertices into inner and outer sets and proves that most relevant degree-k vertices lie in the outer set.
- Large degrees: A Chernoff bound and union bound show with high probability that no vertex has degree larger than (1 + o(1)) 4eα.This establishes the claimed upper control on the largest degrees.