8 Days on Network Mathematics

This informal international workshop will be focused on stochastic networks, spatial stochastic processes, and their dynamics. It will contain three thesis defenses and a series of one hour lectures given by researchers active in the field.

Where: INRIA Paris, 2 rue Simone Iff Paris.

When: September 18 to 27, 2023.

Organizer: ERC NEMO.

Registration: https://forms.gle/kbxJgAJTQrYuBSKy5

Online attendance: https://inria.webex.com/inria/j.php?MTID=m77683f1b8c6daa74ca10241122912297 (separate links for the PhD defenses, please contact the defendant directly if you want to attend)

Titles and Abstracts

Charles Bordenave – CNRS Marseille

Mobility edge, the Poisson Infinite weighted tree of Aldous and Lévy Matrices

Anderson’s 1958 paper on wave scattering in disordered media is still of central importance in contemporary mathematical physics. In this talk, we will present recent progress in understanding the phenomena of localization / delocalization of eigenwaves for some random operators. These operators are built on random trees introduced by Aldous and these are the scaling limits of heavy-tailed random matrices, the Lévy matrices. The focus will be put on the existence of a mobility edge, that is to say of an abrupt transition between localization and delocalization of eigenwaves. It is a work in collaboration with Amol Aggarwal (Columbia) and Patrick Lopatto (NYU).

Pierre Calka – Université de Rouen

Typical and extremal results for random polytopes in smooth convex bodies

We consider the random polytope generated by n independent and uniformly distributed points in a smooth convex body. We are interested in studying the typical and extremal distributions of several functionals of the facets of the random polytope, which are the distance to the boundary, the volume and the diameter. Each of those functionals is coupled with the relative position of the facet, which is given by a boundary point of the underlying smooth convex body. We exhibit in particular explicit limit distributions for the typical distributions and prove similar explicit convergences of measures associated to the extreme value regime, including convergence in total variation. This leads us in particular to getting limiting extreme value distributions for the distance to the boundary and for the volume. In the particular case of dimension two and when the underlying convex body is an Euclidean ball, we obtain that the limit distribution of the typical height resembles a Tracy-Widom distribution. Moreover, the corresponding height process satisfies a so-called 1:2:3 scaling property which makes it similar to the growth processes from the infamous KPZ universality class, even though the limit process, known as the Burgers’ festoon, does not involve any Airy process. This is joint work with Joe Yukich.

Nicolas Curien – Université Paris Saclay

Ideal Poisson-Voronoi tiling

We study the limit in low intensity of Poisson–Voronoi tessellations in hyperbolic spaces. In contrast to the Euclidean setting, a limiting non-trivial ideal tessellation appears as the intensity tends to 0. The tessellation obtained is a natural Möbius-invariant decomposition of the hyperbolic space into countably many infinite convex polytopes, each with a unique end. We study its basic properties, in particular the geometric features of its cells. Based on joint works with Matteo d’Achille, Nathanel Enriquez, Russell Lyons and Meltem Unel.

Michel Davydov – Inria de Paris

Point-process-based Markovian dynamics and their applications

In this thesis, we are interested in mathematical models of phenomena that can be interpreted as network dynamics. This includes for example neuron population models in which neurons interact at random times with their neighbors or epidemics propagation where infected or susceptible individuals move from town to town. The mathematical description of such phenomena generally requires a compromise between physical or biological relevance and mathematical tractability. The main focus of this work is the elaboration of mathematical proofs to justify the introduction of models taking into account the geometry of the underlying networks whilst preserving tractability. The main mathematical tool for that purpose is the replica-mean-field, which consists in copies of the studied network between which interactions are routed randomly. The main results of this thesis concern the behavior of such a dynamical system when the number of replicas goes to infinity. In various settings, we show that it concerges to dynamics under the Poisson Hypothesis, that is, interaction times are replaced by independent Poisson processes, which allows to obtain closed forms in certain models.

Laurent Decreusefond – Télécom Paris

Invertibility of functionals of the Poisson process and applications

We show that solving SDEs with constant volatility on the Wiener space is the analog of constructing Hawkes-like processes, i.e. self excited point process, on the Poisson space. Actually, both problems are linked to the invertibility of some transformations on the sample paths which respect absolute continuity: adding an adapted drift for the Wiener space, making a random time change for the Poisson space. Following previous investigations by Üstünel on the Wiener space, we establish an entropic criterion on the Poisson space which ensures the invertibility of such a transformation. As a consequence of this criterion, we improve the variational representation of the entropy with respect to the Poisson process distribution. Pursuing the Wiener-Poisson analogy so established, we define several notions of generalized Hawkes processes as weak or strong solutions of some fixed point equations and show a Yamada-Watanabe like theorem for these new equations. As a consequence, we find another construction of the classical (even non linear) Hawkes processes without the recourse to a Poisson measure. Joint work with L. Coutin.

