The Effect of Network Topology on the Spread of Epidemics

AMany network phenomena are well modeled as spreads of epidemics through a network. Prominent examples include the spread of worms and email viruses, and, more generally, faults. Many types of information dissemination can also be modeled as spreads of epidemics. In this paper we address the question of what makes an epidemic either weak or potent. More precisely, we identify topological properties of the graph that determine the persistence of epidemics. In particular, we show that if the ratio of cure to infection rates is smaller than the spectral radius of the graph, then the mean epidemic lifetime is of order, where is the number of nodes. Conversely, if this ratio is bigger than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order for a positive constant. We apply these results to several network topologies including the hypercube, which is a representative connectivity graph for a distributed hash table, the complete graph, which is an important connectivity graph for BGP, and the power law graph, of which the AS-level Internet graph is a prime example. We also study the star topology and the Erd˝os-Rényi graph as their epidemic spreading behaviors determine the spreading behavior of power law graphs.