Message passing theory for percolation models on multiplex networks with link overlap

Multiplex networks describe a large variety of complex systems, including infrastructures, transportation networks, and biological systems. Most of these networks feature a significant link overlap. It is therefore of particular importance to characterize the mutually connected giant component in these networks. Here we provide a message passing theory for characterizing the percolation transition in multiplex networks with link overlap and an arbitrary number of layers $M$. Specifically we propose and compare two message passing algorithms that generalize the algorithm widely used to study the percolation transition in multiplex networks without link overlap. The first algorithm describes a directed percolation transition and admits an epidemic spreading interpretation. The second algorithm describes the emergence of the mutually connected giant component, that is the percolation transition, but does not preserve the epidemic spreading interpretation. We obtain the phase diagrams for the percolation and directed percolation transition in simple representative cases. We demonstrate that for the same multiplex network structure, in which the directed percolation transition has nontrivial tricritical points, the percolation transition has a discontinuous phase transition, with the exception of the trivial case in which all the layers completely overlap.

Figure 1

A multiplex network with $M=3$ layers and link overlap is shown in panel (a). In panel (b) the different types of nontrivial multilinks connecting the nodes are listed.

Figure 2

A multiplex network with link overlap demonstrating that the DMCGC is not equivalent to the MCGC. Here the multiplex network has $M=2$ layers corresponding to the networks formed by links indicated, respectively, with solid and dashed lines. In panel (a) we assume that one node is connected to the DMCGC. By applying the message passing algorithm described in Sec. 7, we observe that two nodes of the network do not belong to the DMCGC. In panel (b) we consider the same multiplex network configuration but this time we assume that a single node is connected to the MCGC. By applying the message passing algorithm described in Sec. 8 we observe that all the nodes of this network belong to the MCGC.

Figure 3

The critical lines of discontinuous hybrid phase transition (red dashed line) and of continuous phase transition (blue solid line) describing the emergence of the DMCGC are shown for the case of a multiplex networks with two layers and the Poisson multidegree distribution with $\langle k^{(1,0)}\rangle =\langle k^{(0,1)}\rangle =c_1$ and $\langle k^{(1,1)}\rangle =c_2$.

Figure 4

Nondirectional character of the message passing approach to compute the MCGC.

Figure 5

Schematic representation of the message passing algorithm to calculate the MCGC in the presence of link overlap. The $\infty$ symbols represent whether node $i$ is connected or not to the MCGC by a node different from $j$ on a given layer.

Figure 6

The critical line of a discontinuous hybrid phase transition is shown for a multiplex networks with two layers and Poisson multidegree distribution with $\langle k^{(1,0)}\rangle =\langle k^{(0,1)}\rangle =c_1$ with $\langle k^{(1,1)}\rangle =c_2$.

Figure 7

The lines of critical points for the discontinuous hybrid transition describing the emergence of the MCGC are shown for the case of a multiplex networks formed layers with a Poisson multidegree distribution with $\langle k^{(1,0,0)}\rangle =\langle k^{(0,1,0}\rangle =\langle k^{(0,0,1)}\rangle =c_1$ with $\langle k^{(1,1,0)}\rangle =\langle k^{(1,0,1)}\rangle =\langle k^{(0,1,1)}\rangle =c_2$ and $\langle k^{(1,1,1)}\rangle =c_3$. The lines of the figure refer to critical lines for constant values of $p{c}_2$ given, respectively, by $p{c}_2=0.0$ (blue dashed line), $p{c}_2=0.25$ (red dotted line), $p{c}_2=0.5$ (orange dot-dashed line), and $p{c}_2=0.75$ (green long-dashed line).

Figure 8

The lines of critical points for the discontinuous hybrid transition describing the emergence of the MCGC are shown for the case of a multiplex network formed by three layers with a Poisson multi degree distribution with $\langle k^{(1,0,0)}\rangle =\langle k^{(0,1,0}\rangle =\langle k^{(0,0,1)}\rangle =c_1$ with $\langle k^{(1,1,0)}\rangle =\langle k^{(1,0,1)}\rangle =\langle k^{(0,1,1)}\rangle =c_2$ and $\langle k^{(1,1,1)}\rangle =c_3$. The lines of the figure refer to critical lines for constant values of $p{c}_1$ given, respectively, by $p{c}_1=0.0$ (blue, dashed line), $p{c}_1=0.5$ (red dotted line), $p{c}_1=1.0$ (orange dot-dashed line), $p{c}_1=1.5$ (green long-dashed line), and $p{c}_1=2.0$ (dark green tiny-dashed line).

Figure 9

Simulations of the MCGC for $p=1$ are shown as a function of $c_3$ for $c_1=1.0,c_2=0.15$ (green diamonds) and for $c_1=0.4,c_2=0.0$ (blue triangles). The results were obtained from simulation of three-layer multiplex networks with $N={10}^4$ nodes. The data have been obtained for a single realization in the case of $c_1=1.0,c_2=0.15$, and they have been averaged over 10 realizations for $c_1=0.4,c_2=0.0$. The simulations results perfectly match the theoretical expectations (solid lines). Notice that in both case we have a discontinuous jump although the jump is too small to be appreciated for $c_1=0.4,c_2=0.0$.