From the spread of epidemics to dissemination of information, there are a wide range of natural phenomena that have inspired a variety of dynamical models on random graphs. Roughly speaking, the underlying random graph takes into account the complex nature of connectivity (either physically or socially), while the dynamical aspect of the model intends to emulate the evolution of the natural phenomenon under investigation. Besides having potential real-world applications, many of these models turn out to be challenging problems themselves, attracting attention from researchers from different communities (mathematics, physics, computer science, etc.)
In this half-day workshop, presentations will be given by experts on some of the latest developments in the field, investigating various aspects of these models, including problems on statistical inference, asymptotic behaviours, etc. We very much hope the workshop will also be an opportunity for discussion and collaboration for researchers from different communities who are interested in the field.
The event will feature talks from the following speakers. Each talk will be around 45 minutes, followed by a short discussion.
14:00 - 15:00
Peter Mörters (University of Cologne)
The contact process on evolving networks: From fast to slow dynamics
Chatterjee and Durrett (2009) showed that the contact process on scale-free networks exhibits metastable behaviour. This is in contrast to the corresponding mean-field model where for small infection rates metastable behaviour is only observed for power-law exponents 2 < τ < 3. In this talk we investigate the contact process on a network evolving according to an independent stationary dynamics. Varying the speed of the network evolution allows us to interpolate between the two scenarios and unlock a rich picture involving phase-transitions and crossover in the survival strategy of the contact process. The talk is based on ongoing joint work with Emmanuel Jacob (ENS Lyon) and Amitai Linker (Cologne).
15:00 - 16:00:
Laurent Massoulié (INRIA)
Partial alignment of sparse random graphs
Graph alignment is a generic algorithmic problem with many applications. In this work we consider alignment of sparse random graphs generated from the correlated Erdös-Rényi distribution. We introduce the Neighborhood Tree Matching Algorithm which provably returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds in a challenging regime of graphs with average degree in O(1) and correlation parameter bounded away from 1. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent. This is based on joint work with Luca Ganassali, see
https://arxiv.org/abs/2002.01258 .
16:00 - 17:00:
Shankar Bhamidi (University of North Carolina)
Long range dependence in evolving networks
The goal of this talk is to describe probabilistic approaches to two major problems for dynamic networks, both of which are intricately connected to long range dependence in the evolution of such models:
1. Detecting the initial seed which resulted in the current state of the network: Imagine observing a static time slice of the network after some large time $n$ started with an initial seed. Suppose all one gets to see is the current topology of the network (without any label or age information). Developing probably efficient algorithms for estimating the initial seed has inspired intense activity over the last few years in the probability community. We will describe recent developments in addressing such questions including robustness results such as the fixation of so called hub vertices as time evolves.
2. Change point detection: Consider models of growing networks which evolve via new vertices attaching to the pre-existing network according to one attachment function $f$ till the system grows to size $τ(n) < n$, when new vertices switch their behavior to a different function g till the system reaches size n. The goal is to estimate the change point given the observation of the networks over time with no knowledge of the functions driving the dynamics. We will describe non-parametric estimators for such problems.
Free to RSS Fellows
Free to non-Fellows before 30 January. After then a £10 fee will be charged.
Join the Society as a Fellow.
Sign up (for free) as an e-Student.