Explosive percolation transitions in growing networks

Recent extensive studies of the explosive percolation (EP) model revealed that the EP transition is second order with an extremely small value of the critical exponent $\beta$ associated with the order parameter. This result was obtained from static networks, in which the number of nodes in the system remains constant during the evolution of the network. However, explosive percolating behavior of the order parameter can be observed in social networks, which are often growing networks, where the number of nodes in the system increases as dynamics proceeds. However, extensive studies of the EP transition in such growing networks are still missing. Here we study the nature of the EP transition in growing networks by extending an existing growing network model to a general case in which $m$ node candidates are picked up in the Achiloptas process. When $m=2$, this model reduces to the existing model, which undergoes an infinite-order transition. We show that when $m\ge 3$, the transition becomes second order due to the suppression effect against the growth of large clusters. Using the rate-equation approach and performing numerical simulations, we also show that the exponent $\beta$ decreases algebraically with increasing $m$, whereas it does exponentially in a corresponding static random network model. Finally, we find that the hyperscaling relations hold but in different forms.

Figure 1

The growing network model with $m=3$: Plot of $n_s\left(p\right)$ versus $s$ at $p=p_c$ (blue solid line), $p>p_c$ (red dashed curves), and $p<p_c$ (black solid curves) based on numerical values obtained from the rate equation. The transition point $p_c$ and the exponent $\tau$ are estimated as $p_c=0.413842\left(1\right)$ and 2.5, respectively. The black dotted line is a guide line with slope $-2.5$.

Figure 2

The growing network model with $m=3$: Scaling plot of $n_s\left(p\right)s^{\tau }$ versus $s|p-p_c{|}^{1/\sigma }$ for different values of $p$ in the region (a) $p<p_c$ and (b) $p>p_c$. Data for different $p$ values are well collapsed onto a single curve by choosing $\sigma =0.720\left(2\right)$ and $\tau =2.500\left(1\right)$.

Figure 3

The growing network model with $m=3$: Plot of $G\left(p\right)$ versus $p$. Data points are obtained from the rate equation. Inset: Dashed line is a guideline with slope 0.694(2).

Figure 4

The growing network model with $m=3$: Plot of the mean cluster size $\langle s\rangle$ as a function of $p$. Data points are obtained from the rate equation. To take into account of finite-size effect, we truncate cluster size at given sizes $s^{*}={10}^3,{10}^4,{10}^5$ (dashed curves from below), and ${10}^6$ (solid curve). Insets: Plots of $\langle s\rangle$ versus $|p-p_c|$ for $p<p_c$ (left) and $p>p_c$ (right). Dashed lines are guidelines with slope $-0.696\left(3\right)$.

Figure 5

The growing network model: (a) Plot of $1-p_c$ versus $m$. Data points obtained from the rate equation seem to fit to the formula $1-p_c=1.81/m$. (b) Plot of $\beta$ versus $m$. Data points obtained from the rate equation seem to fit to the formula $\beta =1/(m-1.56)$.

Figure 6

The growing network model: shown are the testings whether the empirical formulas for the exponents (a) $\tau -2=1/(m-1)$, (b) $1/\sigma =(m-1)\beta$, and (c) ${\gamma }_p=(m-2)\beta$ are correct. Data points are obtained from the rate equation.

Figure 7

The static network model with $m=3$: Plot of $n_s\left(t\right)$ versus $s$ at $t=t_c$ (blue solid line), for $t>t_c$ (red dashed curves), and for $t<t_c$ (black solid curves) based on numerical values obtained from the rate equation. The transition point $t_c$ is determined as $t_c=0.849130\left(1\right)$ and the exponent $\tau$ is estimated as $\tau =2.105\left(5\right)$. The black dotted line is a guideline with the slope $-2.105$.

Figure 8

The static network model with $m=3$: Scaling plot of $n_s\left(t\right)s^{\tau }$ versus $s|t-t_c{|}^{1/\sigma }$ (a) for $t<t_c$ and (b) for $t>t_c$. Data points are well collapsed by taking $\tau =2.105\left(5\right)$ and $\sigma =0.790\left(1\right)$.

Figure 9

The static network model with $m=3$: Plot of the order parameter $G\left(t\right)$ as a function of $t$. Inset: The dotted line is a guideline with the slope $0.133\left(1\right)$.

