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 {em structural motifs} that is well suited for reasoning about the effect of a networks structural properties on diffusion across the network. We illustrate by deriving several general results relating graph structure to dynamical phenomena.
This paper re-introduces the network reliability polynomial - introduced by Moore and Shannon in 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 est
imation by distributed simulation. We describe a collection of graphs derived from ErdH{o}s-Renyi 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 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.
