Source-linked AI summary
Percolation in Multiplex Networks with Overlap
Davide Cellai, Eduardo López, Jie Zhou, James P. Gleeson, Ginestra Bianconi
TL;DR
Multiplexes are often fragile, yet link overlap across layers has largely been neglected despite being ubiquitous. This paper develops a general percolation framework incorporating overlap and shows that overlap can improve robustness while producing complex critical behavior.
Problem
Link overlap in multiplex networks has largely been neglected, despite its ubiquity and its relevance to the robustness of interdependent systems.
Method
The paper develops a general formalism for percolation with edge overlap and applies it to 2- and 3-layer Poisson graphs by calculating their phase diagrams.
Results
Edge overlap can enhance multiplex robustness, change a duplex transition from hybrid first order to second order, and produce high-order multicritical points in multilayer systems.
Takeaways & Limitations
Overlap is a key feature for characterizing robustness in real multiplexes and can make system reliability less predictable when overlapping edges do not involve all layers.
Abstract
from arXiv · showhide
From transportation networks to complex infrastructures, and to social and communication networks, a large variety of systems can be described in terms of multiplexes formed by a set of nodes interacting through different networks (layers). Multiplexes may display an increased fragility with respect to the single layers that constitute them. However, so far the overlap of the links in different layers has been mostly neglected, despite the fact that it is an ubiquitous phenomenon in most multiplexes. Here we show that the overlap among layers can improve the robustness of interdependent multiplex systems and change the critical behavior of the percolation phase transition in a complex way.
I. INTRODUCTION
Multiplexes model systems whose nodes interact through multiple network layers, but link overlap—common in empirical systems—has been largely neglected in robustness theory. The paper develops an overlap-aware percolation formalism and applies it to two- and three-layer Poisson graphs.
- Multiplexes represent systems in which the same nodes interact through different networks, including social, transportation, and brain-network layers.
- Interdependent multiplexes can be more fragile than their individual layers, with node failures triggering cascades and abrupt MCGC collapse.The MCGC is the extensive component mutually connected across every layer.
- Empirical multiplexes commonly contain overlapping links, such as friendships or transportation connections shared across communication or transport layers.
- The paper introduces a general theoretical framework for studying percolation under random damage when links overlap across layers.The authors position percolation as a first step toward more complex network models and dynamics.
- Applying the framework to 2- and 3-layer Poisson graphs, the paper calculates phase diagrams and finds that overlap can enhance robustness while producing high-order critical points.
II. MULTIPLEX WITH OVERLAP
The paper represents multiplex edge patterns with mutually exclusive multilinks and corresponding multiadjacency matrices, making overlap explicit across layers. It then characterizes local overlap through multidegrees and accommodates both fully overlapping and uncorrelated multilayer structures.
- A multiplex consists of the same labelled nodes represented across multiple network layers, each layer having its own adjacency matrix.
- A multilink is a binary vector specifying exactly which layers connect a node pair, so each pair has one multilink type.
- Multiadjacency matrices record whether each node pair is connected by each multilink type and satisfy constraints because only one multilink can describe a pair.
- For example, (i,j) has multilink (1,1,0), whereas (r,l) has multilink (1,1,1), explicitly distinguishing partial from full overlap.
- Multidegrees count multilinks of a given type incident to a node and provide higher-order measures of local overlap.
- The framework includes fully overlapping multiplexes, which recover continuous classical percolation, and uncorrelated layers as distinct limiting cases.
III. EMERGENCE OF THE MUTUALLY CONNECTED GIANT COMPONENT (MCGC)
The paper derives a message-passing framework for the mutually connected giant component under random node removal in locally tree-like multiplexes with overlap. It formulates the framework for multidegree ensembles and uses generating functions to obtain self-consistent probabilities for messages and MCGC membership.
- Without link overlap, the MCGC undergoes a hybrid first-order transition when random node removal reaches a critical point.
- A node belongs to the MCGC exactly when it receives supporting connections satisfying the required condition in every layer.
- On locally tree-like multiplexes, message passing determines MCGC membership from messages sent by neighboring nodes.
- The framework evaluates messages by excluding the incoming edge and combining independent neighbor contributions under the locally tree-like assumption.
- Multiplexes are generated from multidegree sequences by attaching typed stubs and randomly matching stubs of the same multilink type.
- The probabilities S_n and S describe reaching the MCGC through a multilink and the probability that a random node belongs to it, respectively.
- The resulting quantities are self-averaging in the large-network limit and generalize earlier equations to significant link overlap.
- For factorizable multidegree distributions, generating functions reduce the self-consistency equations for message and MCGC probabilities.
A. Two Poisson layers with Overlap
For two Poisson layers, increasing edge overlap improves multiplex robustness and changes percolation from hybrid first order to second order through a tricritical point. The phase diagram and simulations characterize these transitions and their finite-size behavior.
- Analytical and numerical comparison: Analytical solutions agree with simulations for continuous transitions, while discontinuous transitions near the tricritical point show finite-size effects and improved agreement for larger networks.Comparisons across network sizes indicate convergence toward the analytical solution as N increases.
- Phase behavior: The second-order transition line is obtained by requiring a nontrivial solution x⋆ > 0 of h(x⋆) = 0 to vanish continuously as p approaches the critical value.The analysis expands the equation near x⋆ = 0 and identifies second-order points where h′(0) = 0.
- Phase behavior: At c2 = 2c1 and c2p = 1, the system reaches the tricritical point where the transition behavior changes.The expansion requires higher-order terms because h′′(0) = 0 at this point.
- Phase behavior: For c2 < 2c1 and c2p < 1, the model exhibits hybrid first order transitions defined by h(x⋆) = h′(x⋆) = 0 with x⋆ > 0.The critical exponent is β = 1/2; when c2 = 0, the threshold recovers c1pc = 2.4554... for two Poisson networks without overlap.
- Phase behavior: Increasing overlap improves robustness and changes the transition from hybrid first order to second order through a tricritical point.The continuous transition is driven by percolation of the sub-network of double edges, while non-coincident paths matter beyond the tricritical point.
B. Three Poisson Layers with Overlap
For three-layer Poisson multiplexes, overlap produces multiple percolation regimes whose transition order and critical behavior depend on single, double, and triple edge fractions. The phase diagram includes continuous, discontinuous, tricritical, and multicritical transitions, with greater triple-edge overlap generally increasing resilience.
- Model: The three-layer model assigns mean degrees c1 to single edges, c2 to double edges, and c3 to triple edges, with one order parameter S.The parameters refer to edge multiplicities across the three layers, not exponents.
- Phase diagram: The phase diagram separates nonpercolating S = 0 from percolating S > 0 regions, with continuous transitions at c3p = 1 and discontinuous transitions for c3p < 1.The three-dimensional diagram is parameterized by c1, c2, and c3.
- Critical points: A tricritical line at c3p = 1 terminates at multicritical point Q, where it encounters the line of discontinuous transitions.The line is characterized by higher-order vanishing conditions on g(x), and its endpoint structure includes U and Q.
- Transition regimes: At small c2p, the MCGC collapse can be continuous or discontinuous depending on the relative abundance of single and triple edges.The continuous transition is driven by the subnetwork of triple edges, whereas discontinuous collapse occurs when the relevant balance favors the alternative regime.
- Transition regimes: In part of parameter space, increasing p crosses a continuous transition before a discontinuous transition, causing S to grow continuously and then jump to a larger value.The discontinuous transition separates a phase driven by non-coincident paths from a classical phase driven by coincident triple-edge paths.
- Critical behavior: The critical exponent is β = 1 at second-order points, β = 1/2 at tricritical points, and β = 1/3 at multicritical point Q.These values characterize S − Sc near the corresponding critical occupation probability.
- Robustness: Increasing the fraction of triple edges makes the multiplex more resilient, whereas increasing c2/c1 can make the transition discontinuous and potentially catastrophic.The authors therefore state that network design must account for all relevant layers.
V. CONCLUSIONS
The paper presents a general framework showing that link overlap changes percolation transitions and robustness in multiplex networks. In multilayer systems, overlap can generate complex critical behavior, including multicritical points and transitions between percolating phases of different strengths.
- A critical overlap value in duplexes can change a hybrid first-order transition into a second-order transition and improve system robustness.
- Multiplexes with more than two layers exhibit complex critical phenomena, including high-order multicritical points.
- First-order transitions can occur between percolating phases with different strengths.
- Overlap involving fewer than all layers can change a continuous transition into a discontinuous one, making reliability less predictable.
- The framework is intended to characterize robustness in real multiplexes where link overlap is common, including online games, social networks, and epidemiology.
Appendix A: Calculation of the critical points in the three layer Poisson multiplex
The appendix calculates critical points and exponents for a three-layer Poisson multiplex by expanding the function g(x) and imposing derivative conditions. These conditions distinguish continuous, tricritical, multicritical, and positive-x critical points.
- The three-layer Poisson multiplex uses c1 for single-layer edges, c2 for double-layer edges, and c3 for triple-layer edges.
- Second-order critical points satisfy g′(0) = 0 and g′′(0) > 0, provided no first-order transition has already occurred.
- The second-order critical points lie at c3p = 1 and have critical exponent β = 1.
- The multicritical point Q is obtained by setting g′(0) = g′′(0) = g′′′(0) = 0, while higher-order behavior uses g′′′′(0).
- Positive-x critical points C satisfy g(xc) = g′(xc) = g′′(xc) = 0 and are analyzed using the auxiliary function Φ.