Cumulative merging percolation: a long-range percolation process in networks

Cumulative Merging Percolation: A long-range percolation process in networks Lorenzo Cirigliano, 1, 2 Giulio Cimini, 3, 2 Romualdo Pastor-Satorras, 4 and Claudio Castellano 5, 2 1 Dipartimento di Fisica Universit`a “Sapienza”, P.le A. Moro, 2, I-00185 Rome, Italy. 2 Centro Ricerche Enrico Fermi, Piazza del Viminale, 1, I-00184 Rome, Italy 3 Dipartimento di Fisica e INFN, Universit`a di Roma “Tor Vergata”, I-00133 Rome, Italy 4 Departament de F´ısica, Universitat Polit`ecnica de Catalunya, Campus Nord B4, 08034 Barcelona, Spain 5 Istituto dei Sistemi Complessi (ISC-CNR), Via dei Taurini 19, I-00185 Rome, Italy (Dated: March 3, 2022) Percolation on networks is a common framework to model a wide range of processes, from cascading failures to epidemic spreading. Standard percolation assumes short-range interactions, implying that nodes can merge into clusters only if they are nearest-neighbors. Cumulative Merging Percolation (CMP) is an new percolation process that assumes long-range interactions, such that nodes can merge into clusters even if they are topologically distant. Hence in CMP percolation clusters do not coincide with the topological connected components of the network. Previous work has shown that a specific formulation of CMP features peculiar mechanisms for the formation of the giant cluster, and allows to model different network dynamics such as recurrent epidemic processes. Here we develop a more general formulation of CMP in terms of the functional form of the cluster interaction range, showing an even richer phase transition scenario with competition of different mechanisms resulting in crossover phenomena. Our analytic predictions are confirmed by numerical simulations. I. INTRODUCTION Percolation theory is among the most developed fields of statistical mechanics and mathematical physics. A percolation process can be defined as follows: We have a collection of elements and some connections among them. This object is called a graph, the elements are called vertices (or nodes) and the connections are called edges (or links). We then remove some nodes according to a certain probabilistic or deterministic rule. For instance, we can remove all nodes with more than a given number of connections, or we can remove nodes uniformly at random. At the end of the removal process we wonder about which connectivity properties are preserved. The main problem of percolation theory is to understand if a giant component (GC), that is a connected component of extensive size, still exists in the graph after the removal process. Originally, percolation was studied on various types of low-dimensional lattices. The powerful methods of statistical mechanics of phase transitions and critical phenomena, such as mean-field approximations, renormalization group, asymptotic expansions and scaling theory, provide us with a complete understanding of the percolation process on regular lattice topologies [ 1 ]. In the past 20 years, the interest about complex networks has led to a great deal of activity concerning percolation processes on graphs [ 2 – 6 ]. Percolation processes are used to model a wide range of natural phenomena, just by changing the underlying graph or the probabilistic rule that determines the removal of nodes. For instance, percolation on a regular lattice can model transport processes in porous media, such as electrical and hydraulic conduction, air permeability and diffusion [ 7 ]. On the other hand, percolation on random graphs [ 8 ] can be used to investigate the robustness of a networked system under intentional or random attacks [ 2 ]. Additionally, a deep connection exists between percolation and epidemic spreading. Indeed, the fundamental susceptible-infected-recovered (SIR) epidemic model on networks [ 9 ] can be mapped onto a bond percolation process [ 10 ]. Such a mapping allows to use the tools of percolation theory to get a full understanding of static properties of the SIR model. For epidemic processes which admit a stationary steady state, such as the susceptibleinfected-susceptible (SIS) model, this mapping is less immediate, and has been realized only through a new percolation model recently proposed [11]. Such a model, called cumulative merging percolation (CMP), is a truly long-range percolation process. This specification (long-range percolation) is often used for models where, in a lattice, additional links connecting sites separated by any euclidean distance are added, with a probability depending on the distance [ 12 , 13 ]. In CMP instead, distances are only topological and two nodes can belong to the same cluster even if no path of nearest-neighbor nodes connecting them belongs to the cluster itself. Models of similar type, called extendedneighborhood percolation models, have been studied on regular lattices [ 14 – 17 ]. In such models percolation clusters do not need to coincide with topologically connected components, as two nodes may form a cluster even if they are not nearest-neighbors but separated by paths of finite length (typically 2 or 3). In CMP this length can be arbitrarily large. CMP has been recently studied in a specific degreeordered case [ 18 ] to elucidate the behavior of the SIS model on random uncorrelated networks with power-law degree distribution P ( k ) ∼k−γ . By means of a scaling approach and numerical simulations, it was shown that the long-range nature of the model guarantees, for any γ > 2, the existence of a percolating cluster for any value of the control parameter (i.e., the degree threshold that determines node removal), at variance with what happens for the short-range counterpart [ 19 , 20 ]. The aim of arXiv:2203.01014v1 [cond-mat.stat-mech] 2 Mar 2022 2 the present work is to define in full generality CMP on networks. We present a scaling theory that extends the one introduced in Ref. [ 18 ] to more general forms of the interaction range. We then consider in detail two paradigmatic functional forms of the interaction range, deriving predictions concerning the existence of a phase-transition at finite or infinite value of the control parameter and the associated critical behavior. We obtain a rich scenario with competition of different mechanisms resulting in crossover phenomena, which is confirmed by means of numerical simulations. The paper is organized as follows: In Sec. II, we first define the CMP process in the most general form and present the detailed specifications considered in the rest of the paper. In Sec. III we write a general scaling approach used to analyze the process. Sec. IV is dedicated to a detailed analysis of two classes of CMP, characterized by algebraically and logarithmically growing interaction range. Finally, in Sec V, we summarize our main results and present some possible future research paths. II. CUMULATIVE MERGING PERCOLATION In classical (short-range) percolation, a cluster coincides with a topologically connected component C , i.e., a subset of nodes such that for any two nodes i and j there exists a path connecting them, made of nearest-neighboring nodes belonging to C . Thus, for instance, if all nearest neighbors of a node are removed, this node cannot be a part of any cluster – except the one formed by itself only. In order to introduce a long-range model, we need to go beyond such a definition. In this section, we define a general procedure to define clusters that may be composed of topologically disconnected and arbitrarily distant components. A. General definition We denote a graph by G ( V, E ), where V is the set of nodes and E is the set of edges. Each node i∈V is endowed with a non-negative mass mi≥0. The mass of the set composed by two nodes i and j is given by the sum of their masses m=mi+mj.(1) Apartition of the graph P ( G ) is a collection of subsets of nodes P(G) = {A}A⊆V such that: (i) the sets in P cover V ; (ii) every element in V belongs to exactly one subset in P . Each element of P is called cluster, denoting with Ci the cluster to which node i belongs. Notice that by definition each node belongs only to one cluster. Because of Eq. (1) , the mass of a cluster is the sum of the masses of all nodes belonging to it. We define the interaction range of a cluster to be a non-decreasing function of its mass, r ( m ). We stress that these clusters need not be topologically connected components. Given a pair of nodes ( i, j ), the merging operator Mi,j , acting on the space of all partitions of the graph, merges the two clusters Ciand Cjif and only if di,j ≤min{r(mCi), r(mCj)}; (2) where di,j is the topological distance between i and j . If the condition eqrefmarging is not fulfilled, the merging operator leaves the two clusters unaltered. Notice that the merging occurs only if node i is within the interaction range of the cluster Cj and vice-versa, and that two clusters may be merged together even if they are at arbitrary topological distance with each other, provided the interaction ranges are sufficiently large. We define the cumulative merging procedure as follows: 1. fix an infinite sequence ( it, jt ) t∈N of pairs of nodes of V; 2. start from the finest partition P0:={{i}, i ∈V}; 3. iteratively apply the merging operator Pt+1 =Mit,jt(Pt).(3) The asymptotic partition P∞:= lim t→∞ Pt,(4) depends, in principle, on the sequence ( it, jt ) t∈N . Consider for instance the case in which all nodes have an infinite interaction range, except node a and node b , which are distant nodes with small interaction range. The sequence ( it, jt )=( a, b ) for every t leads to P∞ = P0 , while it is immediate to realize that P∞ will be different for other sequences. A way to overcome this difficulty is to consider only recurrent sequences: we say that the sequence ( it, jt ) t∈N is recurrent if {it, jt} = {k, l} infinitely many times, for every k, l ∈V with k6 = l . An important result on the asymptotic partition, whose proof can be found in Ref. [ 11 ], guarantees that the cumulative merging procedure is well defined, i.e. sequence-independent, provided that the sequence is recurrent. In summary, given a graph, a collection of node masses, and the function r ( m ), the cumulative merging procedure generates a unique partition of the graph in clusters, not necessarily topologically connected. Notice that nodes with r ( mi ) < 1 by construction do not play any role (i.e., they necessarily form clusters of size 1), apart from determining the topological distances among other nodes. We denote them as inactive, while nodes with r ( mi ) ≥ 1 are active, as they may participate in merging events and form clusters of size larger than 1. The CMP model defined above can be seen as a percolation process: Depending on the function r ( m ), the node masses and the underlying graph, the asymptotic partition may be composed of microscopic clusters only 3 or include a giant cluster encompassing a finite fraction of the total number of nodes. It is a long-range percolation model because clusters may be composed by different and arbitrarily distant topologically connected components. This is qualitatively different from extended-range percolation models which allow only finite distances between disconnected components. B. A specific class of CMP models Following Refs. [ 11 , 18 ], we set node masses to be equal to their degree, i.e. mi = ki . In this way, the mass of a cluster is the sum of the degrees of the nodes that belong to it. Moreover, we take the interaction range to be a function of the ratio between m and a parameter ka , that plays the role of control parameter in the percolation problem, r(m) = f(m/ka),(5) where f ( x ) is a non-decreasing function, with f (1) = 1 and f ( x ) < 1 for x < 1. According to this definition all nodes with degree ki< ka have interaction range r < 1 and are thus inactive. Nodes with degree larger than or equal to kaare active. In this way percolation occurs in a degree-ordered way: Increasing the control parameter ka is equivalent to removing nodes of increasingly higher degree. For the minimal value ka = kmin , all nodes are active and hence the clusters coincide with the components of the underlying graph. For large ka→ ∞ the number of active nodes gets smaller and smaller and the nontrivial question is whether an extensive cluster still exists. With all these specifications, given a network and the value of ka , the final partition of the CMP is univocally defined. Fig. 1 reports an example of how the CMP process unfolds and what is the final partition of the graph. Other choices for the initial masses, the interaction range and the underlying graph are possible, leading to a wealth of different models with different critical properties. For example, if r ( m ) = 1, for any m≥ 1, CMP coincides with standard site percolation, either in its degree-ordered version [ 19 , 20 ], if the initial mass of node i is mi = ki Θ( ki−ka ), or in its random version, if mi = ki with probability φ and 0 otherwise. Taking instead a generic interaction range r ( m ) and again mi = ki with probability φ and 0 otherwise, one has a truly long-range CMP with random activation. The investigation of these and other variants constitutes an interesting avenue for future research. In the following we study this class of degree-ordered CMP processes on power-law degree-distributed networks, described by uncorrelated random graphs with degree distribution, in the continuous approximation, P(k)=(γ−1)kγ−1 min k−γ(6) where γ > 2 and kmin is the minimum degree of nodes in the network. FIG. 1. Visual representation of a CMP process on a graph with ka = 3 and r ( m ) = m/ka . (a) All nodes in the graph are shown. Colors depend on the degree k . (b) Initial configuration of the merging process, with ka = 3, each node forming a cluster. Empty circles are inactive nodes. Colored dashed regions represent the interaction range of each active node. (c) Intermediate configuration of the merging process. Dark red regions represent clusters. (d) Final configuration of the merging process. From (c) to (d) the long-range nature of the process plays a crucial role. Note that the process ends since the interaction range of the cluster with r = 2 does not reach any node of the cluster with r= 22/3. Our aim is to investigate the formation of a CMP giant cluster (CMPGC) 1 . Hence we focus on the quantity SCMP , defined as the fraction of nodes belonging to the CMP largest cluster, as a function of the control parameter ka . In percolation theory it is customary to consider the fraction of active (non removed) nodes, namely φ , as control parameter. In the large Nlimit, φ=Na N=Z∞ ka dkP (k) = ka kmin 1−γ ,(7) where Na is the number of active nodes. From this equation, it follows that we can express SCMP as a function of φ by just replacing ka/kmin with φ1/(1−γ) . In particular, the behavior for large ka corresponds to the behavior for small fraction φ of active nodes. Defining φc as the threshold value at which a macroscopic CMPGC first appears, we expect that, close to the transition SCMP ∼(φ−φc)β,(8) where β is a characteristic exponent. In the case φc = 0, we expect SCMP ∼φβ∼kβ(1−γ) a,(9) 1 This object was called CMP giant component in Ref. [ 18 ]. We prefer to change denomination here to stress the difference between topologically connected components and CMP clusters. 4 that is, a decay of the CMPGC size as a function of ka. III. GENERAL SCALING THEORY FOR DEGREE-ORDERED CMP A. CMP for γ≤3 A simple observation allows us to characterize the behavior of SCMP on networks with 2 < γ ≤ 3. The shortrange counterpart, i.e. with r ( m ) = 1, of the CMP as defined above is called degree-ordered percolation (DOP). Its behavior on power-law distributed networks has been studied in Refs. [ 19 , 20 ], where a detailed investigation of the critical properties of the DOP giant component (DOPGC) can be found. In particular, it has been shown that: • for γ≤ 3 a DOPGC always exists for any finite value of ka; • for γ > 3, a DOPGC exists only up to a finite critical point (ka)DOP c. From this result we can infer that for γ≤ 3 a CMPGC always exists for every value of ka . Indeed, since the DOPGC is always a subset of the CMPGC, it follows that SDOP ≤SCMP for every ka , and since the short-range model has an infinite critical point, so has the long-range model. Furthermore, essentially all active nodes belong to the DOPGC [18] and thus SCMP ≃ka kmin 1−γ .(10) Notice that this result is valid in full generality as long as r ( m ) is a non-decreasing function. Instead, for γ > 3 the DOP has a transition to a phase with no giant component at ( ka ) DOP c and this does not allow us to draw any conclusions a priori on SCMP for large ka . In the following section, we develop a general scaling theory to understand the behavior of SCMP for γ > 3. B. CMP for γ > 3 Following [ 18 ], we identify two different mechanisms that may contribute to the formation of a CMPGC: A: Extended DOP mechanism: it is essentially an extension of the DOP process involving the merging of DOP clusters separated by distances larger than 1; B: Merging of distant isolated nodes: it works for high values of ka when essentially all active nodes are isolated and, on average, at large distance from each other. We compute the scaling of the order parameter SCMP with ka due to each mechanism separately, and we identify the ranges of ka values where one of them dominates over the other. 1. Extended DOP mechanism In the DOP model for γ > 3 there is an extensive giant cluster for ka up to ( ka ) DOP c . Above this threshold no DOP cluster is extensive. In the CMP model, due to the interaction range extending beyond 1, DOP clusters may merge and this may lead to the formation of a CMPGC even for ka> ( ka ) DOP c . The most natural candidates for this merging are small clusters at distance 2 from each other or massive isolated nodes at distance 2 from small clusters. We consider these two contributions separately. If two small clusters are topologically isolated but at distance 2 from each other, the two clusters merge provided their interaction range is larger than their relative distance. The merging of small clusters at distance 2 may then make possible the merging of other, more distant small clusters and so on. Assuming that in this way all NNI topologically nonisolated nodes enter the CMPGC, this mechanism gives a largest cluster of size (see Ref. [ 18 ] for details) NNI N≃ka kmin 1−γ"γ−1 γ−2kmin ka kmin 3−γ# =hkika kmin 2(2−γ) .(11) The plausibility of this assumption strongly depends on the shape of the function f ( x ) in Eq. (5) and on the value of ka . If f ( x ) grows as x or faster, a cluster of two nodes has by definition an interaction range equal at least to 2. Hence such a cluster can merge if at distance 2 from another cluster. If instead f ( x ) grows more slowly the interaction range of a cluster formed by two adjacent nodes may be smaller than 2, and the extended DOP mechanism becomes ineffective. In such a case Eq. (11) is a rough overestimation of the largest cluster size. In addition, for small ka there are many active nodes and it is plausible that distances among connected clusters are small. For large ka instead, clusters will tend to be at larger distances from each other, and an interaction range equal to 2 will not be sufficient to guarantee the merging. In a similar way, we can argue that also an isolated node can merge with a DOP cluster at distance 2 from it, if it is massive enough so that its interaction range is at least 2. If we define ke the value of k such that r ( ke ) = 2, and assume that all isolated nodes with degree k≥ke become in this way part of the CMPGC, we can estimate SCMP as the fraction of isolated nodes with k≥ke . Following [ 18 ], considering that ke is proportional to ka , and taking the 5 limit kakmin, we have [18] Nr≥2 N∼ke kmin 1−γ1−γ−1 γ−2 ke kc,(12) an expression that is also a clear overestimate of the true contribution, getting worse for large ka. Summing up the two contributions we obtain S(1) CMP ≃NNI N+Nr≥2 N.(13) Since the decay of Nr≥2/N with ka is slower than the decay of NNI/N , the first term in Eq. (13) dominates, in principle, only up to a crossover scale k∗ 1 , which depends on γ and on the detailed functional form of the interaction range. However, as noticed in [ 18 ], one does not expect to actually observe such a crossover as for asymptotically large ka this mechanism cannot be active. Indeed, for small values of ka (many active nodes), distances between small clusters are typically small, favoring the merging process. As ka is increased, in particular beyond ( ka ) DOP c , typical distances between active nodes grow larger and the extended DOP mechanism is strongly suppressed. Therefore, we can assume the contribution of the extended DOP mechanism to the size of the CMPGC to be S(1) CMP ≃ hkika kmin 2(2−γ) (14) up to a finite value of ka. 2. Merging of distant isolated nodes An additional mechanism, which can be at work for arbitrarily large ka , involves the formation of clusters resulting from the cumulative merging of massive distant nodes, with no role played by topologically connected clusters. The average distance between a node of degree k and its closest node with degree at least k is given by [ 18 ] d(k)≃1 + a(γ) ln k kmin ,(15) where a(γ) = γ−3 ln(κ)(16) and κ = k2/hki − 1 is the network branching factor. If r ( k ) ≥d ( k ), these two nodes merge in a single CMP cluster. For this reason, if r ( k ) grows with k faster than d ( k ), all nodes with a degree larger than kx , where kx is the solution of the equation r(kx) = d(kx),(17) will be part of the same CMP cluster and S(2) CMP =Z∞ kx dkP (k) = kx(ka) kmin 1−γ .(18) Notice that, since r ( m ) depends on ka , also kx is a function of ka. If instead r ( k ) grows, for large k , more slowly than d ( k ) then isolated massive nodes are too far away from each other and this mechanism does not activate. In such a case, since no mechanism is active for diverging ka , the CMP threshold is necessarily finite. 3. Crossover between the two mechanisms If Eq. (17) has a solution then the CMP asymptotic regime for large ka is described by Eq. (18) . As we will see in specific examples below, the asymptotic behavior may be preceded by an interval of ka values where the extended DOP mechanism dominates. In such a case the asymptotic regime is reached after a crossover at a degree value k∗ 2given by the solution of the equation S(1) CMP(k∗ 2) = S(2) CMP(k∗ 2).(19) Notice that, since Eq. (14) is an overestimate of the first contribution due to the extended DOP mechanism, the solution of Eq. (19) is actually an upper bound of the true crossover scale k∗ 2. The picture presented above is valid in networks of infinite size. In numerical simulations on finite networks the asymptotic regime can be actually observed for large kaonly if the system is large enough that the maximum degree kmax ( N ) is much larger than k∗ 2 . For random graphs with γ > 3, generated using the Uncorrelated Configuration Model (UCM) [ 21 ], the maximum degree scales with N as kmax ∼N1/(γ−1) . Hence, to observe the asymptotic regime it is necessary that NN∗ 2 , where N∗ 2 = k∗(γ−1) 2 . For the particular form of r ( m ) describing SIS epidemic dynamics this value is much larger than the sizes that can be simulated; as a consequence in Ref. [ 18 ] only the preasymptotic extended DOP regime was observed. We will see below that for various forms of the function r ( m ) the truly asymptotic regime can be cleanly observed in simulations. The finite size of networks considered in simulations induces also the presence of a size-dependent effective threshold ( ka ) CMP c ( N ) even if there is no threshold in the limit of infinite network size. This must be kept in mind when interpreting simulation results. See Appendix A for details. IV. RESULTS FOR TWO SPECIFIC FORMS OF THE INTERACTION RANGE In this Section we analyze in detail what happens for two specific choices of the functional dependence of the interaction range r ( m ) on the mass. In each case, after deriving the predictions of the scaling theory we compare them with the results of numerical simulations of the CMP process. These were performed by considering random 6 networks built according to the UCM algorithm [ 21 ] with minimum degree kmin = 3 and various sizes N . To avoid the strong sample-to-sample fluctuations in the value of the maximum degree [ 22 ] we extracted the degree distribution imposing the degrees to be strictly constrained between kmin and N1/(γ−1). A. Algebraically growing interaction range In this subsection we consider an interaction range growing algebraically with the cluster mass r(m) = m kaα ,(20) where α > 0 is a fixed parameter. The case α = 1 corresponds to the linear case studied in Ref. [18]. The effectiveness of the extended DOP mechanism strongly depends on the value of α . For α≥ 1 a cluster of size 2 has an interaction range at least equal to 2 and it can merge with another cluster if at distance 2 from it. Moreover, also isolated nodes with k > ke = 2 1/αka and distance equal to 2 merge with DOP clusters. Instead if α < 1 the above statements are no longer true, and only sufficiently massive clusters or isolated nodes at distance 2 may participate to merging events. In such a case Eq. (13) is an overestimation of the size of the CMP largest cluster. Concerning the second mechanism, since r ( m ) grows algebraically, and the average distance grows logarithmically, the interaction range is, asymptotically, always larger than the distance. Hence the equation r ( kx ) = d ( kx ) always has a solution, and the second mechanism is active for sufficiently large degrees, no matter the value of α . Setting kx = ωka , from Eq. (17) we have the transcendental equation ωα= 1 + a(γ) ln (ω) + ln ka kmin (21) which can be solved for ωas (see Appendix B) ω(ka) = e−1 a(γ) ka/kmin exp "−1 αWj −αe−α a(γ) a(γ)ka kmin −α!#, (22) where Wj ( z ) is the Lambert W or product logarithm function [ 23 ]. The branch corresponding to the physical solution is the one with j = − 1, since the branch with j = 0 implies ω→ 0 as ka→ ∞ , in contradiction with the requirement that kx≥ka . Expanding W−1 ( z ) for small argument (that is for kakmin ), we get, see Appendix B, ω≃1 + a(γ) αln a(γ) α+a(γ) ln ka kmin 1/α .(23) Thus we end up, neglecting constants and terms of lower order, with a CMPGC of size S(2) CMP ∼a(γ) ln ka kmin (1−γ)/α ka kmin 1−γ .(24) Eq. (24) is in agreement with the results in [ 18 ], which are recovered setting α = 1. We see that the introduction of an exponent α tuning the interaction range does not change the critical exponent β = 1, but only modifies logarithmic corrections. To calculate the crossover degree k∗ 2 , inserting Eq. (14) and Eq. (18) , evaluated for ka = k∗ 2 into Eq. (19) we obtain, after some transformations, k∗ 2=kmin ¯ω1−γ hki1 3−γ ,(25) where ¯ωis the solution of ¯ω=1 + 1 ln(κ)ln hki+b(γ) ln (¯ω)1/α ,(26) where we have defined b(γ) = 2(γ−2) γ−3a(γ) = 2(γ−2) ln(κ).(27) The equation for ¯ω can be solved analytically by using the Lambert W function with the same strategy developed in Appendix B. Alternatively, we can solve numerically Eq. (26) as a fixed point equation for ¯ω , and then insert this value in Eq. (25) . Fig. 2 shows that the minimum graph size N∗ 2 needed to observe the second mechanism at work is indeed much beyond values that can be considered in practice when α≤ 1, while it attains feasible values for α > 1 and γclose to 4. Numerical simulations of the CMP process (see Fig. 3) confirm the analytical predictions. For α = 0 . 5 and γ = 3 . 7 the crossover to the asymptotic behavior happens at N∗ 2∼ 10 25 ( k∗ 2 is of the order of 10 10 ). We thus have only access to the first regime, dominated by the extended DOP mechanism. Indeed, as predicted by Eq. (14) , the order parameter S decays with an exponent 2(2 −γ ) that extends well beyond the DOP threshold. For α = 5 and γ = 4 instead the crossover value is predicted to be k∗ 2≈ 23. Correspondingly we observe, for NN∗ 2≈ 10 4 , the asymptotic decay to be well described by Eq. (24) . Notice that in this case also the logarithmic correction is necessary to match the decay. B. Logarithmically growing interaction range Another interesting class of CMP processes is the one described by an interaction range growing logarithmically with the mass, that is r(m) = 1 + δln m ka,(28) 7 100 102 104 106 108 1010 1012 1014 3 3.5 4 4.5 5 5.5 6 6.5 7 (a) k∗ 2 γ α= 0.5 α= 1.0 α= 2.0 α= 5.0 100 105 1010 1015 1020 1025 1030 3 3.5 4 4.5 5 5.5 6 6.5 7 (b) N∗ 2 γ α= 0.5 α= 1.0 α= 2.0 α= 5.0 FIG. 2. Analytical results for algebraically growing interaction range. Plot of k∗ 2 (a) and N∗ 2 (b) as a function of γ for algebraically growing interaction range and several values of α. where δ > 0 is a parameter tuning how fast the range increases. In this case, since the interaction range grows only logarithmically with the cluster mass, the asymptotic ineffectiveness of the extended DOP mechanism is expected to be even more severe than in the previous case for α < 1. Concerning the merging of massive isolated distant nodes, since in this case both r ( m ) and d ( k ) grow logarithmically, it is not always true that a degree kx exists such that r(k)≥d(k) for k≥kx. This condition holds when δln k ka≥a(γ) ln k ka+a(γ) ln ka kmin .(29) This implies that kxexists only if δ > a(γ).(30) This result indicates a completely different phenomenology from the one found in Section IV A. The critical line δ = a ( γ ) divides the ( δ, γ ) plane in two regions (see Fig. 4): For δ > a ( γ ), the mechanism responsible for the merging 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 (ka)DOP c 101102 (a) SGC ka N= 104 N= 105 N= 106 N= 107 DOP, N= 107 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 k∗ 2 101102 (b) SCMP ka N= 104 N= 105 N= 106 N= 107 FIG. 3. Comparison of analytical and simulation results for the size of the CMP largest cluster as a function of ka , for algebraically growing interaction range and different combinations of γ and α values: (a) γ = 3 . 7 and α = 0 . 5; (b) γ = 4 and α = 5. The red dashed line is the scaling with exponent 1 −γ , the green dot-dashed line is the scaling with exponent 2(2 −γ ) and the blue dashed line is the prediction of S(2) CMP given by Eq. (18) where kx = ωka and ω is given by Eq. (22) . In panel (a) we also report the results of a simulation of the DOP process on the network with size N= 107. of distant isolated nodes of large degree is active for large ka ; below δ = a ( γ ) instead, the interaction range grows too slowly with respect to the average distance between nodes of degree k and hence the merging of all massive isolated nodes in a single CMP cluster does not occur. As a consequence, we can argue that for δ > a ( γ ) the CMP has an infinite threshold, while for δ < a ( γ ) the order parameter SCMP must go to zero at some finite critical value (ka)CMP c. In the region δ > a ( γ ), we can solve the equation for ω=kx/kaand compute the size S(2) CMP. We have δln(ω) = a(γ) ln(ω) + a(γ) ln ka kmin ,(31) 8 3 4 5 6 7 8 9 10 0 2 4 6 8 10 FIG. 4. Phase diagram of CMP with logarithmically growing interaction range in the ( δ, γ ) plane. In the shadowed region below the blue solid line, the second mechanism does not activate at all. In the region between the solid and dashed lines the second mechanism activates, but it is subleading compared to the first mechanism (as long as the first mechanism is at work). Above the dashed line the second mechanism activates and is leading with respect to the extended DOP mechanism. from which it follows kx=ωka=ka kmin a(γ)/[δ−a(γ)] ka.(32) Inserting the last expression into Eq. (18) S(2) CMP ≃ka kmin (1−γ)δ [δ−a(γ)] .(33) Hence we find that the critical exponent β=δ δ−a(γ)(34) (see Eq. (9) ) is a continuously changing function of the parameters γand δ. Also Eq. (19) for the crossover scale k∗ 2 can be exactly solved in this case. Inserting the expressions (14) and (33) into Eq. (19) and performing straighforward calculations we obtain k∗ 2=kminhkiµ(γ,δ),(35) where µ(γ, δ) = δ−a(γ) (γ−3) [δ−b(γ)].(36) See Fig. 5 for a plot of the function µ(γ, δ). The expression for k∗ 2 in Eq. (35) actually applies only for δ > b ( γ ). Indeed, as discussed above, for δ < a ( γ ) the merging of distant nodes is not active. Hence the CMP model is practically identical to DOP and we expect ( ka ) CMP c≈ ( ka ) DOP c . For a ( γ ) < δ < b ( γ ), instead, the second mechanism activates asymptotically but it is subleading with respect to the first. In this case the extended DOP mechanism dominates for small values of ka but, being asymptotically ineffective, at some point the second mechanism takes over. This crossover does not occur at the k∗ 2 predicted by Eq. (35) (which is smaller than kmin in this case) but where the extended DOP mechanism stops working. For δ > b ( γ ), we have at k∗ 2 a true crossover between the two mechanisms: The merging of distant isolated nodes governs the asymptotic behavior of SCMP . As we can see in Fig. 5, plotting k∗ 2 and N∗ 2 as a function of γ in the region δ > b ( γ ) shows that for small values of δ the crossover is largely out of reach in simulations; instead for larger values of δ , N∗ 2 is strongly reduced and hence it is possible to observe the asymptotic regime in simulations. Results of numerical simulations, reported in Fig. 6, confirm this overall picture. In Fig. 6(a), corresponding to δ < a ( γ ), the behavior of CMP practically coincides with that of DOP. For a ( γ ) < δ < b ( γ ), Fig. 6(b), the extended DOP mechanism dominates, up to a finite threshold. The true asymptotic behavior here is the one predicted by Eq. (33) , but it would be observed only for much larger system size N . For δ > b ( γ ) instead, SCMP nicely follows the asymptotic prediction of Eq. (33) , after the crossover scale. Finally, let us point out that the behavior of the CMP model as δ→a ( γ ) − is nontrivial. Let us consider a fixed value of γ . For δ = 0 the DOP process has a finite critical point ( ka ) DOP c . For δ > a ( γ ), we have instead an infinite critical point and a CMPGC always exists. What happens in the intermediate region? How does the finite critical point ( ka ) CMP c change in the region as a function of δ ? We know that ( ka ) CMP c→ ( ka ) DOP c as δ→ 0, but what happens for δ→a ( γ ) − ? As long as δ < a ( γ ) the merging of distant isolated nodes is not at work for large degrees. Hence the transition is governed by the extended DOP mechanism and occurs not far from the DOP critical point. As a consequence, we expect ( ka ) CMP c to be a discontinuous function of δ at fixed γ , jumping from a finite value to ∞ when δ reaches a ( γ ). A direct numerical verification of this conjecture is however impossible, due to finite-size effects. V. DISCUSSION AND CONCLUSIONS In this paper, extending the work of Refs. [ 11 , 18 ], we introduced a general formulation for a new class of percolation processes in networks, dubbed cumulative merging percolation (CMP), characterized by the fact that nodes belonging to a cluster need not be topologically connected. Clusters are instead defined via an iterative procedure that may merge network subsets even if they are far apart in the network. In this sense CMP is a long-range percolation process, qualitatively different 9 100 1010 1020 1030 1040 1050 3 3.2 3.4 3.6 3.8 4 (b) γ k∗ 2 N∗ 2 100 102 104 106 108 1010 4 6 8 10 12 (c) γ k∗ 2 N∗ 2 FIG. 5. Analytical results for logarithmically growing interaction range. (a) Three-dimensional representation of µ ( γ, δ ) of Eq. (36) . (b) Plot of k∗ 2 and N∗ 2 as a function of γ for δ = 2. (c) Plot of k∗ 2 and N∗ 2 as a function of γ for δ = 20. In both panels b) and c) the condition δ > b ( γ ) is verified. The red vertical lines represent the value of γ for which δ = b ( γ ) and thus k∗ 2and N∗ 2diverge. from extended-neighborhood processes, which have only a finite interaction range. We then considered a specific subclass of CMP models, characterized by node masses equal to node degrees and a degree-ordered activation of nodes. This class generalizes the CMP model introduced in Ref. [ 18 ] by allowing for an arbitrary (non-decreasing) functional dependence r ( m ) of the interaction range on the cluster mass. Building on [ 18 ] we developed a scaling theory for this class of CMP models on power-law degreedistributed networks, which allows us to determine the 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 (ka)DOP c 101102 (a) SGC ka DOP δ= 0.3 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 101102 (b) SCMP ka N= 104 N= 105 N= 106 N= 107 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 k∗ 2 101102 (c) SCMP ka N= 104 N= 105 N= 106 N= 107 FIG. 6. Comparison of analytical and simulation results for the size of the CMP largest cluster as a function of ka , for logarithmically growing interaction range and different combinations of γ and α values: (a) γ = 3 . 7 and δ = 0 . 3, so that δ < a ( γ ), the system size is N = 10 7 ; (b) γ = 3 . 7 and δ = 1, so that a ( γ ) < δ < b ( γ ); (c) γ = 4 and δ = 20, so that δ > b ( γ ). The vertical dashed line in panel (c) is the value of k∗ 2 . The red dashed line is the scaling with exponent 1 −γ , the green dot-dashed line is the scaling with exponent 2(2 −γ ) and the blue dashed line is the prediction of S(2) CMP given in Eq. (33). behavior of the order parameter SCMP and the associated critical properties. We then considered two specific functional forms for r ( m ). We first focused on the case in which r ( m ) grows algebraically with m . We showed that a giant cluster (CMPGC) always exists for any value of ka (the control parameter that sets the degree threshold for node activation), even if the interaction range grows sublinearly,