Sergey Foss – Heriot Watt University, UK

On limiting properties of monotone Markov chains

I will present a number of results related to the existence and uniqueness of the stationary distribution of stochastically monotone Markov chains and their generalisations. This is a joint work with Michael Scheutzow (TU Berlin).

Nicolas Gast – INRIA Grenoble

Which approximations for particle systems on graph?

Mean field models are very good approximations of the behavior of particles systems when each particle can interact with everyone else. I many cases, it has been shown to be asymptiotically exact as the number of particles $N$ goes to infinity, with an error that decreases as O(1/N). The situation is different when the interactions between particles are constrained by a graph. When the graph is dense, mean-field like results still apply. But the situation is different for sparse graphs. In this talk, I will focus on two specific models (an information propagation network with interference and a dynamic random graph) and ask the question of what types of approximations can we build and with what performance guarantee? Each model will call for its own methods: refined replica mean field or pair-approximation. This talk may contain more open questions than actual results.

Alexandre Gaudillière – CNRS Marseille

Using Kirchhoff’s forests for network immunisation

We will discuss how one can use Kirchhoff’s random spanning forests to choose which nodes to immunize, or remove, inside a given network in order to make it more resistant from a simple mathematical point of view on epidemic propagations. This is a joint work with Irina Gurewitsch, Luca Avena and Michael Emmerich.

Sayeh Khaniha – Inria de Paris

Unimodularity in Random Networks: Applications to the Null Recurrent Doeblin Graph and Hierarchical Clustering

This thesis is based on the notion of unimodularity in the context of random networks and explores two domains of application: Coupling from the Past in the null recurrent case based on the associated Doeblin Graphs and unsupervised classification based on hierarchical clustering on point processes. The first part of this thesis focuses on the properties of a specific random graph called the Doeblin Graph, which is associated with the Coupling from the Past algorithm used for perfect sampling of the stationary distribution of a Markov Chain. In the irreducible, aperiodic, and positive recurrent case, it is known that the Bridge Doeblin Graph, a subgraph of the Doeblin Graph, is an infinite tree that is unimodularizable and contains a unique biinfinite path. This bi-infinite path plays a crucial role in constructing a perfect sample of the stationary state of the Markov chain. This thesis extends the study to the null recurrent case, where it is shown that the Bridge Doeblin Graph is either an infinite tree or a forest composed of a countable collection of infinite trees. In the former case, the infinite tree possesses a single end, is not generally unimodularizable, but exhibits local unimodularity. These properties are leveraged to investigate the stationary regime of measure-valued random dynamics on the Bridge Doeblin Tree, particularly the taboo and potential random dynamics. The second part of this thesis introduces a novel hierarchical clustering model tailored for unsupervised classifications of datasets which are countably infinite. Clustering, a widely used technique in unsupervised learning, aims to identify groups within a dataset based on element similarities. The proposed algorithm employs multiple levels of clustering, constructing clusters at each level using nearest-neighbor chains of points or clusters. This algorithm is applied to the Poisson point process, and it is proven that the clustering algorithm defines a phylogenetic forest on the Poisson point process, which is a factor of the point process and is therefore unimodular. Various properties of this random forest, such as the mean sizes of clusters at each level or the mean size of the cluster of a typical node, are examined.

Ali Khezeli – Inria de Paris

On the Existence of Balancing Allocations and Factor Point Processes

Let $\Phi$ and $\Psi$ be ergodic stationary random measures on $\mathbb R^d$. The study of balancing allocations and balancing transport kernels between $\Phi$ and $\Psi$ has been of great interest in the last two decades. This was started by the novel work [Hoffman, Holroyd and Peres, 2005], which provided a generalization of the stable marriage algorithm and constructed a balancing allocation between the Lebesgue measure and the Poisson point process. For the existence of factor allocations in general, it is necessary that $\Phi$ and $\Psi$ have the same intensity, but no simple necessary and sufficient condition is known yet. Recently, [Last, Thorisson, 2023] provided the sufficient condition that $\Phi$ is diffuse (i.e., has no atoms) and there exists a point process as a factor of $(\Phi,\Psi)$. It was conjectured in [Khezeli, 2016] that there always exists a factor point process provided that $(\Phi,\Psi)$ has no nontrivial symmetry a.s. In this talk, we prove this conjecture by using the results of the theory of Borel equivalence relations. Meanwhile, we will provide a quick introduction into this theory and its applications in probability theory. Based on joint work with Samuel Mellick.

