Physical Review. E
American Physical Society
image
Role of hubs in the synergistic spread of behavior
Volume: 99, Issue: 2
DOI 10.1103/PhysRevE.99.020301
  • PDF   
  • XML   
  •       

Table of Contents

Highlights

Notes

Abstract

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 pk∼k−α, we clarify how the dominance of hubs in social networks affects the conditions for MOTs. Our results show that, for α<4, an abundance of hubs drive MOTs, even if a synergistic spreading event requires an arbitrarily large number of adjacent spreaders. In particular, for 2<α<3, 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.

Baek, Chung, Ha, Jeong, and Kim: Role of hubs in the synergistic spread of behavior

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–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–9], weakened individuals [10–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–15], Poissonian random networks [6–8,10–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: 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 pkkα (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 thresholdn2, 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 n2. 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 k3 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 (S1), weakened (S2), infected (I), or removed (R). All nodes are initially S1, 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 S1 or S2 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 (n1)th attempt on the same S1 node, in which case the node becomes S2. 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).

(a) The GEP with n=3 on a five-node network. Each thick arrow represents a time step. (b) Examples of the transitions of r in the GEP with n=3 on the SFNs. Inset: a magnified view of the double phase transition for (α,μ)=(4.5,1). (c) The α dependence of the TCP (λc,μt) and (d) the scaling exponents in Table I. The SFNs in (b)–(d) have km=4.
FIG. 1.
(a) The GEP with n=3 on a five-node network. Each thick arrow represents a time step. (b) Examples of the transitions of r in the GEP with n=3 on the SFNs. Inset: a magnified view of the double phase transition for (α,μ)=(4.5,1). (c) The α dependence of the TCP (λc,μt) and (d) the scaling exponents in Table I. The SFNs in (b)–(d) have km=4.

Substrate. The GEP spreads on an ensemble of infinitely large random SFNs constrained by two conditions. First, the degree distribution obeys a power law pk=kα/ζα,km for kkm and α>2, where the generalized zeta function ζs,v, defined as the analytic continuation of i=vks for s1, normalizes the distribution. The assumed range of α ensures that the mean degree k=ζα1,km/ζα,km 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 Pελβc, rελβt, and rεμβt/ϕ with ελ(λλc)/λc and εμ(μμt)/μt.

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

λc=kk(k1)=ζα1,kmζα2,kmζα1,kmforα>30for2<α<3,
which lies between 0 and 1 for sufficiently large km. 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.
TABLE I.
Scaling exponents describing Pελβc, rελβt, and rεμβt/ϕ of the GEP on the random SFNs near a TCP.
 βcβtϕ
α>511212
4<α<511α3α4α3
3<α<41α314α
2<α<313α4α3α1α2

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 kmn2, which does not affect the main results. Then q satisfies a self-consistency equation q=f(q), where

f(q)1k=kmpkm=0k1k1m(1λ)min[m,n1]×(1μ)max[0,mn+1]qm(1q)k1mm=0k1.
Each summand indexed by m on the right-hand side accounts for the probability that the node has m nodes among k1 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 pkkpk/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
r=1k=kmpkm=0kkm(1λ)min[m,n1]×(1μ)max[0,mn+1]qm(1q)kmm=0k,
where pk appears instead of pk 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 km=4.

Conditions for MOTs. A MOT occurs at λ=λc when it coincides with a discontinuous jump of r. Since Eq. (3) implies rkλ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)

