key: cord-0010909-fx9ibkuf
authors: Baek, Yongjoo; Chung, Kihong; Ha, Meesoon; Jeong, Hawoong; Kim, Daniel
title: Role of hubs in the synergistic spread of behavior
date: 2019-02-25
journal: nan
DOI: 10.1103/physreve.99.020301
sha: d7cf4df78d4571d653777a96993e6f4e5b581ea8
doc_id: 10909
cord_uid: fx9ibkuf

The spread of behavior in a society has two major features: the synergy of multiple spreaders and the dominance of hubs. While strong synergy is known to induce mixed-order transitions (MOTs) at percolation, the effects of hubs on the phenomena are yet to be clarified. By analytically solving the generalized epidemic process on random scale-free networks with the power-law degree distribution [Formula: see text] , we clarify how the dominance of hubs in social networks affects the conditions for MOTs. Our results show that, for [Formula: see text] , an abundance of hubs drive MOTs, even if a synergistic spreading event requires an arbitrarily large number of adjacent spreaders. In particular, for [Formula: see text] , we find that a global cascade is possible even when only synergistic spreading events are allowed. These transition properties are substantially different from those of cooperative contagions, which are another class of synergistic cascading processes exhibiting MOTs.

Introduction. There has been a growing body of literature on mixed-order transitions (MOTs), which qualify as both continuous and discontinuous phase transitions depending on the chosen order parameter. Such transitions appear in many different contexts, such as DNA unzipping [1] [2] [3] , Ising spins with long-range interactions [4] , and various percolation models with biased merger of clusters [5] . A common aspect of these systems is the existence of long-range interactions which encourage global ordering over a finite fraction of the system at criticality [4] .

Recently added to the list are various models of cascades with synergistic spreading rules involving cooperation between different contagions [6] [7] [8] [9] , weakened individuals [10] [11] [12] [13] [14] [15] [16] , or multiple spreading thresholds [17] . If each transmission occurs independently without synergy, the cascade exhibits a continuous percolation transition [18] . In contrast, with sufficiently strong synergy, the transition can be a MOT: a continuous transition of the probability of a global cascade coincides with a discontinuous jump of the cascade size. Moreover, the lines of MOTs and purely continuous transitions join at a tricritical point (TCP) with its own critical properties [19] . Again, the long loops of the substrate, through which different spreading pathways cross each other, facilitate global cascades at the MOTs [8, 11] .

A natural question arises on how the conditions for MOTs depend on the structure of the underlying substrate. In homogeneous structures, such as lattices [6, 7, [13] [14] [15] , Poissonian random networks [6] [7] [8] [10] [11] [12] [13] 17] , and modular networks [16] , a MOT requires sufficiently strong synergy between two spreaders and dimension greater than two [13, 14] . However, cascades typically occur on heterogeneous structures: * These authors contributed equally to this work. † Corresponding author: msha@chosun.ac.kr for instance, social networks feature a significant fraction of highly connected individuals called hubs, whose existence is typically modeled by scale-free networks (SFNs) with a power-law distribution p k ∼ k −α (with α > 2) of the number of neighbors k (called degree) [20] . Since SFNs with a greater variance of k contain more loops [21] , α can be a major determinant of the conditions for MOTs. For cooperative contagions on SFNs, a heterogeneous mean-field approach [9] showed that a discontinuous jump of the cascade size is possible for α > 3 given sufficiently strong synergy, but not for 2 < α < 3; however, whether the same statement holds for general kinds of synergy remains to be clarified.

In this study, we show that the synergistic spread of behavior exhibits substantially different transition phenomena for small values of α. As empirically observed [22] , social reinforcement induces a large boost in the spread of a behavior if the target individual has sufficiently many adjacent spreaders. As a simple model incorporating this feature, we study the generalized epidemic process (GEP) with the synergy threshold n 2, in which the spreading probability changes when the number of spreading neighbors is greater than or equal to n, extending the original version limited to n = 2 [13] . In the sense that the cluster is formed by a mixture of single-node and multinode mechanisms, our model can be considered a cascading-process analog of the heterogeneous k-core percolation [23] , which is a pruning process. We analytically show that, for 2 < α < 4, an abundance of hubs enable MOTs for arbitrarily large n 2. In contrast to cooperative contagions, the cascade size exhibits a discontinuous jump even for 2 < α < 3 in a manner similar to the abrupt appearance of a giant heterogeneous k core with k 3 on the same SFNs [23] . While the near-TCP scaling exponents for α > 3 remain identical to those of cooperative contagions [9] , a new set of exponents can be identified for 2 < α < 3.

Dynamics. In the GEP, a node can be susceptible (S 1 ), weakened (S 2 ), infected (I), or removed (R). All nodes are initially S 1 , except for one randomly chosen I node (the "seed") starting the spread. At each time step, a random I node attempts to spread the behavior to all of its S 1 or S 2 neighbors, each of the former (latter) with probability λ (μ). Upon success, the target becomes I. A failed attempt does not affect the target unless it is the (n − 1)th attempt on the same S 1 node, in which case the node becomes S 2 . After then, the chosen I node immediately deactivates and becomes R, permanently removing itself from the dynamics. The process goes on until the network runs out of I nodes. The GEP with n = 3 on a five-node network is illustrated in Fig. 1(a) .

