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

This paper reintroduces the network reliability polynomial, introduced by Moore and Shannon [Moore and Shannon, J. Franklin Inst. 262, 191 (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 of 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.

Figure 1

Network reliability $R\left(x\right)$ for assortative Erdős-Rényi GNM graphs with sizes $V$, $2V$, and $4V$. The inset shows the transition from $R\left(x\right)=0$ to $R\left(x\right)=1$.

Figure 2

Degree distributions for the Erdős-Rényi graphs, GNM (left panel) and the scale-free-like graphs, SFL (right panel). Note the logarithmic axes for the SFL graphs.

Figure 3

Accessible ranges of assortativity and number of triangles for GNM and SFL graphs.

Figure 4

$k_{\min }$ (bottom) and $k_{\max }$ (top) for disassortative, neutral, and assortative GNM (left panel) and SFL (right panel) graphs under an AR-$\alpha$ reliability rule with $\alpha =0.2$.

Figure 5

The average reliability $\langle R\left(x\right)\rangle$ (left panel) and the critical points (right panel) for disassortative, neutral, and assortative GNM graphs under an AR-$\alpha$ reliability rule with $\alpha$ $=$ 0.2.

Figure 6

The average reliability $\langle R\left(x\right)\rangle$ (left panel) and the critical points (right panel) for disassortative, neutral, and assortative SFL graphs under an AR-$\alpha$ reliability rule with $\alpha$ $=$ 0.2.

Figure 7

Peak value of the derivative of $R\left(x\right)$ for disassortative, neutral, and assortative GNM (left panel) and SFL (right panel) graphs under an AR-$\alpha$ reliability rule with $\alpha$ $=$ 0.2.

Figure 8

A degree distribution-preserving edge swap. The four vertices shown are connected by the edge stubs shown here to the rest of the graph, which is not shown. Left panel: Assortativity-changing edge swap. In this example, $d_i=4$, $d_j=3$, $d_k=2$, and $d_l=5$. Hence $d_i{d}_j+d_k{d}_l=22$ and $d_i{d}_k+d_j{d}_l=23$ so the graph at the bottom has a higher assortativity than the one at the top [30, 31]. If the graph at the top is connected, then the graph at the bottom will also be connected if there is a path from $i$ to $j$. In that case, this will be an acceptable edge swap for $A^{+}$, but not for $A^{-}$. Right panel: Assortativity-preserving and triangle-changing edge swap. $B$ and $D$ have no neighbors in common, nor do $C$ and $E$. In this example, $d_B=d_E=4$ and $d_C=d_D=2$. Hence, $d_B{d}_D+d_C{d}_E=40=d_B{d}_C+d_D{d}_E$ so the graph at the top has the same assortativity as the one at the bottom. If the graph at the top is connected, then the graph at the bottom will also be connected if there is a path from $B$ to $D$. In that case, the swap from top configuration to bottom configuration will be an acceptable one for $T^{+}$; the swap in the opposite direction will be acceptable for $T^{-}$, since the swap cannot disconnect the graph. This swap changes the number of triangles in the graph by at least one, and more if $B$ and $C$ have any common neighbors besides $A$.