NETWORKS

Organiser: Michel Mandjes (University of Amsterdam)

Julia Komjathy (TU Eindhoven)

Explosive information diffusion on scale-free spatial random graphs

In the talk we study weighted distances in scale-free spatial network models, so called geometric inhomogeneous random graphs (GIRG).  In this model, each vertex is given an independent weight and location from the unit cube (or torus) in d dimensions, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We assign i.i.d. weights to the edges of the created random graphs and study the weighted distance between two uniformly chosen vertices. The question is, how does the weight of the minimal weight path scale as the number of vertices tends to infinity? This length corresponds to the transmission time of the information between a source vertex and another vertex.

We give an if and only if condition on the edge-weights for the following phenomenon that is often called ‘explosion’: the time it takes to transfer the information does not grow with the size of the graph, but rather converges in distribution. 

This model – despite its simplicity – can explain why for instance trendy videos on the internet can reach a large proportion of the world’s population in a short amount of time. 

Tobias Müller (Groningen University)

Percolation and random graphs in the hyperbolic plane

In my talk, I will describe some recent and ongoing work on random geometric graphs and Poisson–Voronoi percolation in the hyperbolic plane.

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\). In the Poisson–Voronoi percolation model, we take a constant intensity Poisson process and assign to each point its Voronoi-cell, that is the set of all points closer to it than to any other Poisson point, and then we flip a coin for each cell to determine whether it will be coloured black or white. We say that percolation occurs if the set of black cells contains an unbounded component.

For both these models it turns out that the hyperbolic versions display behaviour that is spectacularly different from their Euclidean counterparts.

(Based on recent and ongoing works with M. Bode, E. Broman,  N. Fountoulakis, B. Hansen, P. van der Hoorn, D. Mitsche,  J. Tykesson, M. Schepers.)

Daniel Dadush (CWI)

On approximating the covering radius and finding dense lattice subspaces

Kannan & Lovasz (Annals of Math `88) asked whether the covering radius of an \(n\)-dimensional Euclidean lattice can be tightly characterized using only volumetric information, namely using only determinants of lattice projections. In a recent breakthrough, Regev and Stephens-Davidowitz (STOC `17) answered this question in the affirmative, showing that the determinant of the “sparsest’’ lattice projection can in fact certify a lower bound on the covering radius that is tight up to polylogarithmic factors in the lattice dimension \(n\). In this work, we first refine this characterization, by showing that using a chain of lattice projections one can in fact certify a lower bound that is tight up to the so-called slicing constant of Voronoi cells, which is conjectured to be \(O(1)\). Second, we make this theory algorithmic by providing a single exponential time algorithm based on discrete Gaussian sampling for computing an \(O(\log^{2.5} n)\)-approximately sparsest lattice projection. For this purpose, we rely heavily upon on the notion of canonical filtration of a lattice, developed by Stuhler in `76 and a reverse Minkowski theorem of Regev and Stephens-Davidowitz.