PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Allocation of Interconnecting Links in Cyber-Physical Systems: Interdependence, Cascading Failures and Robustness

Osman Yagan, Dajun Qian, Junshan Zhang, Douglas Cochran

arXiv:1201.2698v2physics.data-ancs.SIphysics.soc-ph

TL;DR

Interdependent cyber-physical systems can experience recursive cascading failures, making inter-link allocation central to robustness. The paper analytically and experimentally studies regular bi-directional allocation without detailed topology information and finds it optimal against random attacks. Simulations illustrate a substantial robustness gap between regular and random allocation.

  • Problem

    Cascading failures in interdependent networks and their cross-network effects remain insufficiently understood, motivating robust allocation methods for cyber-physical systems.

  • Method

    The paper analyzes a regular strategy that gives every node the same number of bi-directional inter-network edges, using analytical characterization and computer simulations.

  • Results

    Regular bi-directional allocation is optimal against random attacks when detailed individual-network topology is unavailable, outperforming random allocation and unidirectional links.

  • Takeaways & Limitations

    When network topologies are unknown, allocating exactly the same number of bi-directional inter-edges to all nodes is the recommended strategy within the paper’s scope.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Interdependent cyber-physical networks can amplify node failures through recursive cross-network dependencies, motivating allocation strategies that improve robustness when network topologies are unavailable. The paper studies regular bi-directional inter-link allocation and establishes its optimality against random attacks.

  • I. INTRODUCTION: Interdependent networks can suffer cascading failures because failures in one network cause failures among dependent nodes in the other.The cascade may continue recursively and produce catastrophic system-wide impact.
  • I. INTRODUCTION: Existing work largely studied single networks or one-to-one interdependence, leaving broader cascading dynamics and cross-network effects insufficiently understood.The one-to-one model gives each node exactly one bi-directional inter-edge to a unique node in the other network.
  • II. SYSTEM MODEL: The proposed regular strategy gives every node exactly k bi-directional inter-edges, creating uniform support and dependency across the two networks.The model uses an N × N interdependency matrix to represent these links.
  • I. INTRODUCTION: For a fixed expected inter-degree, bi-directional links outperform unidirectional links, while deterministic equal allocation outperforms random inter-link allocation.These comparisons establish the regular strategy’s robustness advantage over the alternatives considered.
  • I. INTRODUCTION: Analytical results, numerical examples, and simulations are used to characterize and validate the optimal allocation strategy.The paper claims the strategy is optimal when individual network topologies are unknown.
  • II. SYSTEM MODEL: The analysis evaluates steady-state functioning giant components and the critical threshold pc under uniformly random failures initiated in network A.A node functions only if it has support from the other network and belongs to its own network’s giant component.

III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES

The paper models cascading failures as alternating fragmentation and support loss across two networks. Generating-function analysis tracks functioning giant components and the evolving distribution of inter-edges under regular allocation.

  • III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES: Generating functions are used to quantify the remaining giant components and critical threshold pc under random node failures.The objective is to characterize steady-state functioning portions of networks A and B.
  • III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES: The cascade alternates between networks as fragmentation removes support links and causes further node failures.The illustrative six-node example reaches steady state after failures propagate through both networks.
  • III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES: A random attack removes a fraction 1−p of network A, after which only nodes in A’s functioning giant component can operate.The resulting support losses initiate the next stage in network B.
  • III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES: Regular allocation complicates the analysis because the inter-edge distribution over functioning nodes must be tracked at every stage.Nodes may retain different numbers of inter-edges after neighboring failures, even though allocation initially gives each node k links.
  • III. ANALYSIS OF CASCADING FAILURES UNDER REGULAR ALLOCATION OF INTER-EDGES: In network B, nodes that lose all inter-edges fail, while surviving nodes are filtered through B’s functioning giant component.The retained nodes are grouped according to how many inter-edges remain.

C. Stage 3 : Further A-Nodes Failures due to B-Node Failures

Stage 3 accounts for further A-node failures caused by fragmentation of network B. The analysis computes support loss and maps the resulting A fragmentation to an equivalent attack for estimating A3.

  • C. Stage 3 : Further A-Nodes Failures due to B-Node Failures: When B fragments to its functioning giant component B2, each inter-edge from B2 to A1 may be removed.The removal probability is approximated using the ratio of functioning B nodes to retained B nodes.
  • C. Stage 3 : Further A-Nodes Failures due to B-Node Failures: An A1 node loses support and stops functioning when all of its inter-edges are removed, with probability (1−PB(p′B2))^k.This produces the surviving subnetwork Ā3 before its giant component is determined.
  • C. Stage 3 : Further A-Nodes Failures due to B-Node Failures: The combined effects of Stage 1 and Stage 3 failures are treated, for determining |A3|, as an equivalent initial random attack on network A.The equivalent attack removes the same portion of nodes from the initially retained network.
  • C. Stage 3 : Further A-Nodes Failures due to B-Node Failures: The resulting functioning giant component A3 is then obtained using the equivalent occupation fraction p′.This transformation avoids directly recomputing the coupled fragmentation effect at that stage.

