Determining whether a class of random graphs is consistent with an observed contact network.

We demonstrate a general method to analyze the sensitivity of attack rate in a network model of infectious disease epidemiology to the structure of the network. We use Moore and Shannon's "network reliability" statistic to measure the epidemic potential of a network. A number of networks are generated using exponential random graph models based on the properties of the contact network structure of one of the Add Health surveys. The expected number of infections on the original Add Health network is significantly different from that on any of the models derived from it. Because individual-level transmissibility and network structure are not separately identifiable parameters given population-level attack rate data it is possible to re-calibrate the transmissibility to fix this difference. However, the temporal behavior of the outbreak remains significantly different. Hence any estimates of the effectiveness of time dependent interventions on one network are unlikely to generalize to the other. Moreover, we show that in one case even a small perturbation to the network spoils the re-calibration. Unfortunately, the set of sufficient statistics for specifying a contact network model is not yet known. Until it is, estimates of the outcome of a dynamical process on a particular network obtained from simulations on a different network are not reliable.

Analyzing network reliability using structural motifs.

This paper uses the reliability polynomial, introduced by Moore and Shannon in 1956, to analyze the effect of network structure on diffusive dynamics such as the spread of infectious disease. We exhibit a representation for the reliability polynomial in terms of what we call structural motifs that is well suited for reasoning about the effect of a network's structural properties on diffusion across the network. We illustrate by deriving several general results relating graph structure to dynamical phenomena.

Using the network reliability polynomial to characterize and design networks.

We consider methods for solving certain network characterization and design problems that arise in network epidemiology. We argue that the network reliability polynomial introduced by Moore and Shannon is a useful framework in which to reason about these problems. Specifically, we show how efficient estimation of the polynomial permits characterizing and distinguishing very large networks in ways that are are dynamically relevant. Furthermore, a generalization of flows and cuts to structures that determine the reliability suggests a new measure of edge or vertex centrality that we call criticality. We describe how criticality is related to the more common notion of betweenness and illustrate its application to targeting interventions to control outbreaks of infectious disease. Although our applications are to infectious disease outbreaks, the methods we develop are applicable to many other diffusive dynamical systems over complex networks.

Network reliability: the effect of local network structure on diffusive processes.

This paper reintroduces the network reliability polynomial, introduced by Moore and Shannon [Moore and Shannon, J. Franklin Inst. 262, 191 (1956)], for studying the effect of network structure on the spread of diseases. We exhibit a representation of the polynomial that is well suited for estimation by distributed simulation. We describe a collection of graphs derived from Erdos-Rényi and scale-free-like random graphs in which we have manipulated assortativity-by-degree and the number of triangles. We evaluate the network reliability for all of these graphs under a reliability rule that is related to the expected size of a connected component. Through these extensive simulations, we show that for positively or neutrally assortative graphs, swapping edges to increase the number of triangles does not increase the network reliability. Also, positively assortative graphs are more reliable than neutral or disassortative graphs with the same number of edges. Moreover, we show the combined effect of both assortativity-by-degree and the presence of triangles on the critical point and the size of the smallest subgraph that is reliable.