Substrate. The GEP spreads on an ensemble of infinitely large random SFNs constrained by two conditions. First, the degree distribution obeys a power law p k = k −α /ζ α,k m for k k m and α > 2, where the generalized zeta function ζ s,v , defined as the analytic continuation of ∞ i=v k −s for s = 1, normalizes the distribution. The assumed range of α ensures that the mean degree k = ζ α−1,k m /ζ α,k m is finite. Second, there is no correlation between the degrees of adjacent nodes. Given these two conditions, one may assume that a node and each of its neighbors have mutually independent statistics, which makes the problem analytically tractable.

Notations. The final fraction of R nodes, denoted by r, quantifies the cascade size. The probability of a global cascade with r > 0 is denoted by P ∞ . The percolation transition from the phase with zero r and P ∞ to the phase with positive r and P ∞ occurs at λ = λ c , and r exhibits a continuous (discontinuous) transition at the point if μ μ t (μ > μ t ). The scaling behaviors near the TCP (λ, μ) = (λ c , μ t ) are characterized by three exponents β c , β t , and φ, so that

Transition of P ∞ . For the SFNs defined above, multiple spreading pathways rarely cross at the same node unless the cascade has already reached a finite fraction of the network. For this reason, μ is completely irrelevant to the transition from P ∞ = 0 to P ∞ > 0: only λ controls the transition by a bond-percolation mechanism. Thus one can simply apply the theory of bond percolation on the random SFNs [24] to obtain the transition point

which lies between 0 and 1 for sufficiently large k m . The percolation theory [24] also shows that the transition can only be continuous with the universal scaling behavior P ∞ ∼ β c λ for small positive λ , where the α-dependent values of the critical exponent β c are listed in Table I . Such equivalence has also been noted for the GEP [10, 13] and cooperative contagions [6, 8, 11, 12] on homogeneous networks. Analytic calculation of r. In contrast to P ∞ , r depends on μ as the crossing of spreading pathways is nonnegligible whenever r > 0. Here we present a calculation of the dependence based on a standard tree ansatz for random SFNs [24] . For this aim, we consider the probability q that a node at an end of a randomly chosen link is R after the spread has stopped. For simplicity, we assume k m n − 2, which does not affect the main results. Then q satisfies a self-consistency equation 

Each summand indexed by m on the right-hand side accounts for the probability that the node has m nodes among k − 1 neighbors (excluding the neighbor at the other end of the randomly chosen link) trying to spread the behavior to it, all of which fail to do so. Note that p k ≡ k p k / k is the degree distribution of a node at the end of a path, weighted by k because higher-degree nodes are more likely to be connected. Once q is known, we can calculate r by

where p k appears instead of p k because all nodes have equal weights regardless of k in the definition of r. For any parameters, Eqs. (2) and (3) provide an exact, albeit implicit, solution for r. Examples are shown in Fig. 1(b) for the GEP with n = 3 on the SFNs with k m = 4.

A MOT occurs at λ = λ c when it coincides with a discontinuous jump of r. Since Eq. (3) implies r k λq, the transitions of r and q should be of the same type. The latter are encoded in the small-q expansion of Eq. (2), which for noninteger α is given by (see [25] for the detailed derivation)

where is the gamma function, and g s,n is defined as

Here q j with an integer j corresponds to the contribution from j neighbors, while q α−2 stems from the hubs. We note that the latter gets an extra factor of ln q for the special cases where α is an integer, which leads to some complications (see [25] for more details). The transition type is determined by whether q = f (q) has a positive root at λ = λ c , which in turn depends on the sign off ≡ lim q↓0 f (q). Iff > 0 (f < 0), a positive root exists (cannot exist), and the transition of r is discontinuous (continuous). Applying this criterion to Eq. (4), we find that the transition of r is discontinuous (continuous) if μ > μ t (μ < μ t ), where μ t ∈ [0, 1] is a solution of g min[2,α−2],n (λ c , μ t ) = 0

for any noninteger α > 2. In Fig. 1(c) , we show examples of λ c and μ t on the SFNs with k m = 4 satisfying this equation. The solvability of Eq. (6) has the following implications:

(i) If α > 4, for n = 2 the solution is μ t = λ c 1−λ c , which depends on α only through λ c . This is because the transition type is determined by the sign of q 2 in Eq. (4), which is a twoneighbor effect. On the other hand, for n 3 there is no solution because g 2,n (λ c , μ t ) = −λ 2 c < 0; in other words,f < 0 always holds, so the transition of r is always continuous. Here μ comes into play only for three-or-more neighboring spreaders, so it cannot affect the sign of q 2 .

