Department of Mathematics Colloquium

University of Idaho

Spring 2013

Thursday,  February 15, 3:30-4:20 pm, room TLC 045

Refreshments in Brink 305 at 3:00 pm

Spreading processes on graphs and PageRank


Paul Horn

Department of Mathematics

Harvard University


Disease breaks out on a graph! As medicine is expensive, it is unrealistic to send medicine to all vertices in preparation to fight the outbreak, but we still desire to ensure that the disease dies out quickly on the medicated vertices and escapes the medicated set with low probability. Under a variant of the contact process, a classical model of the spread of disease, we show how to accomplish such a goal on an arbitrary host graph. In particular,
we show that the probability that the disease escapes a given medicated set can be bounded in terms of the PageRank of the complement. We additionally look at a broad generalization of this, where multiple interacting processes spread on a graph, where a new vectorized version of PageRank becomes critical to our understanding of the process.