Distributing Antidote Using PageRank Vectors

Abstract

We give an analysis of a variant of the contact process on finite graphs, allowing for nonuniform cure rates, modeling antidote distribution. We examine an inoculation scheme using PageRank vectors that quantify the correlations among vertices in the contact graph. We show that for a contact graph on _n_ nodes we can select a set _H_ of nodes to inoculate such that with probability at least 1 − 2ε, any infection from any starting infected set of _s_ nodes will die out in _c_ log _s_+_cˈ_ time, where _c_ and _cˈ_ depend only on the probabilistic error bound ε and the infection rate, and the size of _H_ depends only on _s_, ε, and the topology around the initially infected nodes, independent of the size of the whole graph.