D. Stage 4 : Further Fragmentation of Network B

Stage 4 further fragments network B after cascading failures triggered by earlier node removals and inter-edge disconnections. The functioning giant component B4 is characterized by an equivalent initial random attack on B.

  • D. Stage 4 : Further Fragmentation of Network B: Stage 3 failures disconnect inter-edges supporting B2 according to the fraction of nodes lost during network A’s fragmentation.A node in B2 with j inter-edges fails when all its supporting inter-edges are disconnected.
  • D. Stage 4 : Further Fragmentation of Network B: Failures in Stages 2 and 4 have an equivalent effect on B4 to removing an appropriate fraction of nodes through an initial random attack.The analysis maps cascading failures to an equivalent node-removal fraction for computing the functioning giant component.
  • D. Stage 4 : Further Fragmentation of Network B: The size of the functioning giant component B4 is expressed using the equivalent remaining fraction after the cascade.The supplied derivation identifies B4 through the effective attack fraction generated by the preceding stages.

E. Cascading Dynamics of Node Failures

The cascading process can be extended recursively across successive functioning giant components until both networks reach an equilibrium point where further fragmentation stops. For arbitrary intra-network topologies, the steady state is determined through network-specific giant-component functions.

  • E. Cascading Dynamics of Node Failures: The recursive analysis yields the sizes of all functioning giant components A1, A3, …, A2m+1 and B2, B4, …, B2m.The expressions follow the same alternating cascade pattern across the two networks.
  • E. Cascading Dynamics of Node Failures: The recursion stops at an equilibrium point where neither network fragments further.The equilibrium is represented by limiting fractions of the surviving giant components.
  • E. Cascading Dynamics of Node Failures: For arbitrary intra-network structures, the steady-state equations can be solved using the corresponding functions PA and PB for given p and k.The limiting giant-component fractions are computed from PA∞ = xPA(x) and PB∞ = yPB(y).

IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY

This section establishes that regular allocation is optimal among bi-directional inter-link strategies when intra-network topology is unavailable. The comparison uses a random inter-degree distribution and shows that equal inter-degree allocation maximizes robustness at fixed mean inter-degree.

  • IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY: Regular allocation gives every node in networks A and B exactly k bi-directional inter-edges.This system is called System 1 and serves as the benchmark for comparing allocation strategies.
  • IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY: Jensen’s inequality and convexity show that the strongest robustness occurs when the inter-degree distribution degenerates to one common value.Thus regular allocation is optimal among all possible bi-directional inter-link allocation strategies.
  • IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY: System 2 assigns each node a random number of bi-directional inter-edges drawn from a distribution F with probabilities αj.Nodes are partitioned into subgraphs of sizes αjN, and every node in the jth subgraph receives j inter-edges.
  • IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY: The random-allocation cascade is analyzed by iteratively treating inter-edge disconnections and node failures as equivalent removals in the opposite network.This produces recursive expressions for the giant-component fractions at each stage.
  • IV. OPTIMALITY OF REGULAR ALLOCATION STRATEGY: For a fixed mean inter-degree, System 1 has at least as large steady-state functional giant components as System 2.The comparison is made through recursive relations for the two systems’ functioning fractions.

B. Regular Allocation versus Random Allocation

The regular-allocation system is compared with random allocation under matched mean inter-degree and identical intra-network structure. The proof shows that regular allocation has stronger robustness and a no-larger critical threshold against random attacks.

  • B. Regular Allocation versus Random Allocation: The induction compares the recursive functioning fractions of regular and random allocation at every cascade stage.Monotonicity of PA and PB, convexity, and Jensen’s inequality provide the comparison conditions.
  • B. Regular Allocation versus Random Allocation: PA1∞(p; k) ≥ PA2∞(p; α) and PB1∞(p; k) ≥ PB2∞(p; α).The regular system’s steady-state functional giant components are no smaller in either network.
  • B. Regular Allocation versus Random Allocation: pc1(k) ≤ pc2(α), so regular allocation has a critical threshold no greater than random allocation under the matching condition.A contradiction argument establishes the threshold inequality from the steady-state component comparison.
  • B. Regular Allocation versus Random Allocation: Regular bi-directional allocation is more robust than any random bi-directional allocation strategy, and bi-directional links outperform unidirectional links.The section states both comparisons as robustness conclusions under the paper’s model.

C. Bi-directional Inter-Edges versus Unidirectional Inter-Edges

