Weak percolation on multiplex networks

Bootstrap percolation is a simple but nontrivial model. It has applications in many areas of science and has been explored on random networks for several decades. In single-layer (simplex) networks, it has been recently observed that bootstrap percolation, which is defined as an incremental process, can be seen as the opposite of pruning percolation, where nodes are removed according to a connectivity rule. Here we propose models of both bootstrap and pruning percolation for multiplex networks. We collectively refer to these two models with the concept of “weak” percolation, to distinguish them from the somewhat classical concept of ordinary (“strong”) percolation. While the two models coincide in simplex networks, we show that they decouple when considering multiplexes, giving rise to a wealth of critical phenomena. Our bootstrap model constitutes the simplest example of a contagion process on a multiplex network and has potential applications in critical infrastructure recovery and information security. Moreover, we show that our pruning percolation model may provide a way to diagnose missing layers in a multiplex network. Finally, our analytical approach allows us to calculate critical behavior and characterize critical clusters.

Figure 1

Diagrammatic representation of the probabilities $Z_n$ and $X_n$ in the case of two types of edges, 1 and 2.

Figure 2

Diagrams describing the second term on the right-hand side of Eq. (5) in the case of a node with multidegree $(q_1,q_2)=(2,2)$: $A_1=[1-{(1-Z_2)}^{q_2}]$ and $B_1={(1-X_1)}^{q_1-1}[{(1-X_2)}^{q_2}-{(1-Z_2)}^{q_2}]$. $A_1$ calculates the probability that, after having followed a type-1 edge, we get to a node from which at least one edge of type 2 leads to an unpruned cluster (finite or infinite). We can display this as a sum of three terms representing all the relevant possibilities in the case of $q_2=2$. $B_1$ is composed of two factors. The first factor represents the probability that no edge of type 1 leads to an infinite unpruned cluster ($\infty =0$). The second factor calculates the probability that all the edges of type 2 either lead to finite unpruned clusters ($\square =1\cap \infty =0$) or no clusters at all ($\square =0$). This is the meaning of the first line of $B_1$. The second line shows that $B_1$ can be written in a more compact way as a difference between the probability that none of the outgoing edges of type 2 lead to an infinite cluster and the probability that all the outgoing edges of type 2 do not lead to an unpruned cluster (even finite). This second line explains pictorially the way we write $B_1$ in Eq. (5).

Figure 3

Example of clusters in a multiplex with two types of edges. Black nodes are invulnerable or seed vertices; white nodes are vulnerable vertices. In WPP, all the nodes are unprunable (remain active), because each white node is connected to another node by each edge type. In WBP, only the nodes inside the green dot-dashed lines become active, while the remaining two nodes have only one active neighbor, by one edge type only, so they cannot become active.

Figure 4

Diagrams describing the second term on the right-hand side of Eq. (8) in the case of a node with multidegree $(q_1,q_2)=(2,2)$: $A_1=[1-{(1-Z_1)}^{q_1-1}][1-{(1-Z_2)}^{q_2}]$ and $B_1=[{(1-X_1)}^{q_1-1}-{(1-Z_1)}^{q_1-1}][{(1-X_2)}^{q_2}-{(1-Z_2)}^{q_2}]$. $A_1$ calculates the probability that, following an edge of type 1, we get to a node from which at least one edge of type 2 leads to an active cluster (finite or infinite). We can display this as a sum of three terms representing all the relevant possibilities in the case of $q_2=2$. $B_1$ is composed of two factors, one for each type of edge. In the first line, we show that each factor calculates the probability that all the edges of type 1 or 2 either lead to finite active clusters ($\square =1\cap \infty =0$) or no clusters at all ($\square =0$). This can be written in a more compact way (second line) as a difference between the probability that none of the outgoing edges of type 2 lead to an infinite cluster and the probability that all the outgoing edges of type 2 do not lead to an active cluster (even finite). This second line explains pictorially the way we write $B_1$ in Eq. (8).

Figure 5

Phase diagram of the WPP model for two uncorrelated Erdős-Rényi networks with identical mean degree $\mu$.

Figure 6

Phase diagram of the WPP model for two uncorrelated Erdős-Rényi networks with mean degree ${\mu }_1$ and ${\mu }_2$. Horizontal axis is ${\nu }_2=p{\mu }_2$. Each solid curve shows the location of the continuous transition for a different value of ${\nu }_1=p{\mu }_1$, from right to left ${\nu }_1=\{0.2,0.5,0.7,1,1.5\}$. The black dashed line represent points where ${\mu }_1={\mu }_2$.

Figure 7

Phase diagram of the WPP model for three uncorrelated Erdős-Rényi networks with identical mean degree $\mu$. The solid line gives the location of the continuous transition; the dashed line gives the location of the discontinuous transition. The point $C$ is the critical point.

Figure 8

Phase diagram of the WBP model for two uncorrelated Erdős-Rényi networks with identical mean degree $\mu$. The solid line gives the location of the continuous transition; the dashed line gives the location of the discontinuous transition. The point $C$ is the critical point.

Figure 9

Phase diagram of the WBP model for two uncorrelated Erdős-Rényi networks with mean degree ${\mu }_1$ and ${\mu }_2$. Horizontal axis is ${\nu }_2=p{\mu }_2$. Each solid curve shows the location of the continuous transition for a particular value of ${\nu }_1$, from top to bottom ${\nu }_1=\{1.5,2.193,5,10\}$. Dashed curves show the corresponding location of the discontinuous transition (which is always above the continuous transition), with circles marking the critical end point.

Figure 10

A representation of a cluster of critical vertices in WPP. Hatching indicates that vertices are members of the WPP percolating cluster. Because critical vertices are in the percolating cluster for WPP, a critical vertex may be linked to the percolating cluster via another critical vertex. That is, external edges of type $Z_i$ are not necessarily required. Furthermore, this means that critical dependencies can be bidirectional: it is possible for avalanches to propagate in either direction along such edges. Note that outgoing critical edges must be of the opposite type to the incoming one. The boxes containing crosses represent the probability $Z_n-R_n$.

Figure 11

Representation of the probability $R_1$ that, on following an edge of type 1, we encounter a (nondamaged and nonseed) vertex that has $\ge 1$ child edge of type 2 leading to a member of the percolating cluster and zero of type 1. The barred line represents the probability $1-Z_1$. The arrow in the edge is to illustrate the direction of propagation of activation.

Figure 12

An example of a critical cluster in WBP. Avalanches of activation propagate through the cluster following the arrowed edges. If an upstream vertex is activated, all downstream critical vertices will in turn be activated. Note that, unlike for WPP, in WBP it is not possible for an edge to be arrowed in both directions. Activation can only ever propagate in one direction along a given edge. Also note that in the WBP case outgoing critical edges must be of the same type as the incoming one.