Topological theory of resilience and failure spreading in flow networks

Link failures in supply networks can have catastrophic consequences that can lead to a complete collapse of the network. Strategies to prevent failure spreading are thus heavily sought after. Here, we make use of a spanning tree formulation of link failures in linear flow networks to analyze topological structures that prevent failure spreading. In particular, we exploit a result obtained for resistor networks based on the matrix tree theorem to analyze failure spreading after link failures in power grids. Using a spanning tree formulation of link failures, we analyze three strategies based on the network topology that allow us to reduce the impact of single link failures. All our strategies either do not reduce the grid's ability to transport flow or do in fact improve it—in contrast to traditional containment strategies based on lowering network connectivity. Our results also explain why certain connectivity features completely suppress any failure spreading as reported in recent publications.

Figure 1

Different methods for mitigating failure spreading in linear flow networks. (a) The failure of a single link (red) with unit flow results in flow changes $\mathrm{\Delta }F$ (color scale) throughout the Scandinavian power grid. (b) Failure spreading to Finland may be reduced by strengthening a link that horizontally separates Sweden and Finland. (c) Adding nodes, thus increasing the length of the rerouting path, reduces failure spreading to Finland as well. (d) Adding two links to construct a network isolator results in a complete vanishing of flow changes in the other part of the grid. Grid topology was extracted from the open energy system model PyPSA-Eur [30].

Figure 2

Flow changes decay exponentially with cyclic paths in different networks. (a) and (d) Number of spanning trees (STs) $\tau (G/p)$ in an Erdős-Rényi (ER) random graph $G(200,300)$ with 300 edges and 200 vertices (a) and in the power flow test case “IEEE 118” [35] (d) that contain a randomly chosen cyclic path $p$ ($y$ axis) plotted against the length of the path $len\left(p\right)$ ($x$ axis). The number of STs decays exponentially with the length of the path, thus appearing linear on a logarithmic $y$ scale. (b) and (e) The rerouting distance scales exponentially with the LODF evaluated here for a single trigger for both grids. (c) and (f) The exponential scaling is preserved when averaging over all possible trigger links. Shading indicates 0.25 and 0.75 quantiles, a line represents the median. In Figs. 8 and 9 in the Appendix we demonstrate that the scaling robustly occurs for ER random graphs by analyzing 20 random realizations.

Figure 3

Spanning trees (STs) may be used to explain the shielding effect of certain connectivity structures between different parts of a network. (a) and (b) A square grid is divided into two parts by either weakening the links connecting two parts [(a), blue, $w_e=0.1]$ or strengthening the links perpendicularly separating the two parts [(b), blue, $w_e=10]$. (c) and (d) For both divisions, the failure of a single link with unit flow (red) significantly reduces failure spreading to the other part of the network. (e)–(h) Different STs (black) that contain specific paths of the form $(v_0=r,v_1,...,v_i=m,v_{i+1}=n,v_{i+2},...,v_k=s)$ used to calculate the flow changes on link $(m,n)$ for a failure of link $(r,s)$ by virtue of Eq. (7). (e) and (f) For the weakly connected network shown in (a) and (c), a monitoring link in the same part (e) may lead to STs that contain only one weak link (blue shading). Thus the contribution of this ST to the sum over all STs is much stronger than for a monitoring link in the other part, where STs have to contain at least two weak links [(f), blue shading]. (g) and (h) For the strongly connected network shown in (g) and (h), the STs with the highest contribution are the ones containing all edges with strong weights [(g), blue shading]. (h) If links $(m,n)$ and $(r,s)$ are in different parts, no ST may contain all edges with strong weights (blue shading), thus reducing failure spreading in this case.

Figure 4

Network isolators that lead to a complete vanishing of LODFs are created using certain symmetric paths in the network. (a) STs that contain a path starting at node $r$ and terminating at node $s$ and containing the edge $(m,n)$ (blue) or $(n,m)$ (red) have to cross the subgraph consisting of dotted, colored edges in the center. Since each path can contain each vertex and edge only once, each ST passing through the subgraph in one way (blue) has a counterpart passing through the subgraph in the other way (red). (b) Failure of a link (red) results in vanishing LODFs (color scale) in the part connected by a network isolator as predicted using the ST formulation of link failures.

Figure 5

Sign reversal of LODFs by symmetric subgraphs. (a) and (b) Modifying the subgraph connecting two graphs from the two parallel lines to the two crossing lines leads to a sign reversal of the LODFs in the connecting subgraphs (shades of gray). This is in line with the compensatory effect of the symmetric subgraphs used to create the network isolator in Fig. 4.

Figure 6

Failure spreading between Finland and the rest of Scandinavia is suppressed for all three strategies. We evaluate the ratio of LODFs, $\overline{R}\left(m\right):={\langle R(m,d)\rangle }_d$, averaged over distance $d$ [Eq. (14)] between the right part of the grid, i.e., Finland, and its left part, i.e., the remainder of Scandinavia (see Fig. 1). We average the ratio over all distances $d$ for a given trigger link $m$ and sort the values by magnitude for the initial Scandinavian power grid (dark blue circles). We then analyze the ratio for the three strategies outlined in Sec. 4b and shown in Fig. 1. We observe that all strategies consistently yield reduced failure spreading between the two parts. Strengthening a specific link [blue triangles; cf. Fig. 1] inhibits failure spreading more than increasing the length of the rerouting path [light blue squares; cf. Fig. 1], while adding a network isolator [light blue diamonds; cf. Fig. 1] completely suppresses failure spreading.

Figure 7

Systematic analysis of the overall impact of a given strategy for mitigating failure spreading. We compare the impact of each of the strategies shown in Fig. 1 on the overall grid resilience measured by the LODF ratio $\overline{\mathcal{R}}\left(m\right):={\langle \mathcal{R}(m,d)\rangle }_d$ averaged over distance $d$ [Eq. (15)], which expresses to what extent the impact of the failure of a given link $m$ on the network differs from its impact in the grid without the modification. We average the ratio over all distances to calculate a link-based measure of grid resilience. (a) We observe that strengthening a single link has an overall positive impact on grid resilience and reduces the LODF ratio up to tenfold (dark blue links), with only a few links showing an increase (red). (b) An increase in rerouting as shown in Fig. 1 improves resilience in most links as well; the effect is, however, less pronounced than in the previous case. (c) Adding a network isolator strongly improves resilience in Finland, while slightly weakening it in the rest of Scandinavia. Thus all three strategies consistently have a positive impact on link-based resilience in Finland.

Figure 8

Exponential decay of the number of spanning trees (STs) $\tau (G/p)$ in Erdős-Rényi (ER) random graphs, with length of randomly chosen cyclic path $len\left(p\right)$, occurs robustly. Each panel shows the number of STs in a different, random realization of an ER graph $G(200,300)$ with 300 edges and 200 vertices after collapsing a randomly chosen cyclic path. We analyze 200 randomly chosen cyclic paths for each ER graph (dots) and perform a least-squares fit of an exponential function on the semilog scale (dashed lines). The number of STs decays exponentially with the length of the path, thus appearing linear on a logarithmic $y$ scale.

Figure 9

Decay of averaged LODFs with rerouting distance to the trigger link is robust throughout 20 different realizations of Erdős-Rényi (ER) random graphs. Each panel shows the decay of LODFs for a different, random realization of an ER graph $G(200,300)$ with 300 edges and 200 vertices. We observe an approximately exponential scaling of LODFs with rerouting distance when averaging over all possible links located at a fixed rerouting distance to the trigger link. Shading indicates 0.25 and 0.75 quantiles; a line represents the median.