MARK KAC SEMINAR

A growing family of random graphs is called robust if it retains a giant component after percolation with arbitrarily small positive retention probability. We study robustness for graphs, in which new vertices are given a spatial position on the unit circle and are connected to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering we can independently tune the power law exponent τ of the degree distribution and the exponent δ at which the connection probability decreases with the distance of two vertices. We show that the network is robust if τ < 2 + 1/δ, but fails to be robust if τ > 2 + 1/(δ-1). This is the first instance of a scale-free network where robustness depends not only on its degree distribution but also on its clustering features. This is joint work with Emmanuel Jacob (ENS Lyon).

In this talk, I will describe some recent and ongoing work on various models of random graphs embedded in the hyperbolic plane. The talk is partly based on joint works with Michel Bode, Erik Broman, Nikolaos Fountoulakis and Johan Tykesson.

Random geometric graphs are obtained by taking a random set of points in the plane (usually either generated by a Poisson process or sampled i.i.d. uniformly from a large disk or square), and then joining any pair of points by an edge whose distance is less than some parameter r>0. The subject essentially goes back to the work of E.N. Gilbert, who defined a very similar model in 1961. They have since become the focus of considerable research effort and very precise answers are now known to many of the natural questions for this model.

A natural question is what happens if we define this model not on the ordinary Euclidean plane but instead on the hyperbolic plane. In an ongoing joint work with Erik Broman and Johan Tykesson we consider one possible and natural definition of hyperbolic random geometric graphs: We take a constant intensity Poisson process on the hyperbolic plane, join two points by an edge if the distance is less than some (constant) r>0, and we discard all points outside of a disk of (large) radius. We then consider the number of points in the largest component. It turns out that, perhaps surprisingly, strikingly different behaviour occurs from the Euclidean case.

Perhaps even more surprisingly, it turns out that for some choices of the parameters, hyperbolic random geometric graphs display features that are usually associated with so-called complex networks. Famously, around the turn of the century it was noted that many “real” networks stemming from diverse fields (chemical reaction networks, the internet and social networks) share certain characteristics. Ordinary, Euclidean random geometric graphs, as well as the hyperbolic version we study with Broman and Tykesson, are very far from showing these characteristics, but recently Krioukov – Papadopoulos – Kitsak – Vahdat – Boguna observed that there is a way to define random geometric graphs on the hyperbolic plane such that they display these characteristics. In two joint works with Michel Bode and Nikolaos Fountoulakis we studied the largest component and the transition from a disconnected to a connected graph in this model. In both cases our results are very different from the results for all other models in the literature as far as we are aware.