Abstract
We consider a cyber-physical system consisting of two interacting networks, i.e., a cyber-network overlaying a physical-network. It is envisioned that these systems are more vulnerable to attacks since node failures in one network may result in (due to the interdependence) failures in the other network, causing a cascade of failures that would potentially lead to the collapse of the entire infrastructure. The robustness of interdependent systems against this sort of catastrophic failure hinges heavily on the allocation of the (interconnecting) links that connect nodes in one network to nodes in the other network. In this paper, we characterize the optimum inter-link allocation strategy against random attacks in the case where the topology of each individual network is unknown. In particular, we analyze the "regular" allocation strategy that allots exactly the same number of bi-directional inter-network links to all nodes in the system. We show, both analytically and experimentally, that this strategy yields better performance (from a network resilience perspective) compared to all possible strategies, including strategies using random allocation, unidirectional inter-links, etc.
Introduction: The Fragility of Interdependence
Modern society relies on "networks of networks." Power grids depend on communication networks for control, while communication networks require electricity from the grid. This mutual dependence, or interdependence, creates a feedback loop where a failure in one system can trigger a "cascading failure" in the other. Without careful design, a localized disturbance can escalate into a system-wide collapse.
The central challenge is determining how to distribute a limited number of "inter-links" between these networks to maximize robustness. This paper addresses a common real-world scenario: designing these connections when the internal "map" (topology) of each network is unknown.
Methodology: Evaluating Allocation Strategies
The researchers compared three primary strategies for inter-link allocation:
- Regular Bi-directional: Every node is assigned exactly $k$ bi-directional links.
- Random Bi-directional: Links are bi-directional, but the number of links per node follows a random distribution.
- Random Unidirectional: Links are one-way, and the number per node is random.
To model the failure process, the authors used generating functions from random graph theory. This allowed them to track the "functioning giant component"—the largest connected part of the network capable of operation—as failures propagate through successive stages.
Key Insights: The Power of Regularity
The study's primary finding is that regular allocation is mathematically optimal when internal topology is unknown. Several factors contribute to this:
- Eliminating Weak Links: By ensuring every node has exactly $k$ connections, the system avoids "weak links"—nodes that would have failed early in a random distribution due to having zero or very few connections.
- Bi-directionality as a Safety Net: Bi-directional links create a mutual support bond. If Node A1 supports B1 and B1 supports A1, the pair is significantly more resilient than if they were connected via separate, unidirectional paths.
- Deterministic Superiority: Even when the average number of links is identical, a deterministic "regular" strategy outperforms a random one. In the context of cascading failures, variance in connectivity is a primary driver of instability.
Results and Performance
Numerical simulations on networks with $N = 5,000$ nodes confirmed the analytical proofs. For two Erdős-Rényi networks with an average internal degree of 4:
- Regular Allocation ($k=2$): The system remained resilient until 57% of nodes were lost ($p_c = 0.43$).
- Random Allocation (Mean $k=2$): The system collapsed after losing only 18% of its nodes ($p_c = 0.82$).
This dramatic improvement in resilience is achieved purely through the distribution of links, requiring no additional resources.
Conclusion
When designing critical infrastructure, "equality" in connectivity is a powerful tool for robustness. While knowing the specific topology of a network allows for targeted hardening of hubs, the "regular" allocation strategy provides a robust, provably optimal baseline for protecting interdependent systems against catastrophic cascades when such information is unavailable.
Summary updated