Network Reliability: The effect of local network structure on diffusive processes

Abstract

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 estimation by distributed simulation. We describe a collection of graphs derived from Erdős-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 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.

12 pages, 8 figures, 1 table

References in corpus (2)

• Dynamical and spectral properties of complex networks
• Robustness and Assortativity for Diffusion-like Processes in Scale-free Networks

Cited by in corpus (6)

• Degree correlations in directed scale-free networks
• Exact sampling of graphs with prescribed degree correlations
• Sensitive Dependence of Optimal Network Dynamics on Network Structure
• From Network Reliability to the Ising Model: A Parallel Scheme for Estimating the Joint Density of States
• Analyzing Network Reliability Using Structural Motifs
• Model selection for sequential designs in discrete finite systems using Bernstein kernels