The effect of network topology on the spread of epidemics

TLDR

Network phenomena such as worm and email virus propagation, faults, and information dissemination are commonly modeled as epidemic spreads on graphs. This study investigates what network topological features determine whether an epidemic is weak or potent. The authors identify topological properties that govern epidemic persistence and apply these findings to hypercube, complete, power‑law, star, and Erdős–Rényi network topologies. They demonstrate that when the cure‑to‑infection ratio exceeds a graph’s spectral radius, the mean epidemic lifetime grows logarithmically with the number of nodes, whereas if the ratio falls below a generalized isoperimetric constant, the mean lifetime decays exponentially with the network size.

Abstract

Many 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 larger than the spectral radius of the graph, then the mean epidemic lifetime is of order log n, where n is the number of nodes. Conversely, if this ratio is smaller than a generalization of the isoperimetric constant of the graph, then the mean epidemic lifetime is of order e/sup na/, for a positive constant a. 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 Erdos-Renyi graph as their epidemic spreading behaviors determine the spreading behavior of power law graphs.