title: Using the network reliability polynomial to characterize and design networks.
abstract: 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 callcriticality. 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.
authors.affiliation: Network Dynamics and Simulation Science Laboratory, Virginia Bioinformatics Institute ; Department of Population Health Sciences, Virginia-Maryland Regional College of Veterinary Medicine.
authors.forename: Stephen
authors.initials: S
authors.lastname: Eubank
authors.affiliation: Network Dynamics and Simulation Science Laboratory, Virginia Bioinformatics Institute.
authors.forename: Mina
authors.initials: M
authors.lastname: Youssef
authors.affiliation: Network Dynamics and Simulation Science Laboratory, Virginia Bioinformatics Institute ; Department of Physics Virginia Tech, Blacksburg, Virginia 24061.
authors.forename: Yasamin
authors.initials: Y
authors.lastname: Khorramzadeh
keywords: complex networks; graph theory; graphical models; network reliability; network theory; network topology