WorksMathematics
Capacity-Aware Redistribution Control for Mitigation of Cascading Failures in Networks
Abstract
This paper studies the control of irreversible cascading failures in networks with finite node capacities. Each node carries a nonnegative divisible quantity, referred to as load, and fails irreversibly when its load exceeds its capacity. The network dynamics are represented by topology-dependent row-stochastic matrices. When nodes fail, these matrices must be updated. However, directly deleting rows and columns corresponding to failed nodes can reduce the total load in the network. We therefore introduce a topology update that preserves unit row sums and quantifies any unserved load explicitly. We derive the resulting load-balance relation and a necessary and sufficient condition for lossless redistribution after simultaneous failures. Based on these results, we formulate a two-stage optimization problem: the first stage minimizes unserved load, and the second stage minimizes the highest capacity utilization among the surviving nodes. Simulations on grid and Barabasi-Albert networks show that, unlike the standard equal and residual-capacity redistribution approaches, the proposed method prevents secondary failures in all tested cases, with a tradeoff against served load on scale-free networks.
Introduction
Many networked systems, such as power, transportation, communication, and service networks, move a conserved quantity, hereafter referred to as load, among nodes with finite capacities such as substations, stations, or routers. When the load at a node exceeds its capacity, the node fails permanently, and its load is either transferred to surviving nodes or remains unserved. Redistribution may overload further nodes and trigger a cascade of failures [1, 2, 3]. Each failure also changes the network topology and thereby alters subsequent load transfers.
Capacity-based models [1], [2] describe how overload and changes in network flows can lead to propagating failures. Decentralized redistribution using neighboring information is proposed in [4], and optimal reassignment of failed-link loads in multilayer networks is studied in [5]. Related cascade models and mitigation strategies have been studied in the complex-networks literature [6, 7, 8]. For local redistribution, equal sharing can be used. It requires no optimization, but ignores the residual capacities of surviving nodes. It also does not coordinate transfers from simultaneously failing nodes that share a receiver, i.e., a surviving neighbor.
In power networks, the method in [9] computes load-shedding schedules over successive cascades using linearized power-flow equations. For a similar application, homogeneous load reduction, optimized shedding, and a tree heuristic approach are compared in [10]. For networks with external inflows, [11] investigates distributed routing under irreversible link failures and reductions in link capacities. For continuous-time flow networks, throughput and overload properties under monotone distributed routing are derived in [12]. Generally, existing cascade models typically change load only at failures and treat each failed node separately. Moreover, the optimization-based and robust approaches in [9, 10, 11, 12] rely on power-flow models or on flow networks with external inflows, and are thus not directly applicable when a finite node load is reassigned at failures. It therefore remains unclear how load transfers between failures should adapt to node removal, and under which conditions the loads of simultaneously failing nodes can be reassigned without overloading shared receivers.
In this work, we consider a finite divisible load held at the nodes, with no continuing external inflow. Nominal transfers follow a topology-dependent row-stochastic matrix, whereas loads of failed nodes are reassigned among surviving neighbors. When nodes fail, directly deleting the corresponding rows and columns can reduce the total load before redistribution. We propose an alternative to this strategy. In this context, our contributions are as follows. First, we show that our alternative topology update preserves row stochasticity after single or simultaneous failures and derive the corresponding total-load balance. Second, when the nominal surviving-node loads have enough capacity, we give a necessary and sufficient condition for lossless redistribution after simultaneous failures and determine the minimum load that must remain unserved. Third, we formulate a two-stage linear program that first minimizes unserved load and then minimizes the highest surviving-node capacity utilization. We give a necessary and sufficient condition under which no further failures occur. Fourth, in simulations with grid and scale-free networks, we compare our approach with standard heuristics, i.e., equal and residual-capacity redistribution, after two initial failures with a common surviving neighbor occur, and redistribution requires accounting for shared receiver capacities.
Network Model and Failure Dynamics
Consider an undirected weighted graph with nodes and edges with nonnegative weights. An edge allows load transfer between nodes and . Load is a nonnegative divisible quantity assigned to the nodes and can be divided among neighbors. The fixed capacity is the maximum load that node can carry. The load and capacity vectors are denoted by and , respectively. Let be the set of nodes active before the detection of failures at time , with . The newly failed and previously failed set of nodes respectively belong to
The active graph contains the active nodes and all edges of between them. Failures are irreversible, so and and . All nodes in are detected from and handled simultaneously, since a sequential order would change the outcome when they share surviving neighbors.
Let with entries be the load-transfer matrix before failure detection at step . For an active node , is the fraction of its load sent to neighbor , and is the fraction retained at . Each row sums to one because these fractions account for all of that node’s load. Thus, is row stochastic. In summary, specifies the available connections and specifies the transfer fractions along them. At a failure-free step, the nominal load dynamics are
Let denote the vector of all ones. Since ,
so nominal transfers preserve total load. In order to construct the matrix and to assign transfer weights along the edges of a given network , let with entries be its weighted adjacency matrix, the degree matrix with diagonal entries , , and . For , the initial load-transfer matrix is
This diffusion-type update is used in consensus dynamics [13]. The bound on ensures nonnegative entries , as well as the row-stochasticity, i.e., every row sums to one. When , we have .
Topology update at failure
Let be the surviving nodes. Their graph is . The matrix retains dimension associated with the initial node set . For , the entries read
For every , the entries read
By (5a) and (6), also for , . The intermediate load vector is computed as
This vector gives the load distribution after the matrix update and before the newly failed-node loads are reassigned. By (5b), the transfer weight previously assigned from a surviving node to a newly failed node is retained by that survivor as self-weight, which is consistent with the weight handling of consensus iterations over switching topologies [13]. In contrast, naive row–column deletion without this reassignment can lead to unnecessary loss of load under the nominal dynamics. For a three-node complete graph with , failure of node 2 would give
The surviving rows of sum to , so nominal transfers loose . In , diagonal compensation preserves unit row sums and therefore also total load before redistribution.
Failed-load redistribution and state update
We now define how the load of each newly failed node is redistributed. We assume that this load remains available for a one-time reassignment using the node’s connections immediately before removal. Only surviving neighbors can receive it and these incident connections are excluded from subsequent nominal transfers. For , define the active receiving-neighbor set as
Let be the load transferred from failed node to , and let be its shed or unserved load. All newly failed nodes satisfy the failed-load balance
Thus, every part of newly failed-node load is either assigned to an admissible receiver or marked explicitly as unserved. At each time step, the state is updated in the following order. First, is derived from with (1a). The load-transfer matrix is then updated to , and the intermediate load vector is computed with (7). Then a redistribution scheme determines and . For each , let denote the set of newly failed nodes that can transfer load to . Then the state update is
(12) dispatches the load at each surviving node, whereas (11b) sets all failed-node states to zero. Then the update and is performed. This update order is used throughout the analyses and simulations.
Remark 1: The update (11a)–(11b) can be equivalently written as , where accounts for failed-load removals and redistribution. Its entries are
At a failure-free step, implies and , so the full update reduces to (2).
Load Balance and Lossless Redistribution
In this section, we first show that the proposed matrix update preserves row stochasticity and derive the resulting total-load balance. We then characterize when the loads of simultaneously failed nodes can be fully redistributed without exceeding the capacities of the surviving nodes.
We start by showing that (5b) preserves the stochastic structure required by (3).
Proposition 1: If is nonnegative and row stochastic, then the update (5a)–(6) produces a nonnegative, row-stochastic . If is also symmetric, then is symmetric and doubly stochastic.
Proof: Nonnegativity follows because the update only retains nonnegative entries, sets entries to zero or one, and adds removed nonnegative weights to diagonal. For entries , summing the updated rows gives
since entries associated with previously failed nodes are already zero outside their diagonals. For , the updated row is an identity row and therefore also sums to one. If is symmetric, all surviving off-diagonal pairs remain unchanged and both entries incident to a failed node are set to zero. Hence remains symmetric. Symmetry and unit row sums then imply unit column sums.
Thus, the updated matrix preserves total load under the nominal dynamics, whether one or several nodes fail at the same time. The next proposition gives the resulting total-load balance.
Proposition 2: In the state update (11a)–(11b), suppose that redistribution flows and unserved loads satisfy (10). Then,
Proof: By Proposition 1, . So, by (7),
The isolated column of each newly failed node gives
Previously failed nodes have zero load by the irreversible-failure rule, and their isolated identity form also gives . Since , , and partition , the intermediate load on surviving nodes is
By (11b), we have that
This completes the proof.
If for every , then (14) gives lossless redistribution. Otherwise, total load decreases by , which is precisely the amount that could not be redistributed.
We next characterize whether all newly failed loads can be transferred without immediately overloading a survivor. Define the residual capacity after the transfers by
where . For , let
denote the set of active receivers adjacent to at least one node in .
Theorem 1: Let be the set of nodes that fail simultaneously at time , and assume that for every
. A redistribution with nonnegative flows only to , satisfying (10) with and for every , exists if and only if
Moreover, the minimum unavoidable unserved load is
Proof: If , both claims hold with . Otherwise, let . The idea is to represent the redistribution as a flow from the failed nodes to the receivers and to apply the max-flow/min-cut theorem [14].
First, we construct an auxiliary directed network as illustrated in Figure 1. To distinguish it from , we refer to its elements as vertices and arcs. Connect the source to each with capacity , vertex to each with capacity , and each receiver to the sink with capacity . Since , the failed-to-receiver arcs never restrict a transfer.