Raphaël Lachièze-Rey – Univesité Paris Cité

Matching of dependent point processes

The celebrated Ajtai-Komlos-Tusnady Theorem and its generalisations give the magnitude of the optimal total matching distance between two iid samples of points with Lebesgue intensity on the unit cube. This quantity can be equivalently computed as the Wasserstein distance on a cube between Lebesgue measure and a homogeneous Poisson process. In this work, we generalise this result to dependent samples of points, and in particular to the restriction on a compact window of a stationary random measure, and show that under mild conditions the expected Wasserstein distance magnitude does not exceed that of iid/Poisson input. We also investigate the case of Hyperuniform point processes, including many models of random matrices and Coulomb gases. Such processes are defined as having a low variance for the number of points on a large window, and are expected to behave globally as perturbed lattices, despite a locally disordered structure. We prove that their expected transport cost is indeed comparable to that of a perturbed lattice, which yields in particular that in dimension 1 and 2 this cost is negligible with respect to that of disordered processes such as Poisson processes. Joint work with Yogeshwaran D.

Eva Löcherbach – Université Paris Panthéon Sorbonne

Conditional propagation of chaos for generalized Hawkes processes having alpha-stable jump heights

This is a joint work with Dasha Loukianova (Université d’Evry). We study the convergence of systems of interacting particles driven by Poisson random measure, having mean field interactions and position dependent jump rate. Jumps are simultaneous, that is, at each jump time, all particles of the system are affected by this jump and receive a positive random jump height. This random kick is distributed according to a one-sided alpha-stable law and scaled in N^{-1/alpha}, where N is the size of the system. This particular scaling implies that the limit of the empirical measures of the system is random, describing the conditional distribution of one particle in the limit system. Such limits are conditional McKean-Vlasov limits. The conditioning in the limit measure reflects the dependencies between coexisting particles in the limit system such that we are dealing with a conditional propagation of chaos property. I will spend some time to explain the explicit structure of the limit system which turns out to be the solution of a non-linear SDE driven by Poisson random measure and an independent alpha-stable subordinator. In a second part of the talk I discuss strong error bounds allowing us to control the rate of convergence of the finite particle system to the limit system.

Eric Luçon – Université Paris Cité

How large is the mean-field framework ? LLN and CLT for empirical measures of diffusions on (random) graphs

A common hypothesis for mean-field models is to suppose all-to-all interaction between N particles (the interaction is on the complete graph) with uniform coupling along the population. The motivation of the talk is simple : what happens if one removes edges in the graph of interaction ? the coupling is no longer a functional of the empirical measure of the system, but rather of local empirical measures around each vertex. Under what condition on the graph of interaction do these empirical measures behave as in the mean-field framework as $N\to\infty$ ? We address this question of universality both at the level of the law of large numbers and fluctuations, for a large class of possibly random graphs, including the Erdös-Rényi class. This is based on joint works with S. Delattre, G. Giacomin and F. Coppini and C. Poquet.

Ravi R. Mazumdar – University of Waterloo, Canada

Adaptive multi-rate loss models: A new class of models for studying parallelizable systems

In this talk I will introduce a new class of models that are of relevance in the context of parallelization in multiserver systems. In particular we consider adaptive multi-rate multi-server jobs where each job can be split into a flexible number of sub-jobs up to a maximum limit d. The number of sub-jobs depends on the number of available servers found upon the jobs arrival. All sub-jobs of a job are then processed in parallel and the speed-up is assumed to be a concave increasing sublinear function of the degree of split or parallelization. We analyse the speed-up in the mean delay obtained in a large system. Of interest is the sample size k(n), which represents the number of accessible servers upon job arrival. When the full system is accessible, i.e., k(n) = n, we show that the blocking probability approaches to zero at the rate O(1/√n) and the mean response time of accepted jobs approaches to its minimum value at rate O(1/n) as n → ∞. In cases with the limited system access, i.e., k(n) < n, we show that as long as k(n) = ω(1) in the sub-critical regime and k(n) = ω(√n) in the Halfin-Whitt regime, the same asymptotic performance can be achieved as in the full access. In particular, for k(n) = Θ(√n log n), we show that both the blocking probability and the mean response time approach to their desired limits at rate O(n^{−1/4} ). In particular we show a state-space collapse takes place and the stationary distribution can be obtained from the analysis of certain fluid limits. When k(n) = n and if the speed-up function is linear then the state-space is of dimension 1 that allows for maximal gain d while if it is sub-linear then the state-space is of dimension 2 and the average speed-up lis less than the maximal speed-up which can be precisely obtained. The approach is via the use of Stein’s method and Lyapunov drift techniques. Joint work with S. Ghanbarian (Waterloo), F. Guillemin (Orange), and A. Mukhopadhyay (Warwick).

