Network Reliability: A novel betweenness measure using structural motifs

This paper applies the concept of network reliability, introduced by Moore and Shannon in 1956, for studying the effect of network structure on the spread of diseases. 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 consequences. We conclude by exploring a novel centrality measure based on structural motifs.