Schedule for: 24w4004 - Mathematical Foundations of Network Models and their Applications

Meet at the hotel lobby

Short presentations of open problems by those who submitted them

Location will be announced at the start of each workshop.

Some at CMI, some at hotel.

Meet at the hotel lobby

We consider several distributions for a random permutation of Z, including Mallows and other Gibbs measures weighted by the displacements and the churn (the number of $i\lex$ with $\sigma_i>x$). Under mild assumptions the cycle structure for these has a universal scaling limit which we study. Joint with Christina Goldschmidt, Ander Holroyd, Tom Hutchcroft, and James Martin.

In this talk we present with the poaching and self-employment model a Markov chain with values in finite graphs of a given size. This model is closely linked to a classic model from population genetics, the so-called infinite alleles model. We will demonstrate how techniques from the theory of interacting particle systems and measure-valued processes can be used to analyse this Markov chain.

In this talk we will consider a competition between two growth models with long-range correlations on the torus $\T_n^d$ of size $n$ in dimensions $d$. From two source vertices, two first-passage percolation (FPP) processes start flowing on the torus, and compete to cover the sites. The FPP processes we consider are long-range first-passage percolation processes, as studied by Chatterjee and Dey (https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21571), in the instantaneous percolation regime (a regime of low dependence on the underlying geometry), with different rates and different long-range parameters, that we allow to depend on $n$. We will see interesting phase transitions in the size of the weaker FPP type, depending on the rate of the stronger type. We will discuss the key techniques and ideas, some particular examples, and some interesting open problems. (Joint work with Bas Lodewijks, University of Augsburg)

In this talk we discuss the voter model with binary opinions on a random regular graph with $n$ vertices of degree $d \geq 3$, subject to a rewiring dynamic in which pairs of edges are rewired, i.e., broken into four half-edges and subsequently reconnected at random. A parameter $\nu \in(0, \infty)$ regulates the frequency at which the rewirings take place, in such a way that any given edge is rewired exponentially at a rate $\nu$ in the limit as $n \rightarrow \infty$. We show that, under the joint law of the random rewiring dynamics and the random opinion dynamics, the fraction of vertices with either one of the two opinions converges on time scale $n$ to the Fisher-Wright diffusion with diffusion constant $\vartheta_{d, v}$ in the limit as $n \rightarrow \infty$. We also show that the fraction of discordant edges converges to the product of the fractions of the two opinions, which is a manifestation of homogenisation. We identify $\vartheta_{d, \nu}$ in terms of a continued-fraction expansion and analyse its dependence on $d$ and $\nu$. This a joint work with Luca Avena, Rangel Baldasso, Frank den Hollander and Matteo Quattropani.

Location will be announced at the start of each workshop.

Some at CMI, some at hotel.

Meet at the hotel lobby

In a world of polarized opinions on many cultural issues, we propose a model for the evolution of opinions on a large complex network. Our model is akin to the popular Friedkin-Johnsen model, with the added complexity of vertex-dependent media signals and confirmation bias, both of which help explain some of the most important factors leading to polarization. The analysis of the model is done on a directed random graph, capable of replicating highly inhomogeneous real-world networks with various degrees of assortativity and community structure. Our main results give the stationary distribution of opinions on the network, including explicitly computable formulas for the conditional means and variances for the various communities. Our results span the entire range of inhomogeneous random graphs, from the sparse regime, where the expected degrees are bounded, all the way to the dense regime, where a graph having n vertices has order n^2 edges.

The p-spin Ising model is a generalization of its classical 2-spin analogue, used as a framework for multi-body interactions. In this presentation, I will talk about the different phases in the p-spin Ising parameter space induced by the different natures of asymptotics of the magnetization vector, parameter estimates and heat-bath Glauber dynamics mixing time. This talk is a collection of my past and ongoing works with Bhaswar Bhattacharya, Jaesung Son, Sanchayan Bhowal and Ramkrishna Samanta.

The large population limits of contact processes in homogeneous populations, on lattices and on general fixed graphs are quite well understood. We consider a process where the graph itself is dynamic and changes in response to the contact process, thus creating interaction between the two processes. In the specific scaling regime we consider, surprisingly clean equations emerge which allows us to describe the full limiting graphon-valued diffusion.

Location will be announced at the start of each workshop.

Meeting outside of the auditorium

Some at CMI, some at hotel.

Meet at the hotel lobby

Dense graphs are used to model a variety of mathematical objects, for example, friendship networks and neural networks. Often, these networks are not static but evolve over time with the goal of minimizing some objective function. Naturally, one expects that the evolutions of the edge weights are correlated and in practical examples (e.g. neural networks) the size of the network is also large. This makes the analysis of the network evolution challenging. One fruitful idea that has emerged over the past decade is to investigate the limits of these dynamics as the network size goes to infinity. In this talk, we explain the idea of using graphon limits to analyze a class of dynamics on large graphs.

Collapsed branching processes (CBP) are directed random networks obtained by collapsing families of random sizes in a general continuous time branching process driven by a sublinear function f. When f is affine, i.e. linear or constant, the process corresponds to the preferential or uniform attachment models with random out-degrees. The local weak limits of the CBP is described by a related continuous time branching process that is stopped at an independent exponential time. Further, the in-components of a finite collection of uniformly chosen vertices converge to i.i.d copies of the above limit. The proof follows from a coupling of the in components of the vertices with the limiting objects. As special cases, we obtain descriptions of the local weak limits of directed preferential and uniform attachment models. We also obtain upper and lower bounds on the tail of the in-degree distribution as a consequence.

