Random Hyperbolic Graphs: Degree Sequence and Clustering

Recently, Papadopoulos, Krioukov, Boguñá 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 for models of large real-world graphs, such as high clustering and heavy tailed degree distributions. By computing explicitly a maximum likelihood fit of the Internet graph, they demonstrated impressively that this model is adequate for reproducing the structure of such 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.