Seminar Details
2017-05-05 (14:00) : On the influence of network structure on non-Markovian spreading in deterministic and random graphs
At Euler building (room A.207)
Organized by Mathematical Engineering
Speaker :
Medvedev, Alexey
Abstract :
One model of real-life spreading processes is the SI model (also called First Passage Percolation) on random graphs. Social interactions often follow bursty patterns, which are usually modelled with 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. Along with that we perform a numerical study of the influence of graph properties on characteristic time of spreading using the mobile phone call dataset.