Groningen Stochastics Seminar

If you are interested in giving a talk, please send an email with the title and abstract to b.t.hansen@rug.nl.

Up Next

June 18-20, 2019 Click for Location & Time | Miloš Stojaković
(Novi Sad) | Mini Course: Introduction to Positional Games |
---|

Recent Past

Abstracts

**Title:** Mini Course: Introduction to Positional Games

**Speaker:** Miloš Stojaković

**Locations and Times:**

Tue 18, 10.00-13.00, Room 5161.0222 (Bernoulliborg)

Wed 19, 13.00-16.00, Room 5161.0293 (Bernoulliborg)

Thu 20, 14.00-17.00, Room 5161.0151 (Bernoulliborg)

**Abstract:**
Positional Game Theory provides a solid mathematical footing
for a variety of two-player games of perfect information, usually
played on discrete objects (like graphs), with a number of
applications in other branches of mathematics and computer science.
The field is just a few decades old, and it has experienced a
considerable growth in recent years. Our goal is to introduce some
basic concepts and notions, followed by recent results and numerous
open problems.

The prerequisites include undergraduate knowledge of discrete
mathematics and probability, and the lectures could be of interest to
people with a wide range of backgrounds and different levels of
seniority.

**Title:** Community structure in Networks - limits of learning

**Speaker:** Fiona Skerman

**Abstract:**
Modularity is at the heart of the most popular algorithms for community detection. For a given network G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the network G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q*(G) ≤ 1.

1. "When is there Modularity from fluctuations in Random Graphs?" Guimera et al 2004 showed that the Erdös-Rényi random graph Gn,p with n vertices and edge-probability p can have surprisingly high modularity and that this should be taken into account when determining statistical significance of community structures in networks. Further, they predicted Gn,p to have modularity order (np)-1/3.

Our two key findings are that the modularity is 1 + o(1) with high probability (whp) for np up to 1 + o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)−1/2 whp, in accord with a competing prediction by Reichardt and Bornholdt in 2006 based on spin glass methods.

2. Sampling sufficiency for determining modularity. We analyse when community structure of the underlying graph can be determined from observations of the network which we model by random sampling of the graph.

Joint work with Colin McDiarmid and based on the paper 'Modularity of Erdös-Rényi random graphs' arxiv.org/abs/1808.02243.

**Title:** Interacting diffusions on sparse random graphs

**Speaker:** Guilherme Reis

**Abstract:**
We consider systems of diffusion processes whose interactions are described by a graph. For example, traditional mean-field interacting diffusions correspond to a complete interaction graph. In recent years some effort has been directed to understanding more general interactions. When the interaction graph is random, in the particular case of the Erdős–Rényi random graph, we show how the behavior of this particle system changes whether the mean degree of the Erdős–Rényi graph diverges to infinity or converges to a constant. In this talk we will focus on the case that the mean degree converges to a constant. In this case we prove a strong law of large numbers for the empirical measures. To achieve this we exploit the local weak convergence and a locality property of this system. Loosely speaking, the locality property states that information does not propagate too fast over the graph for this kind of particle system. This tool allow us to manage the dependencies of the system. Joint work with Roberto Imbuzeiro Oliveira.

**Title:** On projections of the supercritical contact process: uniform mixing and cutoff phenomenon

**Speaker:** Stein Andreas Bethuelsen

**Abstract:**
In this talk I will present the findings in https://arxiv.org/abs/1810.06840. This paper concerns the supercritical contact process on general graphs and the study of the asymptotic properties of its projections onto finite subsets. We will see that, under minimal assumptions on the graph structure, such projections have a surprisingly strong temporal loss-of-memory property as soon as the infection rate is large enough. Furthermore, I will discuss certain relations between these results and similar findings for the projection of the 2d Ising model onto a line, as studied in https://arxiv.org/abs/1802.02059 (joint work with Diana Conache (TUM)). When time permits, I will also discuss a particular motivation for these two papers stemming from random walks on (dynamic) random environments.

**Title:** Loop-erased partitioning: two-point correlations on mean-field models

**Speaker:** Luca Avena

