See by year See by month Jump to month

Pete Gábor (Rényi Intézet): Speeding up non-Markovian First Passage Percolation on critical random graphs by adding a single edge

Download as iCal file
Wednesday, 3. May 2017, 14:00 - 16:00
Abstract. One model of real-life spreading processes is First Passage Percolation (also called SI model) on random graphs. Social interactions often follow bursty patterns, which are usually modelled by non-Markovian heavy-tailed edge weights. On the other hand, random graphs are often locally tree-like, and spreading on trees is very slow, because of bottleneck edges with huge weights. We show the surprising phenomenon that adding a single random edge to a tree typically accelerates the process severely. We examine this acceleration effect on some natural models of random trees: critical Galton-Watson trees conditioned to be large in some way, uniform random trees using Loop Erased Random Walks and Pólya urn ideas, and will also discuss near-critical Erdős-Rényi graphs. Joint work with Alexey Medvedev, my former PhD student at CEU.
Location : Szeged, Aradi vértanúk tere 1., Riesz terem.


JEvents v3.1.8 Stable   Copyright © 2006-2013