The analysis compares randomly allocated bi-directional inter-edges with randomly allocated unidirectional inter-edges and finds the former consistently more robust against random node failures. Consequently, regular allocation of bi-directional inter-edges is identified as strongest among the considered strategies.

  • System 3 setup: System 3 models random allocation of unidirectional inter-edges after an initial failure of fraction 1−p in network A.Its steady-state giant-component fractions and critical threshold pc3(α) are defined through recursive relations.
  • Comparison: Theorem 4.2 establishes that System 2 is always more robust than System 3 against random node failures.The comparison uses recursive relations for the two systems and shows the relevant robustness inequalities.
  • Comparison: The comparison applies under an arbitrary distribution α of inter-edges, rather than only a particular allocation distribution.The proof proceeds by induction over the cascade stages and establishes the required inequalities for all stages.
  • Conclusion: Regular allocation of bi-directional inter-edges therefore yields the strongest robustness among all possible strategies against random attacks.This conclusion combines the paper’s regular-allocation result with the demonstrated superiority of bi-directional over unidirectional inter-edges.

V. NUMERICAL RESULTS: THE ERD ˝OS-R´ENYI NETWORKS CASE

The numerical section specializes the analysis to two Erdős-Rényi networks, derives their giant-component functions, and uses theory plus simulations to evaluate steady-state robustness.

  • ER network model: Both networks are modeled as Erdős-Rényi networks with mean intra-degrees a and b.For this model, the functions PA(x) and PB(y) determining giant-component sizes can be obtained explicitly.
  • Analytical calculation: The giant-component solutions are obtained from the network-specific functions and the defining equations for fA and fB.The section introduces the unique solutions fA and fB used in the numerical analysis.

A. Numerical Results for System 1

For System 1, the ER-network equations are reduced to a graphical solution whose critical threshold is the smallest p admitting a non-trivial solution. Simulations then corroborate the analytical critical values.

  • Analytical formulation: System 1’s steady-state giant-component fractions are obtained by substituting the ER expressions into the governing equations.The derivation proceeds through equations (36)–(40).
  • Solution structure: The trivial solution fA = fB = 1 corresponds to zero functional giant-component fractions in both networks.Non-trivial solutions are the relevant cases for sufficiently large p.
  • Critical threshold: The critical threshold pc is the minimum p yielding a non-trivial solution; below it, only the trivial solution remains and both networks completely fragment.For a = b = 3 and k = 2, Figure 3 illustrates the transition as p varies.
  • Critical threshold: At pc, the two solution curves are tangent, allowing fAc, fBc, and pc to be computed numerically from the tangential system.The tangency condition is added to the equations defining the solution curves.
  • Simulation validation: Simulations with N = 5000 estimate pinf and corroborate the analytically obtained pc values across selected a, b, and k settings.The simulations examine the probability that a functional giant component exists at steady state.

B. Numerical Results for System 2

For System 2, the ER analysis uses a Poisson inter-degree distribution and identifies pc through tangency of the resulting curves. Simulations validate the analytical predictions.

  • Steady state: The steady-state giant-component fractions are computed from the recursive process’s limiting relations.The limits are expressed through the network functions PA and PB.
  • System 2 model: System 2 assumes that each node’s inter-degree follows a Poisson distribution with mean k.This assumption supplies the inter-degree expression used in the subsequent equations.
  • Critical threshold: The critical threshold pc corresponds to the tangential point of the System 2 curves and is obtained by solving them graphically.The same tangency criterion used for System 1 is applied to the System 2 equations.
  • Simulation validation: Simulations with N = 5000 estimate pinf and validate the analytical pc curves for different mean intra-degrees and average inter-degree k.The simulations test the probability of a functional giant component at steady state.

C. A Comparison of System Robustness

Across analytical and numerical comparisons, regular allocation of equal bi-directional inter-edges consistently provides the strongest robustness against random attacks. It outperforms random allocation and unidirectional alternatives under matched mean inter-degree, while equal support avoids unsupported nodes.

  • Comparison setup: Regular bi-directional allocation is analytically and numerically compared with random and unidirectional strategies at matched mean inter-degree k.The comparison uses coupled Erdős-Rényi networks and critical threshold pc as the robustness measure.
  • Regular allocation: As k increases, regular allocation raises robustness and drives the critical fraction pc toward the single-network value 1.Figure 4 reports this trend for System 1 across different intra-network mean degrees.
  • Regular versus unidirectional allocation: For a = b = 4, System 1 achieves pc = 0.414 with k = 2, compared with pc = 0.43 for unidirectional System 3 with k = 4.The regular strategy therefore reaches a lower threshold with half the mean inter-degree in this example.
  • Overall comparison: Across all Figure 6 comparisons, System 1 has the lowest pc and highest robustness, System 3 the highest pc, and System 2 lies between them.The ordering supports both regular bi-directional allocation and bi-directional links over the compared alternatives.
  • Regular versus random allocation: For a = b = 3 and k = 2, System 1 has pc = 0.56 versus pc = 0.68 for random System 2.These thresholds correspond to resilience against random failure of up to 44% and 32% of nodes, respectively.
  • Interpretation: Equal allocation treats nodes uniformly when intra-topology information is unavailable and guarantees every node inter-edge support that random strategies may omit.Random allocation can leave a non-negligible fraction of nodes without inter-edges, making them automatically non-functional.
Loading 1201.2698v2…