Analyzing dynamically important differences between complex networks using reliability polynomial

Characterizing networks in a way that is directly relevant to diffusion phenomena on the network is important, but difficult. We argue that the Network Reliability Polynomial is a characterization that folds together static measures like degree, modularity and measures of centrality into precisely the combinations that are most relevant to the dynamics. Thus knowledge of reliability can be used to infer structure, in the sense of network tomography. Furthermore, reliability concepts provide a new perspective for reasoning more generally about the consequences of structural changes. We demonstrate how to compare networks using a novel family of measures of an edge's contribution to particular aspects of diffusion dynamics on a network. The measures are analogous to betweenness, but are more directly related to specific dynamical phenomena. We focus here on phenomena of interest in network epidemiology, but the methods can easily be generalized to other diffusive processes on a network.