Figure 10

The static network model with $m=3$: Plot of $\langle s\rangle$ as a function of $t$. To take into account the finite-size effect, we truncate cluster size at given sizes $N_c={10}^4,5\times {10}^4,{10}^5$ (dashed curves from below), and $5\times {10}^5$ (solid curve). Inset: Plot of the mean cluster size as a function of $t$ for $t>t_c$ (right) and for $t<t_c$ (left). Both dashed lines are guidelines with slope $-1.131\left(6\right)$.

Figure 11

The static network model: (a) Plot of estimated values of $1-t_c$ versus $m$ on a semilogarithmic scale. (b) Plot of estimated values of $\beta$ versus $m$ on a semilogarithmic scale. Data points likely lie on a straight line asymptotically. The error bar of each data point is smaller than the respective symbol size.

Figure 12

The static network model: Shown are the testings of whether the empirical formulas for (a) $\tau$, (b) $\sigma$, and (c) ${\gamma }_p$ are fit to numerical data points obtained from the rate equation.

Figure 13

The growing network model with $m=3$: Scaling plot of $n_s\left(p\right)s^{\tau }$ versus $s|p-p_c{|}^{1/\sigma }$. Data points are obtained from Monte Carlo simulations. Data collapse is established onto a single curve by choosing $\tau =2.5$ and $\sigma =0.72$ for (a) $p<p_c$ and for (b) $p>p_c$.

Figure 14

The growing network model with $m=3$: Scaling plot of $G{N}^{\beta /\overline{\nu }}$ versus $(p-p_c)N^{1/\overline{\nu }}$ for the system sizes $N/{10}^4=2^3-2^{10}$. Data points obtained from numerical simulations are well collapsed onto a single curve with $1/\overline{\nu }=0.35\left(3\right)$ and $\beta /\overline{\nu }=0.24\left(3\right)$.

Figure 15

The growing network model with $m=3$: Scaling plot of $\langle s\rangle N^{-{\gamma }_p/\overline{\nu }}$ versus $(p-p_c)N^{1/\overline{\nu }}$ for different system sizes $N/{10}^4=2^6-2^{10}$. Data obtained from numerical simulations are well collapsed onto a single curve with ${\gamma }_p=0.696$ and $1/\overline{\nu }=0.35$.

Figure 16

The static network model with $m=3$: Scaling plot of $n_s\left(t\right)s^{\tau }$ versus $s|t-t_c{|}^{1/\sigma }$ (a) for $t<t_c$ and (b) for $t>t_c$. Data points obtained from numerical simulations are well collapsed onto a single curve with $\tau =2.105$ and $\sigma =0.79$.

Figure 17

The static network model with $m=3$. Scaling plot of $G{N}^{\beta /\overline{\nu }}$ versus $(t-t_c)N^{1/\overline{\nu }}$ for different system sizes $N/{10}^4=2^7-2^{10}$. Data points obtained from numerical simulations are reasonably collapsed with $1/\overline{\nu }=0.45$ and $\beta /\overline{\nu }=0.06$.

Figure 18

The static network model with $m=3$: Scaling plot of $\langle s\rangle N^{-{\gamma }_p/\overline{\nu }}$ versus $(t-t_c)N^{1/\overline{\nu }}$ for different system sizes $N/{10}^4=2^7-2^{10}$. Data points obtained from Monte Carlo simulations are well collapsed with ${\gamma }_p=1.133$ and $1/\overline{\nu }=0.45$.

Figure 19

The static network model with $m=3$: Scaling plot of $\chi N_c^{-\gamma /{\overline{\nu }}_r}$ versus $(t-t_c)N_c^{1/{\overline{\nu }}_r}$ for different cutoff sizes $N_c/{10}^3=2^6-2^9$. Data points obtained by the rate-equation method are well collapsed with $\gamma =1.01$ and $1/{\overline{\nu }}_r=0.73$.

Figure 20

The growing network model with $m=2$: Plot of $n_s\left(p\right)$ versus $s$ at $p=p_c$ (blue solid line), for $p>p_c$ (red dashed curves), and for $p<p_c$ (black solid lines) based on numerical values obtained from the rate equation. The transition point is estimated as $p_c=0.125$. For $p\le p_c, n_s\left(p\right)$ decays in a power-law manner, indicating that the transition is infinite order.