Upon almost-every realisation of the Brownian continuum random tree (CRT), it is possible to define a canonical diffusion process or ‘Brownian motion’. I will discuss a recent result that establishes the cover time of the Brownian motion on the Brownian CRT (i.e. the time taken by the process in question to visit the entire state space) is equal to the infimum over the times at which the associated local times are strictly positive everywhere. The proof of this result depends on the recursive self-similarity of the Brownian CRT and a novel version of the first Ray-Knight theorem for trees, which is of independent interest. As a consequence, it can be deduced that the suitably-rescaled cover times of simple random walks on critical, finite variance Galton-Watson trees converge in distribution with respect to their annealed laws to the cover time of Brownian motion on the Brownian CRT. Other families of graphs that have the Brownian CRT as a scaling limit are also covered. Additionally, the result partially confirms a 1991 conjecture of David Aldous regarding related cover-and-return times. This project is joint with George Andriopoulos (NYU Abu Dhabi), Vlad Margarint (Charlotte) and Laurent Menard (Paris Nanterre).

In this talk, we present two methods for cutting random recursive trees that aim at reducing the number of steps until the tree is destroyed. The first method deterministically deletes vertices in decreasing order of their degrees, while the second method deletes vertices randomly chosen and biased according to their degree. We compare the current bounds for these models with the classic cutting process of uniformly chosen vertices in random recursive trees.

We introduce a family of network models with a hierarchical granularity structure that naturally arises through finer and coarser population labelings. The structure is easily visualized by merging and shattering vertices, while respecting the edge structure. The family provides a connection of practical and theoretical interest between the Hollywood model of Crane and Dempsey, and the generalized-gamma graphex model of Caron and Fox. A key ingredient for the construction of the family is fragmentation and coagulation duality for integer partitions, and for this we develop novel duality relations that generalize those of Pitman and Dong, Goldschmidt and Martin.

Location will be announced at the start of each workshop.

Some at CMI, some at hotel.

Meet at the hotel lobby

In this talk, we would like to give an overview on recent and past results on large deviations for sparse random graphs and coagulation processes. In particular, recently there have been progresses in the study of inhomogeneous random graphs and random graphs with marks in this framework, with some interesting similarities between different models appear when studying their large deviation rate functions. On the other hand, an approach that exploits the description of interaction in spatial coagulation processes with random tree-like structures has proved useful in proving large deviations for such Markov processes. We will describe such approach and outline possible future directions.

In this paper, we study the annealed ferromagnetic q-state Potts model on sparse rank-1 random graphs, where vertices are equipped with a vertex weight, and the probability of an edge is proportional to the product of the vertex weights. In an annealed system, we take the average on both numerator and denominator of the ratio defining the Boltzmann-Gibbs measure of the Potts model. We show that the thermodynamic limit of the pressure per particle exists for rather general vertex weights. Further, we identify the critical inverse temperature. In the infinite-variance weight case, we show that the critical temperature equals infinity. For finite-variance weights, we show that, under a very general condition, the phase transition is first order for all q\geq 3. However, we cannot generally show that the discontinuity of the order parameter is unique. We prove this uniqueness under a reasonable condition that holds for various distributions, including uniform, gamma, log-normal, Rayleigh distributions. In the special case of Pareto distributions with power-law exponent \tau, we show that the phase transition is first-order when \tau>4, so that the weights have finite third moment, but not necessarily when \tau\in(3,4). In this important case, we prove that the phase transition is second order for \tau\in (3,\tau(q)], in which case we can give an explicit expression for the critical value, while it is first order when \tau>\tau(q), where \tau(q) satisfies an explicit condition. [This talk is based on joint work with Cristian Giardinà, Claudio Giberti, Guido Janssen and Neeladri Maitra.]

Consider a set of n agents, each of whom has a single message to convey to all other agents. The messages are all of the same length. Time is divided into rounds, and during each round, each agent may broadcast a single message. Agents are represented as nodes of a directed communication graph, and a broadcast is received error-free by all (out)-neighbours of the broadcasting node. The problem is to minimise the number of rounds until all agents have received all messages.

In (supercritical) Bernoulli bond percolation on $\mathbb{Z}^d$, the proportion of vertices in the largest cluster restricted to a volume-$n$ box converges to $\theta$: the probability that the origin lies in an infinite cluster. The probability that this proportion is smaller than $\theta-\varepsilon$ decays stretched exponentially with exponent strictly smaller than one. The probability that the largest cluster is much larger than expected decays exponentially. Thus, the upper tail decays much faster than the lower tail. In this talk, we will see that the discrepancy between the tails is reversed in supercritical spatial random graph models in which the degrees have heavy tails. In particular, we will focus on the soft heavy-tailed Poisson-Boolean model. The lower tail decays stretched exponentially, with an exponent that is determined by the strongest of three competing effects. In contrast, the upper tail decays now polynomially, and thus decays much slower than the lower tail. The exponent of this polynomial is determined by the generating function of the finite cluster-size distribution.

Location will be announced at the start of each workshop.