Double Percolation Phase Transition in Clustered Complex Networks

The internal organization of complex networks often has striking consequences on either their response to external perturbations or on their dynamical properties. In addition to small-world and scale-free properties, clustering is the most common topological characteristic observed in many real networked systems. In this paper, we report an extensive numerical study on the effects of clustering on the structural properties of complex networks. Strong clustering in heterogeneous networks induces the emergence of a core-periphery organization that has a critical effect on the percolation properties of the networks. We observe a novel double phase transition with an intermediate phase in which only the core of the network is percolated and a final phase in which the periphery percolates regardless of the core. This result implies breaking of the same symmetry at two different values of the control parameter, in stark contrast to the modern theory of continuous phase transitions. Inspired by this core-periphery organization, we introduce a simple model that allows us to analytically prove that such an anomalous phase transition is, in fact, possible.

Popular Summary

The internal organization of complex networks often has striking consequences for their response to external perturbations or their dynamical properties. Percolation theory has played a prominent role in understanding the anomalous behaviors observed in networks after the failure of their constituent parts. However, the role of clustering in percolation properties of networks is still unclear, despite being one of the most common topological patterns of real complex networks. We perform a thorough study of the effect of clustering on the structural properties of networks and the consequences on their percolation properties.

We find that strong clustering in heterogeneous networks induces a core-periphery organization that has a critical effect on the percolation properties of networks. We observe a novel “double percolation” phase transition with an intermediate state in which only the core is percolated and a final phase in which the periphery percolates, regardless of the core; this break between core and periphery in terms of percolation can arise because of clustering. Inspired by this core-periphery organization, we introduce a simple model that allows us to prove analytically that such an anomalous phase transition is possible. This fact is contrary to the common belief that it is not possible to have two or more consecutive continuous phase transitions associated with the same symmetry breaking.

Our work motivates the search for multiple phase transitions in phenomena beyond percolation and also provides a new definition of the core and periphery of a network. We expect that our findings may have applications in studying the spread of disease epidemics.

Figure 1

Bond percolation simulations for networks of $N=5\times {10}^4$ nodes with a power-law degree distribution, $\gamma =3.1$, and different levels of clustering. (a) Relative size of the largest connected component $g$ as a function of the bond occupation probability $p$. (b) Degree-dependent clustering coefficient $\overline{c}(k)$. (c) Susceptibility $\chi$ as a function of the bond occupation probability $p$. (d) Percolation threshold ($p_{\max }$) as a function of the level of clustering.

Figure 2

Bond percolation simulations for networks with a power-law degree distribution with $\gamma =3.1$, target clustering spectrum $\overline{c}(k)=0.25$, and different network sizes. (a) Relative size of the largest connected component as a function of the bond occupation probability $p$. (c) Susceptibility $\chi$ as a function of the bond occupation probability $p$. (b, d) Position $p_{\max }$ and height ${\chi }_{\max }$ of the two peaks of $\chi$ as functions of the network size $N$. The straight lines are power-law fits, and (b) and (d) show the measured values of the critical exponents.

Figure 3

(a–c) clustering $m$-core decomposition of three different networks with $N=5\times {10}^4$, $\gamma =3.1$, and different levels of clustering, $\overline{c}(k)=0.001$, 0.1, 0.25. The color code of a node represents its $m$ coreness. For instance, nodes colored violet belong to the $m0$-core but not to the $m1$-core and are said to have $m$ coreness of zero. The blue colored nodes belong to the $m1$-core but not to the $m2$-core and have $m$ coreness of 1, etc. The visual representation is as follows. The outermost circle and its contents represent the $m0$-core and therefore the entire network. If we recursively remove all edges of multiplicity 0, we obtain the $m1$-core subgraph, which is contained within the $m0$-core. Nodes with no remaining connections do not belong to the $m1$-core, have $m$ coreness of 0, and are located at the perimeter of the outermost circle. If the $m1$-core is fragmented into different disconnected components, these components are represented as nonoverlapping circles within the outermost one and with nodes of $m$ coreness of 1 located in their perimeters [see, for instance, panels (b) and (c)]. The same process is repeated for each disconnected $m1$-core, which will contain a subset of the $m2$-core, and so on. Links between nodes are not depicted for clarity. (d) The size of the giant $m$-core as a function of $m$ for the networks shown in panels (a–c).

Figure 4

Bond percolation simulations of the core and periphery of a network with $N=5\times {10}^4$, $\gamma =3.1$, and target clustering spectrum $\overline{c}(k)=0.25$. The bond occupation probability to separate the core is $p=0.2$. The susceptibility curve of the periphery (dashed blue line) has been divided by 5 for ease of comparison.

