Characterization of Extremal Epidemic Networks with Diffusion Characters

Daniel Ashlock and Colin Lee.
Submitted to the CIBCB 2008

Abstract PDF eprint

Epidemic models often incorporate contact net- works along which the disease can be passed. The connectivity of the network can have a substantial impact on the course of the epidemic. In this study an evolutionary computation system is used to optimizes networks with a fixed distribution of contacts to yield either long-lasting epidemics or epidemics in which a maximal number of individuals are infected in a given time step. These networks represent extremal cases of network behavior. A novel network analysis tool called the diffusion character matrix, derived from the Leontief inverse of a modified adjacency matrix, is used to demonstrate that the networks located for the two optimizations are substantially different. The diffusion character matrix analysis allows us to place several metric-like dissimilarity measure on the space of graphs with a fixed number of nodes. The evolutionary algorithm used searches the space of networks with a specified degree sequence, with degrees representing the number of contacts for each member of the population. The representation used to evolve networks is a linear chromosome specifying a series of degree-preserving editing moves applied to an initial network that specifies the degree sequence of the searched networks. The evolutionary algorithm uses a non-standard type of restart called recentering in which the currently best network in the population replaces the initial network at intervals. The recentering operator moves the evolving population to successively higher fitness regions of the search space. In this study the algorithm is applied to networks with constant degrees from 3 to 7. The diffusion character matrix analysis also demonstrates that the volume of the search space occupied by networks maximizing the number of individuals that fall sick in one time step is much smaller than that occupied by networks that maximize epidemic length.