f(q)=ζα2,kmζα1,kmζα1,kmλq+ζα3,km3ζα2,km2ζα1,km+1g2,n(λ,μ)q2+Γ(2α)ζα1,kmgα2,n(λ,μ)qα2+O(qmin[3,α1]),
where Γ is the gamma function, and gs,n is defined as
gs,n(λ,μ)1λ1μn1μs+m=0n2m1sm×(1μ)m11μ1λn1m.
Here qj 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 lnq 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 of f¯limq0f(q). If f¯>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
gmin[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 km=4 satisfying this equation. The solvability of Eq. (6) has the following implications:

(i) If α>4, for n=2 the solution is μt=λc1λc, which depends on α only through λc. This is because the transition type is determined by the sign of q2 in Eq. (4), which is a two-neighbor effect. On the other hand, for n3 there is no solution because g2,n(λc,μt)=λc2<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 q2.

(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 n2, 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 km, can still be larger than 1 and thus impossible to achieve, as shown for km=4 in Fig. 1(c).

(iii) If 2<α<3, for any n2, μt=0 is the only solution. This captures limλ0r 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 k3 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 km=4 illustrated in Fig. 1(b). For α=3.5, both continuous and discontinuous transitions of r are possible at λc0.104 with the boundary at μt0.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 λc0.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

rq(ελ/|εμ|)βcif|εμ|ελϕ,εμ<0ελβtif|εμ|ελϕεμβt/ϕif|εμ|ελϕ,εμ>0,
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.

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

rP=limNRN=|εμ|(βt+βc)/ϕF±(ελ|εμ|1/ϕ),
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).
The near-TCP crossover behaviors for n=2 described by Eq. (8). The lines are obtained from the roots of Eq. (4), and the symbols are simulation results obtained using 105 SFNs with N=107 and km=4. The upper (lower) data correspond to the εμ<0 (εμ>0) regime with (a) α=4.5 and (b) α=3.5. See Fig. S2 [25] for the case α=5.5. To remove overlaps, all data for εμ<0 have been divided by 106. All plots use the same values of |εμ|.
FIG. 2.
The near-TCP crossover behaviors for n=2 described by Eq. (8). The lines are obtained from the roots of Eq. (4), and the symbols are simulation results obtained using 105 SFNs with N=107 and km=4. The upper (lower) data correspond to the εμ<0 (εμ>0) regime with (a) α=4.5 and (b) α=3.5. See Fig. S2 [25] for the case α=5.5. To remove overlaps, all data for εμ<0 have been divided by 106. All plots use the same values of |εμ|.

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

qdα,kmλ+μα21/(3α)
with a coefficient dα,km>0 determined by α and km, 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 ϕ=12α 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.
(a) Scaling behaviors of the cascade size r on the SFNs with α=2.5 and km=4. (b) Comparison between the asymptotic values of rP∞ (solid lines) predicted by the roots of Eq. (4) and the corresponding finite-size observable 〈R〉/N (symbols) numerically obtained from 105 networks with N=106. Both (a) and (b) use n=2 and the same values of μ. (c) Universal scaling form of q with respect to dα,kmλ+μα−2, as predicted by Eq. (9). The solid (dashed) lines correspond to λ=0 (μ=0).
FIG. 3.
(a) Scaling behaviors of the cascade size r on the SFNs with α=2.5 and km=4. (b) Comparison between the asymptotic values of rP (solid lines) predicted by the roots of Eq. (4) and the corresponding finite-size observable R/N (symbols) numerically obtained from 105 networks with N=106. Both (a) and (b) use n=2 and the same values of μ. (c) Universal scaling form of q with respect to dα,kmλ+μα2, as predicted by Eq. (9). The solid (dashed) lines correspond to λ=0 (μ=0).

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].

Acknowledgements

Acknowledgments. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) (KR) [Grants No. NRF-2017R1D1A3A03000578 (M.H.) and No. NRF-2017R1A2B3006930 (H.J.)]. Y.B. is supported in part by the European Research Council under the Horizon 2020 Programme, ERC Grant Agreement No. 740269. We also thank Peter Grassberger for helpful comments on mixed-order transitions in DNA unzipping as well as the references.

REFERENCES

[1] 

D. Poland and H. A. Scheraga, J. Chem. Phys.45, 1456 (1966).JCPSA60021-9606

[2] 

M. S. Causo, B. Coluzzi, and P. Grassberger, Phys. Rev. E62, 3958 (2000).1063-651X, doi: 10.1103/PhysRevE.62.3958

[3] 

Y. Kafri, D. Mukamel, and L. Peliti, Phys. Rev. Lett.85, 4988 (2000).PRLTAO0031-9007

[4] 

A. Bar and D. Mukamel, Phys. Rev. Lett.112, 015701 (2014);PRLTAO0031-9007

A. Bar and D. Mukamel, J. Stat. Mech. (2014) P110011742-5468, doi: 10.1088/1742-5468/2014/11/P11001

[5] 

N. Araújo, P. Grassberger, B. Kahng, K. J. Schrenk, and R. M. Ziff, Eur. Phys. J.: Spec. Top.223, 2307 (2014).1951-6355, doi: 10.1140/epjst/e2014-02266-y

[6] 

P. Grassberger, L. Chen, F. Ghanbarnejad, and W. Cai, Phys. Rev. E93, 042316 (2016).2470-0045, doi: 10.1103/PhysRevE.93.042316

