Random graphs and dynamics workshop: Report

The workshop 'Random Graphs and Dynamics' was held on 17 February 2021 via the RSS Teams platform. Organised by the Applied Probability Section, the meeting was attended by over 40 researchers from various disciplines, including statistics, probability and computer science.

Presentations were given by three experts of the field: Peter Mörters (University of Cologne), Laurent Massoulié (INRIA), and Shankar Bhamidi (University of North Carolina). Each presentation was also followed by a short discussion between the speaker and the participants.

The presentation of Peter Mörters discussed some fascinating phenomena in the evolving networks with power-law degrees. In particular he described in detail how exceptionally long survival of an epidemics on the network, called metastable behaviour of contact process, can arise when we tune the parameters for updating the networks.

Laurent Massoulie, on the other hand, looked at on the problem of partial alignment, a notoriously hard problem from theoretical computer science. Inspired by the local structure of the Erdos-Renyi graph, he presented an algorithm — Neighbourhood Tree Matching Algorithm — which returns in polynomial time a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches.

In his presentation, Shankar Bhamidi addressed two major problems for dynamic networks: seed detection and change point detection. Relying upon probabilistic analysis on the long range dependence in the network, he described an approach to the seed detection using fixation of hub vertices as well as non-parametric estimators for the change point detection.

Load more