Maintaining the Giant Component in Networks With Edge Weighted Augmentation Given Causal Failures

Abstract

Understanding the relationship between various nodes of a network is critical for building a robust and resilient network. Studying and understanding the causes of network failures is vital to prevent electric grid blackouts, mitigate supply chain failures, and keep transportation systems functional, among others. Failure of one or more nodes may cause other nodes in the network to fail as well, that is, failures are causal. In general, these failure relationships extend beyond the immediate neighborhood of failed nodes. When any of the causal failures are applied (the nodes of the causal failures are removed), the network could be disconnected. One can add edges to the original network (augmentation problem) in such a way that the network remains connected after applying each of the causal failures, or the largest connected component in the disconnected network is at least a given specified size $\alpha \times n$ ( $\alpha $ -giant component), where n is the number of nodes in the original network. By choosing this size, we guarantee that the network is active for a large population of entities represented by the nodes in the giant component. More formally, we consider the network augmentation problem when faced with causal failures as follows. Given a network $G=(V, E)$ , its complement $\bar {G}=(V, \bar {E})$ with a cost function $c: \bar {E} \rightarrow R^{+}$ and the causality set $\mathcal {C}$ , find a subset of $\bar {E}$ with a minimum total cost such that the network maintains at least one $\alpha $ -giant component when each causal failure in $\mathcal {C}$ is applied to the augmented graph. We prove the NP-hardness of this problem and present a mixed integer linear programming model to provide the exact solution to the problem. Furthermore, we design a heuristic algorithm by checking the connected components when applying each causality. Finally, experiments are conducted on synthetic Erdős-Rényi networks, and we demonstrate the efficacy and efficiency of the heuristic algorithm relative to the mixed-integer linear programming model.

Keywords

• Causal failure
• robustness
• connectivity augmentation
• NP-hardness
• heuristic algorithms