(ii) If 3 < α < 4, Eq. (6) is explicitly dependent on α, reflecting the dominance of the hub-induced q α−2 term. Here the solution exists for any n 2, because the convergence of many spreading pathways at the hubs facilitates a MOT even if n is arbitrarily large. We note that μ t obtained from Eq. (6), depending on k m , can still be larger than 1 and thus impossible to achieve, as shown for k m = 4 in Fig. 1(c) .

(iii) If 2 < α < 3, for any n 2, μ t = 0 is the only solution. This captures lim λ↓0 r being positive (zero) for μ > 0 (μ = 0); in other words, there are so many spreading pathways crossing at the hubs that, regardless of n, synergistic spreading events by μ unaided by λ can induce a global cascade. This regime is where the cascades of the GEP differ most significantly from those of cooperative contagions [9] . In the latter, a node should first be infected by one contagion with probability λ to experience a secondary infection with probability μ, so r = 0 whenever λ = 0. In the GEP, even if λ = 0, a spreading event by μ can still occur because it only requires sufficiently many exposures to neighboring spreaders. This parallels the robust existence of a giant heterogeneous k core with k 3 on the same SFNs even in the limit where the fraction of removed nodes approaches unity [23] .

Based on these results, one can interpret the transition behaviors of the GEP with n = 3 on the SFNs with k m = 4 illustrated in Fig. 1(b) . For α = 3.5, both continuous and discontinuous transitions of r are possible at λ c ≈ 0.104 with the boundary at μ t ≈ 0.371, whereas for α = 4.5 (see the inset for a magnified view) r undergoes a continuous transition belonging to the bond percolation universality class (β c = 1) at λ c ≈ 0.203 even in the extreme case μ = 1. Notably, there is a secondary discontinuous transition (marked by dotted vertical lines) at λ > λ c , whose possibility is not excluded by our argument. This phenomenon seems to be related to the double phase transitions reported in [17] and will be discussed in detail elsewhere [26] .

Tricritical behaviors for α > 3. For small and positive λ , a Taylor expansion of Eq. (4) about (λ, μ) = (λ c , μ t ) yields

where μ ≡ (μ − μ t )/μ t , the exponents β c and β t are shown in Table I as well as Fig. 1(d) , and φ = 1 − β t /β c . The values of β t in this regime are in exact agreement with those reported in [9] . It is notable that the exponent φ, which governs the crossover between different scaling regimes, exhibits nonmonotonic behaviors with the slope changing sign at α = 4 [see Fig. 1(d) ]. This is yet another consequence of the fact that the hubs begin to drive the MOTs as α is decreased below 4. [25] for the case α = 5.5. To remove overlaps, all data for μ < 0 have been divided by 10 6 . All plots use the same values of | μ |.

To numerically verify the scaling exponents derived above, we present the scaling form for rP ∞ , which converges to the average fraction of R nodes, R /N, readily obtained using random SFNs of N nodes (see [25] for more details) in the N → ∞ limit. The scaling form is given by

where F + (F − ) is the scaling function for μ > 0 ( μ < 0). As shown in Fig. 2 , there is a good agreement between the theory and the numerics, despite deviations due to finite-size effects for small | λ | and | μ | (see Fig. S3 [25] for a closer comparison between theory and numerics). Scaling behaviors for 2 < α < 3. As discussed above and illustrated in Figs. 3(a) and 3(b) (the latter providing a numerical verification of the tree ansatz, whose rigorous justification remains an open mathematical problem due to a diverging number of short loops [21] ), λ c = μ t = 0 holds in this regime. Due to the absence of the phase of localized cascades, it would be misleading to call the point a TCP; however, one can still identify universal scaling behaviors and the crossover between them from the leading-order terms of Eq. (4), identifying new scaling exponents previously unreported. We obtain

with a coefficient d α,k m > 0 determined by α and k m , as illustrated in Fig. 3(c) . For μ = 0, the above equation and r ∼ λq from Eq. (3) implies r ∼ λ β t with β t = 4−α 3−α . Moreover, since the positive limiting values of q and r as λ decreases to zero become clear only for μ λ 1/(α−2) , we can also write φ = 1 2−α to describe the crossover. The behaviors of β t and φ for 2 < α < 3 shown in Table I and Fig. 1(c) should be understood in this vein.

Summary. We examined the effects of the degree exponent α on the percolation transitions of the GEP on uncorrelated random SFNs. All analytical results, based on the tree ansatz (2) , are in good agreement with the numerics beyond the regime of strong finite-size effects. It is found that the hub-driven MOTs occur only for α < 4. In particular, for 2 < α < 3, we identified new transition behaviors stemming from the convergence of loops at the hubs. These imply that the spread of behavior and cooperative contagions [9] belong to different universality classes on typical social networks. Our results reveal fundamental principles underlying the formation of compact cultural subgroups fostered by the fat-tailed degree distribution of social networks. Interesting topics for future studies include the conditions for double phase transitions, the nature of finite-size effects, and connections to MOTs and TCPs reported in other percolation models [27, 28] .

Rigorously speaking, a TCP is an end point of the coexistence line shared by three different phases

Networks: An Introduction

We also thank Peter Grassberger for helpful comments on mixed-order transitions in DNA unzipping as well as the references.