Optimization Policies for Polya Contagion Networks

Abstract

This thesis investigates optimization policies for resource distribution in network epidemics, using a model that derives from the classical Polya process. The basic mechanics of this model, called the network Polya process, are based on a modified urn sampling scheme that accounts for both temporal and spatial contagion between neighbouring nodes in a network. We present various infection metrics and use them to develop two optimization problems, one which takes place upon initialization and one which occurs continually as the network Polya process develops. We frame these problems as both one-sided and two-sided resource allocation problems with fixed budgets, and analyze a suite of potential policies. Due to the complexity of these problems, we introduce effective proxy measures for the average infection rate in each case. We also prove that the two-sided infection-curing game on the so-called expected network exposure admits a Nash equilibrium. In both the curing and initialization scenarios we introduce heuristic policies that primarily function on the basis of limiting the number of targeted nodes within a particular network setup. Simulations are run for large-scale networks to compare performance of our heuristics to provably convergent gradient descent algorithms run on the simplified proxy measures.