⇦Chinese Physics Letters, 2018, Vol. 35, No. 1, Article code 016402 Four Types of Percolation Transitions in the Cluster Aggregation Network Model * Wen-Chen Han(韩文臣), Jun-Zhong Yang(杨俊忠)** Affiliations School of Science, Beijing University of Posts and Telecommunications, Beijing 100876 Received 15 September 2017 *Supported by the National Natural Science Foundation of China under Grant Nos 11575036 and 11505016.
**Corresponding author. Email: jzyang@bupt.edu.cn Citation Text: Han W C and Yang J Z 2018 Chin. Phys. Lett. 35 016402 Abstract We study the percolation transition in a one-species cluster aggregation network model, in which the parameter $\alpha$ describes the suppression on the cluster sizes. It is found that the model can exhibit four types of percolation transitions, two continuous percolation transitions and two discontinuous ones. Continuous and discontinuous percolation transitions can be distinguished from each other by the largest single jump. Two types of continuous percolation transitions show different behaviors in the time gap. Two types of discontinuous percolation transitions are different in the time evolution of the cluster size distribution. Moreover, we also find that the time gap may also be a measure to distinguish different discontinuous percolations in this model. DOI:10.1088/0256-307X/35/1/016402 PACS:64.60.ah, 64.60.aq © 2018 Chinese Physics Society Article Text The notion of the percolation transition is widely applied to statistical physics, condensed matter, and other areas.[1-11] Different aggregation network models by adding edges have been proposed to study the percolation transition. It has been believed that the percolation transition is a continuous one and is characterized by the gradual growth of the giant connected component (GCC).[2-5,12] In 2009, Achlioptas et al. reported a discontinuous percolation transition, in a network aggregation model with the product rule.[13] In their model, two possible edges are randomly chosen in each time step and only the edge is selected if the product of the sizes of clusters containing the nodes connected by the edge is the smaller one. They measured ${\it \Delta}_N(a,b)$, the number of edges required for the GCC growing from smaller than $N^a$ to larger than $bN$, and found that ${\it \Delta}_N(a,b)$ follows the power law of $N^{2/3}$. When $N\to\infty$, the time gap ${\it \Delta}={\it \Delta}_N/N$ approaches 0, which suggests a discontinuous percolation transition (DPT). Although the following works showed that all random network aggregation models based on the Achlioptas process actually display a continuous percolation transition,[14,15] DPT was reported in other models. Cho et al. showed DPTs in lattice with the Achlioptas process by choosing the number of edges sub-linear to the system size.[16] Similar phenomena of DPTs were also found in some models, such as the Bohman–Frieze–Wormald model,[17] scale-free networks under the Achlioptas process,[18,19] a hierarchy of small-world bonds grafted onto a one-dimensional lattice,[20] and the cluster aggregation network models (CANMs).[21-23] The CANMs have been investigated by Cho et al. on random networks[22] and by Manna et al. based on lattice.[23] Both groups have found that CANMs could exhibit continuous percolation transitions (CPTs) and DPTs, which can be distinguished by $\Delta G_{\max}$, the maximum increment of the GCC induced by a single edge.[24] When $N\to\infty$, $\Delta G_{\max}$ approaches 0 for CPTs but $\Delta G_{\max}$ remains finite for DPTs.[17,25,26] Recently, Cho and Kahng studied a two-species CANM and found two types of DPTs,[27] type-I DPTs where only one cluster survives and type-II DPTs where a giant cluster coexists with small clusters. Now, it is an interesting question whether one-species CANMs may exhibit different types of DPTs. In this Letter, we investigate a one-species CANM based on random networks and find the system can show two types of DPTs as well as two types of CPTs. The two CPTs are distinguished by the time gap ${\it \Delta}$ in the thermodynamic limit while the two DPTs show different time evolutions of cluster size distributions (CSDs). Moreover, our results show that ${\it \Delta}$ may also be a measure to distinguish two types of DPTs. We start with $N$ isolated nodes at the beginning. In each round, two nodes $i$ and $j$ are chosen with the probabilities $p_i$ and $p_j$, respectively, and the edge with them is connected. The probability $p_i$ is given by $$ p_i=c_i^\alpha\Big[\sum\nolimits_{k=1}^{N}{c_k^\alpha}\Big]^{-1},~~ \tag {1} $$ where $c_i$ represents the size of the cluster containing the node $i$, and $\alpha$ is a tunable non-positive parameter. The parameter $\alpha$ describes the suppression on the cluster sizes and the case $\alpha=0$ reduces to an ER network model.[12] When $\alpha$ decreases, the probability that nodes in small clusters are chosen increases. The self-edge or multi-edges are avoided. Here $L$ is the number of edges presenting in the network and we define the time as $t=L/N$. The average degree of the network is $\langle k\rangle=2t$ at the time $t$. When $t=1.1$ the network stops evolving. Suppose that there should be $m$ clusters in the network at time $t$. We sort them in descending order $S_1\ge S_2\ge\ldots\ge S_m$, where the relative size $S_k$ is defined as $N_k/N$ with $N_k$ being the number of nodes in the $k$th cluster. We consider four quantities, ${\it \Delta}$, $M'_2$, $\Delta G$ and $n_S$. Here ${\it \Delta}(a,b)$ represents the time gap from $S_1=N^{a-1}$ to $S_1=b$ and reflects the abruptness of the growing process. The smaller the value of ${\it \Delta}(a,b)$ is, the more abrupt the growing process is. In this work $a=b=1/2$ is fixed. The quantity $M'_2$,[17] defined as $M'_2=M_2-S_1^2$ with $M_2=\sum_{j}S_j^2$, reaches its maximum at the percolation transition,[28,29] $\Delta G_{\max}$ depicts the largest increment of $S_1$ induced by a single edge, $\Delta G_{\max}=0$ for CPTs and a finite $\Delta G_{\max}$ for DPTs in the thermodynamic limit, and $n_S(t)$ is the ratio of the number of clusters with relative size $S$ to the system size $N$ at time $t$. The results of simulation are averaged over 100 realizations.
cpl-35-1-016402-fig1.png
Fig. 1. The growing process of the system for different $\alpha$: (a) $\alpha=0$, (b) $\alpha=-0.3$, (c) $\alpha=-0.5$, (d) $\alpha=-0.8$, (e) $\alpha=-1$, and (f) $\alpha=-1.5$. The relative size of the GCC ($S_1$) in red and the relative size of the second largest cluster ($S_2$) in green for the left $Y$ axis. The scaled second moment minus the largest cluster ($M'_2$) in blue for the right $Y$ axis. The system size $N=10^6$.
We first consider the case with $\alpha=0$, in which all nodes share the same probability $p=1/N$ to be chosen in each round. In Fig. 1(a), $S_1$ becomes nonzero only when $t>0.5$ while $S_2=0$ always holds. The observations that $S_1 < 1$ and $S_2=0$ at $t=1.1$ indicate that there are still quite many clusters with small sizes, which is also manifested by the finite value of $M'_2$. With decreasing $\alpha$, the probability of choosing nodes in large clusters becomes smaller and the probability of nodes in small clusters being chosen becomes larger. As a result, mergers among clusters tend to firstly occur to those small clusters. After most small clusters have merged, the merging among clusters with medium sizes makes $S_1$ grow abruptly. Figure 1(b) shows that, when $\alpha=-0.3$, the time of peaking for $M'_2$ is delayed to around $t=0.84$ and $S_2$ grows larger together with $S_1$ at the percolation transition. The GCC takes over the whole network $S_1=1$ at $t=1.1$ in most realizations. When $\alpha$ further decreases, the peak time of $M'_2$ will be postponed to $t=1$ and $S_1$ grows more abruptly at the percolation transition. It can be seen from Figs. 1(c)–1(f) that $S_1$ grows abruptly in a very short time during which $M'_2$ reaches its maximum and collapses to 0. Here $S_1=1$ at $t=1.1$ for $\alpha < -0.5$ suggests that the final networks only contain one cluster with sparse connection density.
cpl-35-1-016402-fig2.png
Fig. 2. (a) The value of ${\it \Delta}(1/2,1/2)$ against the inverse of system size $1/N$ on a double logarithmic scale and (b) $\Delta G_{\max}$ against the inverse of system size $1/N$ on a double logarithmic scale. Here $\alpha=0$ in black, $\alpha=-0.3$ in red, $\alpha=-0.5$ in green, $\alpha=-0.8$ in blue, $\alpha=-1.0$ in cyan, $\alpha=-1.5$ in magenta.
It has been highly understood that the model with $\alpha=0$, evolving onto an ER network system, would exhibit a typical percolation transition, a CPT.[13,22] Then, what kind of percolation transition will be for the systems with negative $\alpha$? The growing processes in Fig. 1 only show the existence of the percolation transition and the intuitive analyses only give plausible results that may happen in the systems with different $\alpha$, but they cannot help us to infer whether the percolation transitions of these systems are CPTs or DPTs. Although the time evolution of $S_1$ cannot be used to distinguish different types of percolation transitions, two measures, ${\it \Delta}(1/2,1/2)$ and $\Delta G_{\max}$, related to $S_1$ can be used to distinguish different percolation transitions from each other.[13,17,24] Figure 2(a) shows $\Delta G_{\max}$ against the inverse of the system size ($1/N$) for different $\alpha$. When $\alpha=0$, ${\it \Delta}(1/2,1/2)$ is independent of the system size (see Fig. 2(a)), $\log_{10}(\Delta G_{\max})$ increases with $\log_{10}(1/N)$ in a linear way (see Fig. 2(b)). That is to say, GCC needs time to grow up whatever the system size is and $\Delta G_{\max}=0$ when $N\to\infty$, which verifies that the system exhibits a typical CPT.[17,22] When $\alpha$ becomes more negative, on a double logarithmic scale, the slope of ${\it \Delta}(1/2,1/2)$ against $1/N$ becomes larger while the slope of $\Delta G_{\max}$ against $1/N$ is smaller. When $-0.5 < \alpha < 0$, both ${\it \Delta}(1/2,1/2)$ and $\Delta G_{\max}$ approach 0 when $N\to\infty$, which indicates that the percolation transition is a CPT but not a typical one, in contrast to typical CPTs at $\alpha=0$. When $\alpha < -0.5$, ${\it \Delta}(1/2,1/2)$ approaching 0 while $\Delta G_{\max}$ remaining finite indicate a DPT, where GCC jumps abruptly and it costs slight time. This result is consistent with the fact that the boundary between CPTs and DPTs is $\alpha=-0.5$ in CANMs on random networks.[22,23]
cpl-35-1-016402-fig3.png
Fig. 3. Diagrams of ${\it \Delta}(1/2,1/2)$ and $\Delta G_{\max}$ against $\alpha$. Here ${\it \Delta}(1/2,1/2)$ in red and $\Delta G_{\max}$ in blue. The system size $N=10^5$ in plot (a) and $N=10^6$ in plot (b).
It should be noticed that the relations between $\Delta G_{\max}$ and $\alpha$ and ${\it \Delta}(1/2,1/2)$ and $\alpha$ are roughly reverse. We present them in Fig. 3 clearly. To our surprise, ${\it \Delta}(1/2,1/2)$ and $\Delta G_{\max}$ against $\alpha$ show interesting points. There exist two regimes of $\alpha$ with respect of $\Delta G_{\max}$, and the boundary between them is $\alpha=-0.5$. With decreasing $\alpha$, $\Delta G_{\max}$ increases when $\alpha>-0.5$ but stays unchanged when $\alpha < -0.5$. Considering that $\alpha=-0.5$ is the boundary between CPTs and DPTs, different behaviors in the range $(-0.5,0)$ and $(-1.5,-0.5)$ are acceptable. However, there exist three regimes of $\alpha$ with respect to ${\it \Delta}(1/2,1/2)$ and the boundaries between them are $\alpha=-0.5$ and $\alpha=-1$. Here ${\it \Delta}(1/2,1/2)$ shows different behaviors in CPTs and DPTs, but ${\it \Delta}(1/2,1/2)$ against $\alpha$ in DPTs shows different linear relations. The two different linear relations in DPTs are independent of the system size, as shown in Fig. 3. This probably indicates that there should exist two types of DPTs[5,27] and the boundary of these two types is $\alpha=-1$. The mechanisms behind the two different DPTs are analyzed by Cho et al.[27] and they have shown that systems with different DPTs will show different time evolutions of CSD. Before the percolation transition, only medium clusters exist for type-I DPTs while medium clusters coexist with many small clusters for type-II DPTs. After the percolation, only one cluster exists for type-I DPTs but a finite GCC and small clusters coexist for type-II DPTs.[5,27] We examine the time evolutions of CSDs for different $\alpha$. For $\alpha=-0.8$ where the percolation transition occurs at $t_{\rm c}=0.999935$, we present the CSD at $t_{\rm c}^-=0.9999$ in Fig. 4(a) and $t_{\rm c}^+=1$ in Fig. 4(b). Figures 4(c) and 4(d) show the CSDs at $t_{\rm c}^-=0.99995$ and $t_{\rm c}^+=1.00001$, respectively, for $\alpha=-1.5$ with $t_{\rm c}=1.000005$. According to the time evolution of CSDs,[27] Fig. 4 shows clearly that a system with $\alpha\in(-1,-0.5)$ will exhibit type-II DPTs, where many small clusters exist before and after the percolation, and that a system with $\alpha\in(-\infty,-1)$ should exhibit type-I DPTs, where there only exist medium clusters before the percolation and there only exist one or a few large clusters after the percolation. In type-II DPTs, cluster merging happens among small clusters and medium ones. In contrast, in type-I DPTs, there only exist medium clusters and cluster merging only happens among medium ones. This may be the reason why ${\it \Delta}(1/2,1/2)$ shows different behaviors in different types of DPTs.
cpl-35-1-016402-fig4.png
Fig. 4. Cluster size distributions: (a) $t_{\rm c}^-=0.9999$ and (b) $t_{\rm c}^+=1$ when $\alpha=-0.8$ with the percolation transition at $t_{\rm c}=0.999935$, (c) $t_{\rm c}^-=0.99995$ and (d) $t_{\rm c}^+=1.00001$ when $\alpha=-1.5$ with the percolation transition at $t_{\rm c}=1.000005$. The system size $N=10^6$.
In summary, we have studied the percolation transition in a one-species cluster aggregation network model in this work. It is found that the system would exhibit four types of percolation transitions, typical CPTs, non-typical CPTs, type-II DPTs and type-I DPTs, appearing successively with the decrease of the tunable parameter $\alpha$. The three critical values of $\alpha$ between them are 0, $-0.5$ and $-1$. Using the largest increment of $S_1$ by a single edge $\Delta G_{\max}$,[24] we can easily distinguish the discontinuous percolation transitions from the continuous percolation transitions. Measuring the time gap ${\it \Delta}(1/2,1/2)$, we can present two types of CPTs, the typical CPTs with finite ${\it \Delta}(1/2,1/2)$ and the non-typical CPTs with ${\it \Delta}(1/2,1/2)=0$ in the thermodynamic limit, where $S_1$ grows abruptly. Observing the time evolution of cluster size distribution $n_S(t)$, two types of DPTs, the type-I DPT with only one cluster after the percolation and the type-II DPT consisting of one largest cluster with some small clusters, can be distinguished from each other. These two types DPTs are already in the one-species cluster aggregation network model, while Cho and Kahng found them in a two-species cluster aggregation network model in a recent work.[27] The time gap ${\it \Delta}(1/2,1/2)$ may also be a measure for distinguishing these different percolation transitions in the cluster aggregation network models. References Explosive percolation: Unusual transitions of a simple modelRecent advances in percolation theory and its applicationsAnomalous critical and supercritical phenomena in explosive percolationExplosive percolation in the human protein homology networkContinuous percolation phase transitions of two-dimensional lattice networks under a generalized Achlioptas processCharacteristics of phase transitions via intervention in random networksContinuity of the explosive percolation transitionExplosive Percolation in Random NetworksExplosive Percolation Transition is Actually ContinuousOn the evolution of random graphsAvoiding a Spanning Cluster in Percolation ModelsPhase transitions in supercritical explosive percolationPercolation Transitions in Scale-Free Networks under the Achlioptas ProcessExplosive Percolation in Scale-Free NetworksOrdinary percolation with discontinuous transitionsHybrid Percolation Transition in Cluster Merging Processes: Continuously Varying ExponentsCluster aggregation model for discontinuous percolation transitionsA new route to Explosive PercolationImpact of single links in competitive percolationExplosive Percolation with Multiple Giant ComponentsContinuous Percolation with DiscontinuitiesTwo Types of Discontinuous Percolation Transitions in Cluster Merging ProcessesScaling behavior of explosive percolation on the square latticeBohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition
[1]Stauffer D and Aharony A 1994 Introduction to Percolation Theory (London: Taylor & Francis)
[2] Bastas N, Giazitzidis P, Maragakis M and Kosmidis K 2014 Physica A 407 54
[3]Araújo N, Grassberger P, Kahng B, Schrenk K J and Ziff R M 2014 Eur. Phys. J. Spec. Top. 233 2307
[4] Saberi A A 2015 Phys. Rep. 578 1
[5] D'Souza R M and Nagler J 2015 Nat. Phys. 11 531
[6] Rozenfield H D, Gallos L K and Malse H A 2010 Eur. Phys. J. B 75 305
[7] Liu M X, Fan J F, Li L S and Chen X S 2012 Eur. Phys. J. B 85 132
[8]Li Z W, Liu H J and Xu X 2013 Acta Phys. Sin. 62 0964101 (in Chinese)
[9] Jiao X, Hong J S, Yang H C, Yang C, Shi X H and Hu J Q 2014 Chin. Phys. B 23 076401
[10]Li L and Li K F 2015 Acta Phys. Sin. 64 136402 (in Chinese)
[11] Lee H K, Kim B J and Park H 2011 Phys. Rev. E 84 020101(R)
[12]Erdös P and Rényi A 1960 Publ. Math. 5 17
[13] Achlioptas D, D'Souza R M and Sperncer J 2009 Science 323 1453
[14] da Costa R A, Dorogovtsev S N, Goltsev A V and Mendes J F F 2010 Phys. Rev. Lett. 105 255701
[15] Riodan O and Warnke L 2011 Science 333 322
[16] Cho Y S, Hwang S, Herrmann H J and Kahng B 2013 Science 339 1185
[17] Chen W, Nagler J, Cheng X, Jin X, Shen H, Zheng Z and D'Souza R M 2013 Phys. Rev. E 87 052130
[18] Cho Y S, Kim J S, Park J, Kahng B and Kim D 2009 Phys. Rev. Lett. 103 135702
[19] Radicchi F and Fortunato S 2009 Phys. Rev. Lett. 103 168701
[20] Boettcher S, Singh V and Ziff R M 2012 Nat. Commun. 3 787
[21] Cho Y S, Lee J S, Herman H J and Kahng B 2016 Phys. Rev. Lett. 116 025701
[22] Cho Y S, Kahng B and Kim D 2010 Phys. Rev. E 81 030103(R)
[23] Manna S S and Chatterjee A 2011 Physica A 390 177
[24] Nagler J, Levina A and Timme M 2011 Nat. Phys. 7 265
[25] Chen W and D'Souza R M 2011 Phys. Rev. Lett. 106 115701
[26] Nagler J, Tiessen T and Gutch H W 2012 Phys. Rev. X 2 031009
[27] Cho Y S and Kahng B 2015 Sci. Rep. 5 11905
[28] Ziff R M 2010 Phys. Rev. E 82 051105
[29] Schrenk K J, Felder A, Deflorin S, Araújo N A M, D'Souza R M and Herrmann H J 2012 Phys. Rev. E 85 031103