The diameter of hyperbolic random graphs

Abstract

We study the graph diameter in the KPKVB model, a recent model of random geometric graphs in the hyperbolic plane that was introduced because it has properties reminiscent of complex networks: it has a power law degree distribution, local clustering and small graph theoretic distances. After introducing the model, we show how it can be approximated by a random geometric graph in the Euclidean plane that turns out to be easier to handle. We then use this approximation to improve previous results on the diameter of KPKVB random graphs, by showing that with probability tending to 1 as the number of vertices tends to infinity, the maximum diameter of the components of the graph is at most a constant times log N. Here N denotes the number of vertices. We also provide a logarithmic lower bound for the diameter that holds with probability tending to 1. This lower bound was already known in the literature. Together, this shows that, asymptotically, the graph diameter in the KPKVB model is logarithmic in the number of vertices.