Figure 1. Auxiliary flow network for the connections in Example 1. Edge labels indicate the corresponding capacities.
Then, we relate flows in this network to redistributions. A feasible flow is nonnegative, respects arc capacities, and conserves flow at every vertex except the source and sink. Its value is the total flow leaving the source. Let the flow on arc be . Conservation at makes the source-to- flow equal to . Defining as the unused capacity of this arc, i.e., minus this flow, gives the failed-load balance (10). Conservation at makes the -to-sink flow equal to . Since , we have , so by (11a) the capacity of this arc is respected if and only if . Thus, feasible flows correspond to admissible redistributions within the receiver capacities. A flow of value saturates every source arc and is equivalent to lossless redistribution.
Finally, we determine the maximum flow value. A source–sink cut partitions the vertices with the source and sink on opposite sides. Its capacity is the sum of capacities of the arcs, directed from the source side to the sink side crossing it. The max-flow/min-cut theorem equates the maximum flow value and the minimum cut capacity. The cut with only the source on its side has capacity , and any cut crossing a failed-to-receiver arc has capacity at least . Consider a cut crossing no such arc. Let contain the failed vertices on the source side. Every receiver in must then also lie on that side. For fixed , placing only these receivers on the source side minimizes the cut capacity. The crossing arcs run from the source to failed vertices in and from receivers in to the sink, giving
Hence, the maximum flow value is , which equals exactly when (20) holds. By (22), the minimum unserved load is therefore
The following example shows why comparing total failed load with total residual capacity is insufficient when the admissible transfers are restricted by the network topology.
Example 1: Consider two simultaneously failed nodes and , each carrying units, and two active receivers and with residual capacities and . Let be connected only to , while is connected to both receivers. The aggregate residual capacity is sufficient when . However, applying (20) to gives the tighter condition . Moreover, equal redistribution sends from to and from to , so it violates that receiver’s capacity unless . Hence, aggregate residual capacity does not capture the topology-induced bottleneck.
Remark 2 (Single-node case): Under the assumptions of Theorem 1, for , lossless redistribution within receiver capacities exists if and only if .
Optimization-Based Redistribution Control
This section presents a two-stage linear programming approach for redistributing newly failed-node loads. The first stage minimizes unserved load, while the second stage minimizes the maximum capacity utilization among surviving nodes. As opposed to equal redistribution, we consider residual capacities and coordinate failed nodes sharing a receiver by actively selecting the redistribution flows. Let collect for and , and let collect for .
Stage 1: Minimum shedding
The first stage finds the minimum unserved load consistent with the surviving-node capacities.
Problem 1 (Minimum-shedding redistribution): When , let us compute as follows:
subject to
Constraint (23c) enforces capacity constraints, whereas (23d) permits load to leave only through . Under the nominal survivor-feasibility assumption of Theorem 1, Problem 1 is always feasible for and . If for any surviving node before redistribution, Problem 1 is infeasible because the nonnegative redistribution flows cannot reduce that node’s existing load. No capacity guarantee is made in this case. Note, that problem 1 leads to if lossless redistribution is feasible, and if a minimum load that must remain unserved exists.
Stage 2: Utilization balancing
Stage 2 minimizes maximum capacity utilization while allowing a total unserved load of at most , where is a small tolerance that accounts for the numerical precision of the solver. This maximizes the smallest unused capacity fraction .
Problem 2 (Utilization-balanced redistribution): Given from Problem 1, solve
subject to
Since , bounds the largest normalized surviving-node load after redistribution. Problem 2 is feasible because any optimizer of Problem 1, together with , satisfies all its constraints. Let denote the optimal value of Problem 2. Hence, , and every surviving node remains within its capacity. The Stage 2 solution is therefore also feasible for Stage 1. Stage 2 provides
Thus, balancing receiver utilization increases the unserved load by at most the desired numerical tolerance. When , Problem 1 is solved first, and Problem 2 is then solved using . Both problems concern only the current redistribution.
For subsequent nominal updates, let be the surviving-node block, and let and denote the capacity and load vectors only containing the values of .
Proposition 3 (Failure-free invariance): Suppose , is row stochastic, and . With fixed and no further external input, the nominal updates preserve for every initial state within these bounds if and only if
If the condition holds and Problem 1 is feasible, applying the Stage 2 solution gives no additional failures at any .
Proof. Nonnegativity of gives
so the condition is sufficient by induction. Necessity follows by taking the feasible state , which requires . Since , both vectors have the same sum. Since no entry on the left can be larger, none can be smaller either, so equality holds componentwise. Finally, the bound resulting from Problem 2 places the state after redistribution within these invariant bounds.
Uniform capacities with a doubly stochastic , as in Section V, satisfy this condition, whereas for unequal capacities a redistribution within all capacities at step can still lead to later overloads. Under this condition, the surviving nodes also satisfy , so Problem 1 is always feasible.
Remark 3 (Directed networks): Propositions 1 and 2, Theorem 1, and Problems 1 and 2 do not rely on symmetry. They also hold for a directed graph in which an edge only allows load transfer from to , if denotes the set of surviving out-neighbors of node and is constructed with the out-degree Laplacian and . In this case, however, is in general not doubly stochastic. Hence, the condition of Proposition 3 may fail even for uniform capacities, and a redistribution within all capacities at step can still lead to later overloads.
Numerical evaluation
This section compares equal redistribution, residual-capacity redistribution, and controlled redistribution on grid and scale-free networks. The evaluation focuses on secondary failures and unserved load.
Simulation setup and metrics
We consider the following networks: grid and scale-free networks with , , baseline load , and as in (5) with fixed . In each scenario, we consider two nodes, with a common surviving neighbor. Both of them receive an additional load causing them to fail simultaneously. Their common surviving neighboring node ensures that the two failed nodes compete for at least one receiver. On the grid, we consider all 322 such node pairs, which gives 1610 scenarios per redistribution method over all values of . For each of 30 Barabasi–Albert graphs [15] with attachment parameter 2, we sample 20 such pairs uniformly without replacement, which gives 3000 scenarios per method.
We compare equal redistribution, residual-capacity proportional redistribution, and the controlled redistribution of § 4. The residual-capacity method distributes each failed-node load among its active receivers in proportion to the residual capacities defined in (18). If all corresponding residual capacities are zero, it uses equal redistribution. The optimization problems associated with controlled redistribution are solved with scipy.optimize.linprog using HiGHS. Let be the set of initially disturbed nodes, and let contain all nodes that fail during the cascade. The secondary-failure fraction is . The unserved-load fraction is defined as the total unserved load accumulated over the cascade divided by the initial total load. For the uniform-capacity simulations, Proposition 3 ensures that, once a step produces no new failure, subsequent nominal updates cannot cause another one. All runs pass the state, flow, stochasticity, and balance checks, and no solver fails or iteration limit is reached.
Simulation results and discussion
For the grid network, Figure 2(a)–(Figure 2b) shows the results. Controlled redistribution produces no secondary failures over the tested range. At the largest tested disturbance, , it also leaves less load unserved on average than either of the equal redistribution or the residual capacity redistribution. Equal redistribution passes on all failed-node load whenever a surviving neighbor remains, even if that neighbor lacks sufficient capacity. The resulting overload can cause further failures and if a newly failed node has no surviving neighbor, its load remains unserved. Residual-capacity redistribution uses the available spare capacity, but treats each failed node separately. When several failed nodes share a receiver, the sum of their transfers may exceed its residual capacity. Controlled redistribution instead selects all transfers together and respects each receiver’s capacity.

