Source-linked AI summary
Interdependent networks with correlated degrees of mutually dependent nodes
Sergey V. Buldyrev, Nathaniel Shere, Gabriel A. Cwilich
TL;DR
The paper analyzes failure transitions in interdependent networks with correlated dependencies through the mutual giant component. It finds that CCN are more robust than RCN, with transition order depending on the degree distribution.
Problem
The paper examines how correlated dependencies affect failure and robustness in interdependent networks.
Method
The analysis characterizes the mutual giant component and its phase transition using degree-distribution-based equations.
Results
CCN are always more robust than RCN with the same degree distribution, while finite-second-moment distributions produce first-order transitions at pc > 0.
Takeaways & Limitations
The robustness of CCN increases with the broadness of their degree distribution.
Abstract
from arXiv · showhide
We study a problem of failure of two interdependent networks in the case of correlated degrees of mutually dependent nodes. We assume that both networks (A and B) have the same number of nodes $N$ connected by the bidirectional dependency links establishing a one-to-one correspondence between the nodes of the two networks in a such a way that the mutually dependent nodes have the same number of connectivity links, i.e. their degrees coincide. This implies that both networks have the same degree distribution $P(k)$. We call such networks correspondently coupled networks (CCN). We assume that the nodes in each network are randomly connected. We define the mutually connected clusters and the mutual giant component as in earlier works on randomly coupled interdependent networks and assume that only the nodes which belong to the mutual giant component remain functional. We assume that initially a $1-p$ fraction of nodes are randomly removed due to an attack or failure and find analytically, for an arbitrary $P(k)$, the fraction of nodes $μ(p)$ which belong to the mutual giant component. We find that the system undergoes a percolation transition at certain fraction $p=p_c$ which is always smaller than the $p_c$ for randomly coupled networks with the same $P(k)$. We also find that the system undergoes a first order transition at $p_c>0$ if $P(k)$ has a finite second moment. For the case of scale free networks with $2<λ\leq 3$, the transition becomes a second order transition. Moreover, if $λ<3$ we find $p_c=0$ as in percolation of a single network. For $λ=3$ we find an exact analytical expression for $p_c>0$. Finally, we find that the robustness of CCN increases with the broadness of their degree distribution.
I. INTRODUCTION
The paper studies correspondently coupled networks, where mutually dependent nodes have identical degrees, and analytically characterizes their mutual giant component under random failure. It finds that degree correlations improve robustness and alter the transition behavior, especially for scale-free degree distributions.
- Model: Correspondently coupled networks (CCN) pair nodes one-to-one so mutually dependent nodes have identical degrees and both networks share P(k).The model assumes randomly connected networks with bidirectional dependency links.
- Problem and approach: The analysis seeks the fraction μ(p) in the mutual giant component after randomly removing a 1−p fraction of nodes.Only nodes in the mutual giant component remain functional.
- Main results: CCN undergo a percolation transition at a p_c always smaller than that of randomly coupled networks with the same degree distribution, except for random regular graphs.The paper contrasts CCN with randomly coupled networks (RCN).
- Main results: Finite-second-moment degree distributions produce a first-order transition at p_c>0, with the mutual giant component discontinuously vanishing below the threshold.The functional fraction changes from μ_c>0 at p=p_c to zero for p<p_c.
- Robustness: CCN robustness increases with the broadness of their degree distribution.The paper also reports that CCN are more robust than RCN against random failure.
II. GENERATING FUNCTIONS AND THE CASCADE PROCESS
The first cascade stage uses generating functions to determine the giant component after random node removal. It tracks the resulting degree distribution and component size analytically.
- A. First stage: The first stage models random removal of a 1−p fraction of nodes using generating functions and branching-process methods.The original degree distribution is transformed through a binomial expansion after decimation.
- A. First stage: The fraction of nodes outside the giant component is obtained from the generating function evaluated at the smallest nonnegative root f(p).The root satisfies a transcendental equation.
- A. First stage: The original degree distribution of surviving giant-component nodes is reconstructed from the decimated distribution using Bayes’ formula.A decimated node of degree k′ may have had any original degree k≥k′.
- A. First stage: The first-stage giant component A1 contains N1=Np(1−r1) nodes, where r1=G(t1).Here t1=f1p+1−p and f1=f(p).
B. Second stage
In the second cascade stage, surviving nodes from A1 are projected to B through dependency links, then B is re-percolated after removing links and nodes outside the projected set. This produces a smaller giant component B2 and enables further cascade iterations.
- B. Second stage: Only nodes belonging to A1 remain functional, so their dependent counterparts form the candidate set B1 in network B.The one-to-one dependency mapping D projects A1 onto B.
- B. Second stage: The second-stage giant component has size N2=p(1−r1)(1−r2)N, with r2=˜G1(f2,p1), and is smaller than A1.The cascade therefore causes further disintegration of network B.
- B. Second stage: Because corresponding nodes have equal degrees, A1 and B1 have the same degree distribution from B’s perspective.This equality permits the first-stage approach to be applied to B1.
- B. Second stage: Links from B1 to nodes outside B1 are removed before computing the second-stage giant component.The probability p1 that a link from B1 ends in B1 is used to construct the associated link-degree distribution.
- B. Second stage: The second-stage generating function is ˜G1(x,p1)=[G(xp1+1−p1)−G(t1(xp1+1−p1))]/(1−r1).It describes the link-degree distribution within B1 after excluding links leaving B1.
C. Third stage
The third cascade stage computes the surviving giant component in network A after failures propagated through network B. Because the selected nodes are drawn from A's connected giant component, an effective degree distribution and network size are required.
- The third stage computes giant component A3 after nodes in A1 lacking membership in B2 fail.
- A2 is not a random subset of network A; it is selected from A's connected giant component A1.
- The analysis therefore constructs an effective degree distribution and network size reproducing A2 through random selection from the original network.
- The selection of A2 from A1 has the same effect as randomly selecting a fraction p(1 −r1) of nodes.
- The third-stage problem is equivalent to the second stage after replacing t1, f1, r1 with t2, f2, r2, and advancing to t3, f3, r3.
D. Recursive relations
The cascade is described recursively: each stage determines the next stage's parameter, giant-component size, and internal degree distribution until the process reaches a fixed point.
- For stage i, the analysis derives a recursive relation connecting ti and ti+1.
- Knowing ti determines ti+1, the giant-component size at that stage, and the degree distribution of nodes inside it.
- The derivation repeats the steps used for obtaining t2 from t1, with fi+1 determined by an analogous transcendental equation.
- Eliminating fi+1 and si yields ti+1 as the smallest non-negative root of the resulting relation.
- The iteration starts from t1 = pf1 + 1 −p together with the equation equivalent to the initial transcendental condition.
III. THE MUTUAL GIANT COMPONENT AND THE PHASE TRANSITION
The mutual giant component is obtained from the cascade's fixed point, and its emergence defines the percolation transition. Finite degree-distribution second moments produce a discontinuous transition, while sufficiently broad distributions can change its order.
- The cascade stops when ti+1 = ti = t, and the mutual giant component fraction is µ = limi→∞Ni/N.
- The fixed-point variable t is the smallest non-negative root of Eq. (36), which relates G, H, p, and ⟨k⟩.
- For finite G′′(1), equivalent to a finite second moment, small p leaves only the trivial solution t = 1 and µ = 0.
- As p increases, a nontrivial solution µ > 0 emerges, while the critical point occurs where the right-hand side is tangent to the line at t = tc.
- Because tc < 1, the mutual percolation transition is first order, with µ jumping from zero to µc ≥ µc > 0 at pc.
- The critical threshold can be found by maximizing the left-hand side of Eq. (37) with respect to t; if its maximum is below 1, no mutual giant component exists for any p.
IV. SPECIAL CASES
Special cases illustrate the threshold behavior for ER and random regular networks and show when correspondently coupled and randomly coupled models coincide.
- For ER networks, H(t) = exp[⟨k⟩(t −1)], and the maximal value of Eq. (37)'s left-hand side increases monotonically with ⟨k⟩.
- ⟨k⟩ = 1.706526 is the ER threshold at which the maximal value reaches 1.
- Below ⟨k⟩ = 1.706526, correspondently coupled ER networks disintegrate even without an initial attack or failure.
- For random regular graphs, all nodes share degree k = ⟨k⟩, giving G(t) = t⟨k⟩.
- When all dependent-node degrees coincide, CCN and RCN models are equivalent; the corresponding equations therefore reduce to one another.
C. Scale free networks
For scale-free CCN, the transition is second order: when λ<3, the mutual giant component exists for any p>0, while λ=3 yields a finite positive threshold.
- λ<3: For λ<3, scale-free CCN are as robust as a single scale-free network, whose threshold is pc=0.
- λ=3: For λ=3, G′′(t) diverges logarithmically near t=1, but the left-hand side retains finite slope, giving pc>0 and a second-order transition.
- Analytical example: For the specified discrete distribution, the critical thresholds are pc=0.59328456 for kmin=1 and pc=0.32277924 for kmin=2.
D. Effect of the broadness of the degree distribution
At fixed average degree, broader degree distributions make correspondently coupled networks more robust, although variance alone does not fully determine the threshold.
- Comparative thresholds: For λ=3 scale-free networks with ⟨k⟩=3, pc is estimated as 0.35, below the thresholds of narrower ER and RR distributions.
- Comparative thresholds: For λ<3 scale-free networks, pc=0 for any average degree, matching the robustness trend of single-network percolation.
- Comparative thresholds: With equal average degree, the variance ordering is SF > uniform > ER > RR, and the thresholds satisfy pc(SF) < pc(uniform) < pc(ER) < pc(RR).
- Robustness trend: At fixed average degree, CCN become more robust as the degree distribution broadens, opposite to the behavior of RCN.
- Caveat: Variance alone is insufficient: distributions with identical variances and average degrees can have different pc values.
V. GENERAL IMPLICATIONS ON THE NETWORK ROBUSTNESS
The paper proves that degree-correlated mutual dependencies improve robustness relative to random coupling, while finite-second-moment networks still undergo cascade-driven first-order collapse.
- Comparison with RCN: Except for random regular networks, CCN have a smaller critical threshold than RCN with the same degree distribution.
- Analytical comparison: The critical fraction pc is found by maximizing the equation governing the mutual giant component's nonvanishing condition.
- Comparison with RCN: For the same p, CCN have a mutual giant component at least as large as that of RCN.
- Transition behavior: CCN remain vulnerable to cascade failures and undergo first-order disintegration when G′′(1)<∞.
VI. SUMMARY
The study derives analytical equations for failure cascades and mutual giant components in correspondently coupled networks, then characterizes their robustness across degree distributions and coupling schemes.
- Contributions: The analysis derives recursive equations for cascades, mutual giant-component size, and the critical surviving fraction in CCN.The threshold is obtained by finding the maximum of Eq. (37).
- Transition behavior: Finite second moments lead to cascade-driven first-order disintegration, with the mutual giant component dropping abruptly from a positive fraction to zero at pc>0.
- Robustness comparison: CCN are more robust than RCN with the same degree distribution.
- Scale-free networks: For λ<3, scale-free CCN undergo a second-order transition, retain a mutual giant component for any p>0, and become infinitely small as p→0.
- Degree-distribution broadness: At constant average degree, CCN robustness increases with degree-distribution broadness, opposite to RCN behavior.
- Interpretation: The authors conjecture that any positively correlated dependency degrees are more robust than random coupling, attributing this to suppression of hub dependence on low-degree nodes.