[7] 

L. Chen, F. Ghanbarnejad, W. Cai, and P. Grassberger, Europhys. Lett.104, 50001 (2013).EULEEJ0295-5075

[8] 

W. Cai, L. Chen, F. Ghanbarnejad, and P. Grassberger, Nat. Phys.11, 936 (2015).1745-2473, doi: 10.1038/nphys3457

[9] 

P.-B. Cui, F. Colaiori, and C. Castellano, Phys. Rev. E96, 022301 (2017).2470-0045, doi: 10.1103/PhysRevE.96.022301

[10] 

K. Chung, Y. Baek, M. Ha, and H. Jeong, Phys. Rev. E93, 052304 (2016).2470-0045, doi: 10.1103/PhysRevE.93.052304

[11] 

D. Lee, W. Choi, J. Kertész, and B. Kahng, Sci. Rep.7, 5723 (2017).2045-2322, doi: 10.1038/s41598-017-06182-3

[12] 

W. Choi, D. Lee, and B. Kahng, Phys. Rev. E95, 022304 (2017);2470-0045, doi: 10.1103/PhysRevE.95.022304

W. Choi, D. Lee, and B. Kahng, Phys. Rev. E95, 062115 (2017);2470-0045, doi: 10.1103/PhysRevE.95.062115

W. Choi, D. Lee, J. Kertész, and B. Kahng, Phys. Rev. E98, 012311 (2018).2470-0045, doi: 10.1103/PhysRevE.98.012311

[13] 

G. Bizhani, M. Paczuski, and P. Grassberger, Phys. Rev. E86, 011128 (2012).PLEEE81539-3755

[14] 

P. Grassberger, Phys. Rev. Lett.120, 200605 (2018).PRLTAO0031-9007

[15] 

H.-K. Janssen, M. Müller, and O. Stenull, Phys. Rev. E70, 026114 (2004);PLEEE81539-3755

H.-K. Janssen and O. Stenull, Europhys. Lett.113, 26005 (2016);EULEEJ0295-5075

H.-K. Janssen and O. Stenull, J. Phys. A: Math. Theor.50, 324002 (2017).1751-8113, doi: 10.1088/1751-8121/aa7a2c

[16] 

K. Chung, Y. Baek, D. Kim, M. Ha, and H. Jeong, Phys. Rev. E89, 052811 (2014).PLEEE81539-3755

[17] 

B. Min and M. S. Miguel, Sci. Rep.8, 10422 (2018).2045-2322, doi: 10.1038/s41598-018-28615-3

[18] 

R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Rev. Mod. Phys.87, 925 (2015).RMPHAT0034-6861

[19] 

Rigorously speaking, a TCP is an end point of the coexistence line shared by three different phases. It is unclear whether the same is true for cooperative contagions, but we follow the casual definition of a TCP as a continuous transition point at the intersection between continuous and discontinuous transition lines.

[20] 

M. E. J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010).

[21] 

G. Bianconi and M. Marsili, J. Stat. Mech. (2005) P060051742-5468, doi: 10.1088/1742-5468/2005/06/P06005

[22] 

D. Centola, Science329, 1194 (2010).SCIEAS0036-8075

[23] 

G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E83, 051134 (2011).PLEEE81539-3755

[24] 

R. Cohen, D. ben-Avraham, and S. Havlin, Phys. Rev. E66, 036113 (2002).1063-651X, doi: 10.1103/PhysRevE.66.036113

[25] 

See Supplemental Material at http://link.aps.org/supplemental/10.1103/PhysRevE.99.020301 for additional details.

[26] 

Y. Baek and M. Ha (unpublished).

[27] 

D. Cellai, A. Lawlor, K. A. Dawson, and J. P. Gleeson, Phys. Rev. Lett.107, 175703 (2011).PRLTAO0031-9007

[28] 

N. A. M. Araújo, J. S. Andrade, Jr., R. M. Ziff, and H. J. Herrmann, Phys. Rev. Lett.106, 095703 (2011).PRLTAO0031-9007

https://www.researchpad.co/tools/openurl?pubtype=article&doi=10.1103/PhysRevE.99.020301&title=Role of hubs in the synergistic spread of behavior&author=Yongjoo Baek,Kihong Chung,Meesoon Ha,Hawoong Jeong,Daniel Kim,&keyword=&subject=Rapid Communications,Networks and Complex Systems,