Figure 2. Comparison of the three redistribution methods after two simultaneous initial failures with a common surviving neighbor. Curves show mean secondary-failure and unserved-load fractions for the grid in (a)–(b) and scale-free networks in (c)–(d).
For the scale-free networks, Figure 2(c)–(Figure 2d) shows a trade-off. Controlled redistribution again produces no secondary failures. However, at the largest tested disturbance, , it leaves more load unserved on average than either heuristic. Thus, avoiding further failures does not necessarily preserve more served load. The two optimization problems enforce receiver capacities at the current step, but do not minimize total unserved load over the complete simulation horizon, since a redistribution that is optimal at the current step can increase unserved load later.
Conclusion
We proposed a topology update approach for irreversible node failures that preserves row stochasticity and makes unserved load explicit. We also derived a condition for lossless redistribution after simultaneous failures and formulated a two-stage controller to minimize unserved load and balance receiver utilization. For two initial failures with shared receivers, the controller avoided secondary failures in all tested cases. At the largest disturbance, it left less load unserved than both heuristics on the grid network, but more on the scale-free networks. The benefit in served load therefore depends on the network and disturbance, rather than mitigation of failures alone. Future work will consider multi-step and robust formulations that account for future cascade stages.
References
- [1]A. E. Motter and Y.-C. Lai, “Cascade-based attacks on complex networks,” Phys. Rev. E, vol. 66, no. 6, p. 065102, 2002.pubmed.ncbi.nlm.nih.gov/12513335
- [2]P. Crucitti, V. Latora, and M. Marchiori, “Model for cascading failures in complex networks,” Phys. Rev. E, vol. 69, no. 4, p. 045104, 2004.pubmed.ncbi.nlm.nih.gov/15169056
- [3]I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. Newman, “Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization,” Chaos, vol. 17, no. 2, p. 026103, 2007.pubmed.ncbi.nlm.nih.gov/17614690
- [4]S. Al-Takrouni and A. V. Savkin, “A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks,” Physica A, vol. 392, no. 23, pp. 6135–6145, 2013.
- [5]R. Kumar, S. Kumari, and M. Bala, “Minimizing the effect of cascade failure in multilayer networks with optimal redistribution of link loads,” J. Complex Netw., vol. 9, no. 6, p. cnab043, 2021.
- [6]L. D. Valdez, L. Shekhtman, C. E. La Rocca, X. Zhang, S. V. Buldyrev, P. A. Trunfio, L. A. Braunstein, and S. Havlin, “Cascading failures in complex networks,” J. Complex Netw., vol. 8, no. 2, p. cnaa013, 2020.DOI
- [7]S. V. Buldyrev, R. Parshani, G. Paul, H. E. Stanley, and S. Havlin, “Catastrophic cascade of failures in interdependent networks,” Nature, vol. 464, no. 7291, pp. 1025–1028, 2010.arxiv.org/abs/1012.0206
- [8]A. E. Motter, “Cascade control and defense in complex networks,” Phys. Rev. Lett., vol. 93, no. 9, p. 098701, 2004.pubmed.ncbi.nlm.nih.gov/15447153
- [9]D. Bienstock, “Optimal control of cascading power grid failures,” in Proc. IEEE CDC-ECC, Orlando, FL, USA, 2011, pp. 2166–2173.DOI
- [10]S. Pahwa, C. Scoglio, S. Das, and N. Schulz, “Load-shedding strategies for preventing cascading failures in power grid,” Electr. Power Compon. Syst., vol. 41, no. 9, pp. 879–895, 2013.DOI
- [11]K. Savla, G. Como, and M. A. Dahleh, “Robust network routing under cascading failures,” IEEE Trans. Netw. Sci. Eng., vol. 1, no. 1, pp. 53–66, 2014.
- [12]G. Como, E. Lovisari, and K. Savla, “Throughput optimality and overload behavior of dynamical flow networks under monotone distributed routing,” IEEE Trans. Control Netw. Syst., vol. 2, no. 1, pp. 57–67, 2015.
- [13]R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proc. IEEE, vol. 95, no. 1, pp. 215–233, 2007.
- [14]L. R. Ford, Jr. and D. R. Fulkerson, “Maximal flow through a network,” Can. J. Math., vol. 8, pp. 399–404, 1956.
- [15]A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.