Eliza O’Reilly – Johns Hopkins University, USA

Random Tessellation Forests for High-dimensional Data

Random forests are a popular class of algorithms used for regression and classification that are ensembles of randomized decision trees built from axis-aligned partitions of the feature space. One particular variant, called Mondrian random forests, were proposed to handle the online setting and are the first class of random forests for which minimax optimal rates were obtained in arbitrary dimension. However, the restriction to axis-aligned splits fails to capture dependencies between features, and oblique splits have shown improved empirical performance. Theoretical rates for the Mondrian also suffer from the curse of dimensionality as the partitioning process does not prioritize relevant
features. By viewing the Mondrian as a special case of the stable under iteration (STIT) process, we utilize the theory of stationary random tessellations to show that a large class of random forests with oblique cuts can achieve minimax optimal rates and illustrate how improved rates in high dimensional feature space can be obtained with a data-driven choice of split directions. This talk is based on joint works with Ngoc Mai Tran, Ricardo Baptista, and Xinyu Xie.

Bharath Roy Choudhury – Inria de Paris

Records of stationary processes and unimodular graphs

Consider a navigation rule defined on a graph that maps every vertex of the graph to a vertex in such a way that the navigation rule commutes with every automorphism of the graph. It is to say that the navigation rule applied to the vertices remains the same after taking any automorphism of the graph. Such a navigation rule is said to have the covariance property. This study delves into a collection of such covariant navigation rules, indexed by locally finite graphs, and subject to a measurability condition. This ensemble of rules is termed a vertex-shift. More generally, one can consider vertex-shifts on networks, graphs that have labels on edges and on vertices. A vertex-shift induces a dynamic on the space of locally finite rooted networks. The central focus of this work lies in investigating the dynamic associated to a specific navigation rule called the record vertex-shift. It is defined on the trajectories of any one dimensional discrete random walk whose increments have finite mean and the random walk can jump only one step to the left. Additionally, the work includes several notable results concerning record vertex-shifts applied to processes with stationary increments. The thesis also contains results on more general vertex-shifts on unimodular networks.

Adam Timar – University of Iceland and Alfred Renyi Institute of Mathematics, Hungary

Factor of iid’s through stochastic domination

Consider some random field (coloring, subgraph…) of an infinite transitive graph G. We call it a factor of iid process, if we can obtain it from an iid process on the vertices using an equivariant measurable map.One can naturally generalize these concepts to unimodular random graphs. We will talk about such representations for the Uniform Spanning Forest (USF), the Ising model and others, when G is amenable. A simple new method, using stochastic domination, will allow us to represent these as factors of iid (with the necessary assumption of a unique Gibbs measure in case of the Ising model). Many of these were known, but among the new corollaries is a representation of the USF of recurrent graphs as a factor of iid. Finally we will talk about invariant generating sets of cycle spaces and its connections to some factor of iid processes.

Hermann Thorisson – University of Iceland

Convergence in Density and the Skorokhod Representation

According to the Skorokhod representation theorem extended by Dudley and Wichura to hold on a separable set, convergence in distribution is equivalent to the existence of a coupling with elements converging a.s. in the metric. A density analogue of this theorem says that a sequence of probability densities on a general measurable space has a probability density as a pointwise lower limit if and only if there exists a coupling with elements converging a.s. in the discrete metric (that is, a coupling such that the random elements actually hit the limit and stay there). In this talk we prove the density result, present (and maybe prove) an extension to stochastic processes considered in a widening time window, and finally use that extension to prove the extended Skorokhod representation theorem.

Giovanni Luca Torrisi – CNR Roma, Italy

Sharp deviations and extended CLTs of shot noise and generalized Hawkes processes

We provide sharp deviations and extended CLTs for Poisson shot noise processes with a discrete shot shape. The theoretical results are applied to a class of Poisson cluster point processes with a branching structure, which encompasses Hawkes processes. The proofs are based on the mod-𝜙 convergence theory.