Figure 5

Bond percolation simulations for the core-periphery random graph model with $\alpha =1$ (left column) and $\alpha =0.5$ (right column). In both cases, the core has an average degree of ${\overline{k}}_c=10$ and the periphery ${\overline{k}}_p=2.5$. The core-periphery ratio is $r=0.2$. The black dashed line in plot (b) is the numerical solution of Eqs. (1) and (2) with ${\overline{k}}_{cp}=0$. The inset shows the approach to the theoretical prediction at the second transition point as the size of the system is increased.

Figure 6

Top panels: Bond percolation simulations for networks of 10000 nodes with a power-law degree distribution with $\gamma =3.5$ and different levels of clustering. (a) Relative size of the largest connected component $g$ as a function of the bond occupation probability $p$. (b) Degree-dependent clustering coefficient $\overline{c}(k)$. (c) Susceptibility $\chi$ as a function of bond occupation probability $p$. (d) Percolation threshold ($p_{\max }$) as a function of the level of clustering. Bottom panels: (e-g) $m$-core decomposition of three different networks of 50000 nodes, $\gamma =3.5$, and different levels of clustering, $\overline{c}(k)=0.01$, 0.10, 0.25. (h) Size of the largest connected component of the $m$-core as a function of $m$.

Figure 7

Top panels: Bond percolation simulations for networks of 10000 with a power-law degree distribution with $\gamma =4$ and different levels of clustering. (a) Relative size of the largest connected component $g$ as a function of the bond occupation probability $p$. (b) Degree-dependent clustering coefficient $\overline{c}(k)$. (c) Susceptibility $\chi$ as a function of bond occupation probability $p$. (d) Percolation threshold ($p_{\max }$) as a function of the level of clustering. Bottom panels: (e–g) $m$-core decomposition of three different networks of 50000 nodes, $\gamma =4$, and different levels of clustering, $\overline{c}(k)=0.01$, 0.05, 0.25. (h) Size of the largest connected component of the $m$-core as a function of $m$.

Figure 8

A network of 50000 nodes, with a power-law degree distribution with $\gamma =3.1$ and a clustering spectrum $\overline{c}(k)=0.25$. The nodes are distributed according to the $m$-core decomposition. Red nodes (1811) are the core because they belong to the giant component after we perform a bond percolation with $p=0.2$ (between the two percolation thresholds). Blue and green nodes are peripheral nodes that belong to the giant component at $p=0.5$ (just after the second percolation threshold). Once we subtract the core, blue nodes (10408) still remain in the GC; meanwhile, green nodes (4271) belong to small components. Black nodes (33510) never belong to the GC.

Figure 9

Bond percolation simulations for the core-periphery random graph model for $\alpha =1$ for different sizes. In both cases, the core has an average degree ${\overline{k}}_c=10$ and the periphery ${\overline{k}}_p=2.5$. The core-periphery ratio is $r=0.2$. (a) Relative size of the largest connected component as a function of the bond occupation probability $p$. (c) Susceptibility $\chi$ as a function of bond occupation probability $p$. (b, d) Position $p_{\max }$ and height ${\chi }_{\max }$ of the two peaks of $\chi$ as a function of network size $N$. The straight lines are power-law fits. Panels (b) and (d) show the measured values of the critical exponents.

Figure 10

Bond percolation simulations for the core-periphery random graph model for $\alpha =0.5$ for different sizes. In both cases, the core has an average degree ${\overline{k}}_c=10$ and the periphery ${\overline{k}}_p=2.5$. The core-periphery ratio is $r=0.2$. (a) Relative size of the largest connected component as a function of the bond occupation probability $p$. (c) Susceptibility $\chi$ as a function of bond occupation probability $p$. (b, d) Position $p_{\max }$ and height ${\chi }_{\max }$ of the two peaks of $\chi$ as a function of network size $N$. The straight lines are power-law fits. Panels (b) and (d) show the measured values of the critical exponents.

Figure 11

Left panel: Bond percolation simulations for the US air transportation network. The relative size of the largest connected component $g$ and its susceptibility $\chi$ as a function of the bond occupation probability $p$ are shown. Right panel: $m$-core decomposition.

Figure 12

Left panel: Bond percolation simulations for the human disease network. The relative size of the largest connected component $g$ and its susceptibility $\chi$ as a function of the bond occupation probability $p$. Right panel: $m$-core decomposition.

Figure 13

Left panel: Bond percolation simulations for the Pokec online social network. The relative size of the largest connected component $g$ and its susceptibility $\chi$ as a function of the bond occupation probability $p$ are shown. Right panel: $m$-core decomposition.