Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, June 19, 2023, 04:15 pm
Duration: 30 minutes
Location: OAT S 13
Speaker: Leon Schiller (Hasso-Plattner Institute, Potsdam, Germany)
Random graph models are useful tools for bringing theoretical analyses of algorithms closer to empirical observations. One random graph model that particularly attracted the attention of researchers in this regard are geometric inhomogeneous random graphs (GIRGs) which were found to reproduce the characteristic properties of many realistic instances. This is achieved by randomly distributing n vertices in a d-dimensional torus and subsequently expressing the probability that two vertices are adjacent as a function of their heterogeneous weights and their distance. GIRGs can also be seen as a generalization of hyperbolic random graphs (HRGs) with the main novelty that the dimension of the underlying space is freely adjustable. In spite of this, it is still largely unexplored how this new parameter explicitly influences the properties of the resulting graphs. In this talk, we present first results that address this question and further complement existing research on the behavior of random geometric graphs (RGGs) in high dimensions. We prove that, in the infinite-dimensional limit, GIRGs lose their geometry, i.e., they converge in total variation distance to their non-geometric counterparts (Chung–Lu graphs) where edges are sampled independently of each other. To quantify how quickly this transition occurs and how it impacts important graph structures, we further study the number, size, and position of cliques and identify phase transitions at which their behavior changes fundamentally. Our analysis covers all relevant parameter regimes and generalizes the results of previous work regarding the clique structure of GIRGs. We conclude that geometric effects prevail as long as d is asymptotically smaller than log(n), which manifests in a large number of cliques forming among vertices of low weight. On the other hand, if d scales faster than log(n), the clique structure of our model behaves essentially like that of a Chung–Lu Graph, whereby slightly stronger results apply if d scales faster than log(n)^2. We conclude the talk by giving an overview of how our results compare to what is known for other geometric random graph models and by presenting further open questions and possible starting points for future research we identified.
Automatic MiSe System Software Version 1.4803M | admin login