**Abstract:**
We consider a certain random partitioning of the vertex set of an arbitrary graph that can be efficiently sampled using loop-erased random walks with killing. The related random blocks tend to cluster nodes visited by the random walk-with infinitesimal generator the graph Laplacian- on time scale 1/q, with q > 0 being a tuning parameter. We explore the emerging macroscopic structure by analyzing 2-point correlations. To this aim, we define an interaction potential between pair of vertices of a graph, as the probability that they do not belong to the same block of the random partition. This interaction potential can be seen as an affinity measure for “densely connected nodes” and capture well-separated communities in network models presenting non-homogenous landscapes. In this spirit, we compute the potential and its scaling limits on a complete graph and on a non-homogenous weighted version with community structures. For the latter we show a phase-transition for detectability as a function of the tuning parameter and the edge weights.

Joint work with ALEXANDRE GAUDILLIEĚRE, PAOLO MILANESI (Marselle) AND MATTEO QUATTROPANI (Rome)

**Title:** Local weak convergence for PageRank

**Speaker:** Nelly Litvak

**Abstract:**
PageRank is a well-known algorithm for measuring centrality in networks. It was originally proposed by Google for ranking pages in the World-Wide Web. One of the intriguing empirical properties of PageRank is the so-called `power-law hypothesis': in a scale-free network the PageRank scores follow a power law with the same exponent as the (in-)degrees. Up to date, this hypothesis has been confirmed empirically and in several specific random graphs models. In contrast, in this talk we do not focus on one random graph model but investigate the existence of an asymptotic PageRank distribution, when the graph size goes to infinity, using local weak convergence. The local weak convergence is one of recent notions of graph limits, originally developed for undirected graphs. We will extend this notion to directed graphs and use this to prove the existence of an asymptotic PageRank distribution. As a result, the limiting distribution of PageRank can be computed directly as a function of the limiting object. This may help to identify general network structures in which the power-law hypothesis holds. We apply our results to the directed configuration model and continuous-time branching processes trees, as well as preferential attachment models.

This is a joint work with Alessandro Garavaglia (TU/e) and Remco van der Hofstad (TU/e)

**Title:** On the location of zeros of the independence polynomial for bounded degree graphs

**Speaker:** Guus Regts

**Abstract:**
In this talk I will introduce the independence polynomial (a.k.a. the partition function of the hard-core model in statistical physics) and motivate the study of the location of its zeros by applications to statistical physics and theoretical computer science.

Along the way I will indicate how the theory of complex dynamical systems has been used to settle a conjecture of Alan Sokal on the location of the zeros of the independence polynomial for bounded degree graphs. I will end with some open problems.

**Title:** The discrete Gaussian free field on a compact manifold

**Speaker:** Alessandra Cipriani

**Abstract:**
In this talk we aim at defining the discrete Gaussian free field (DGFF) on a compact manifold. Since there is no canonical grid approximation of a manifold, we construct a suitable random graph that replaces the square lattice Z^d in Euclidean space, and prove that the scaling limit of the DGFF is given by the manifold continuum Gaussian free field. Joint work with Bart van Ginkel (TU Delft).

**Title:** Optimizing constrained and unconstrained network structures

**Speaker:** Clara Stegehuis

**Abstract:**
Subgraphs contain important information about network structures and their functions. We investigate the presence of subgraphs in inhomogeneous random graphs with infinite-variance degrees. We introduce an optimization problem which identifies the dominant structure of any given subgraph. The unique optimizer describes the degrees of the vertices that together span the most likely subgraph and allows us count and characterize all subgraphs.

We then show that this optimization problem easily extends to other network structures, such as clustering, which expresses the probability that two neighbors of a vertex are connected. The optimization problem is able to find the behavior of clustering in a wide class of random graph models.

**Title:** k-regular subgraphs near the k-core threshold of a random graph

**Speaker:** Dieter Mitsche

**Abstract:**
We prove that $G_{n,p}$ whp has a k-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least k; i.e. an non-empty k-core. In particular, this pins down the threshold for the appearance of a k-regular subgraph to a window of size $e^{-\Theta(k)}$.

Joint work with Mike Molloy and Pawel Pralat.

**Title:** Truncated long-range percolation on oriented graphs

**Speaker:** Bernardo N. B. de Lima

**Abstract:**
We consider different problems within the general theme of long-range percolation on oriented graphs. Our aim is to settle the so-called truncation question, described as follows. We are given probabilities that certain long-range oriented bonds are open; assuming that the sum of these probabilities is infinite, we ask if the probability of percolation is positive when we truncate the graph, disallowing bonds of range above a possibly large but finite threshold. We give some conditions in which the answer is affirmative. We also translate some of our results on oriented percolation to the context of a long-range contact process.

Joint work with A. Alves, A. van Enter, M. Hilário and D. Valesin

**Title:** A generator approach to stochastic monotonicity and propagation of order

**Speaker:** Moritz Schauer

**Abstract:**
We study stochastic monotonicity and propagation of order for Markov processes with respect to stochastic integral orders characterized by cones of functions satisfying Φ f ≥ 0 for some linear operator Φ.

We introduce a new functional analytic technique based on the generator A of a Markov process and its resolvent. We show that the existence of an operator B with positive resolvent such that Φ A - B Φ is a positive operator for a large enough class of functions implies stochastic monotonicity. This establishes a technique for proving stochastic monotonicity and propagation of order that can be applied in a wide range of settings including various orders for diffusion processes with or without boundary conditions and orders for discrete interacting particle systems.

Joint work with Richard Kraaij

**Title:** Solvable models from the ergodic point of view

**Speaker:** Evgeny Verbitskiy

**Abstract:** In this review talk, I will discuss a link between solvable models of statistical mechanics (dimers, spanning trees, sandpiles) and algebraic dynamical systems. Even though the question about the existence of such a link was raised almost two decades ago, this problem remained largely inaccessible. The development of the theory of symbolic covers of algebraic dynamical systems has only recently provided a suitable framework.

**Title:** Building your path to escape from home

**Speaker:** Rodrigo Ribeiro

**Abstract:** We consider a random walker in a dynamic random environment
given by a system of independent simple symmetric random walks.
We will describe some perturbative results that can be obtained via multi-scale analysis,
including regimes of high density, low density and large drift on particles.
Based on joint works with Oriane Blondel, Marcelo Hilário, Frank den Hollander,
Vladas Sidoravicius and Augusto Teixeira.

**Title:** Random walk on random walks

**Speaker:** Renato Santos

**Abstract:** In this talk we introduce one of the simplest conceivable model of a random walk that can modify its domain. The model works as follows: before every walker step, with probability p a new leaf is added to the vertex currently occupied by the walker. We discuss questions related to the walker such as the speed it moves away from its initial position and how its neighborhood may looks like asymptotically. This is a joint work with D. Figueiredo, G. Iacobellu, R. Olivera and B. Reed.

**Title:** Law of large numbers and LDP for the Random Walk in the Cooling random Environment

**Speaker:** Conrado Costa

**Abstract:** In this talk we discuss 2 main new results: the Strong Law of Large Numbers and a quenched Large deviation principle for the Random Walk in the Cooling random Environment introduced by Avena, den Hollander in 2016. For the proof of these two results, we present two auxiliary results. The first, an ergodic theorem for cooling random variables and the second, a concentration result for the cumulant generating function of the static Random Walk in the random environment.

**Title:** Monotonicity for multi-range percolation on oriented trees

**Speaker:** Daniel Valesin

**Abstract:** Percolation theory contains a variety of monotonicity-related conjectures which are easy and natural to state but challenging to prove. In this talk, we will survey a few of these problems. We will then specialize to the setting of Bernoulli percolation on multi-range oriented trees. The trees we consider are oriented regular trees where besides the usual short bonds, all bonds of a certain length are added. Independently, short bonds are open with probability p and long bonds are open with probability q. We study properties of the critical curve which delimits the set of pairs (p,q) for which there is percolation. We also show that this curve decreases with respect to the length of the long bonds. Joint work with Bernardo N. B. de Lima and Leonardo T. Rolla.