Behavioral regimes in the evolution of extremal epidemic graphs

Models of epidemic spread often incorporate contact networks along which the epidemic can spread. The character of the network can have a substantial impact on the course of the epidemic. In this study networks are optimized to yield long-lasting epidemics. These networks represent an upper bound on one type of network behavior. The evolutionary algorithm used searches the space of networks with a specified degree sequence, with degrees representing the number of sexual partners of each member of the population. The representation used is a linear chromosome specifying a series of editing moves applied to an initial network. The initial network specifies the degree sequence of the searched networks implicitly and the editing moves preserve the degree sequence. The evolutionary algorithm uses a non-standard type of restart in which the currently best network in the population replaces the initial network. This restart operator is called a recentering operator. The recentering operator moves the evolving population to successively higher fitness portions of the network space. In this study the algorithm is applied to networks with average degree from 2.5 to 7. In low-degree networks, short epidemics result from failure of the disease to spread through the relatively sparse links of the network. In high-degree networks, short epidemics result from the rapid infection of the entire population. The evolutionary algorithm is able to optimize both high and low degree networks to significantly increase the epidemic duration.