Trend-driven information cascades
on random networks

Teruyoshi Kobayashi

August 2015
Discussion Paper No.1529

GRADUATE SCHOOL OF ECONOMICS
KOBE UNIVERSITYROKKO, KOBE, JAPANTrend-driven information cascades on random networks
Teruyoshi Kobayashi∗
Graduate School of Economics, Kobe University, 2-1 Rokkodai, Nada, Kobe 651-8501, Japan(Dated: August 5, 2015)
Threshold models of global cascades have been extensively used to model real-world collective
behavior, such as the contagious spread of fads and the adoption of new technologies. A common
property of those cascade models is that a vanishingly small seed fraction can spread to a finite
fraction of an infinitely large network through local infections. In social and economic networks,
however, individuals’ behavior is often influenced not only by what their direct neighbors are doing,but also by what the majority of people are doing as a trend. A trend affects individuals’ behavior
while individuals’ behavior creates a trend. To analyze such a complex interplay between local- andglobal-scale phenomena, I generalize the standard threshold model by introducing a new type ofnode, called global nodes (or trend followers), whose activation probability depends on a global-scale
trend; specifically the percentage of activated nodes in the population. The model shows that global
nodes play a role as accelerating cascades once a trend emerges while reducing the probability of atrend emerging. Global nodes thus either facilitate or inhibit cascades, suggesting that a moderateshare of trend followers may maximize the average size of cascades.
PACS numbers: 64.60.aq, 89.65.-s.

I.

INTRODUCTION

The mechanisms underlying various sorts of cascades
on complex networks have been extensively studied overthe past decade [1–10]. The threshold model of cascades
formalized by Watts [1], among others, has been widely
employed to describe not only information cascades onsocial networks [1, 10], but also default contagion in financial networks [11–14] and cascades on multiplex networks [15–17].
A common assumption implicitly made in the threshold models is that a node’s activation probability depends
only on local information: the state of neighbors. The
point of the Watts model is that a vanishingly small seedfraction can spread to a finite fraction of an infinitely
large network through local infections, suggesting that
individuals’ behavior at the local scale can add up to a
global-scale outcome.
In real-world social and economic networks, nodes (individuals, firms, banks, etc.) normally collect information not only from their direct neighbors, but also froma wide variety of media sources. Individual nodes caneasily access global-scale information (poll results, average prices, average loan rates, etc.) and use it in theirown decision-making (whom to vote for, whether to raiseor maintain prices, whether or not to change loan rates,etc.). This implies that a global-scale outcome affects individuals’ behavior while individuals’ behavior adds up
to a global-scale outcome. Thus, there arises a complex
interplay between local- and global-scale phenomena.
To analyze such an interplay in a formal way, I generalize the Watts’ threshold model by considering two types∗ kobayashi@econ.kobe-u.ac.jp

of nodes: local nodes (or trendsetters) and global nodes(or trend followers). The former are activated only by
local neighbors as in the standard model, while global
nodes are nodes whose states are dependent on a globalscale outcome. In the model, global nodes will be activated if a large enough fraction of the total number ofnodes are activated.
The main contribution of this paper is to show thatthe introduction of global nodes significantly changes themechanism of how a large-size cascade appears. Therearises a saddle-node bifurcation in the presence of global
nodes, and thereby a cusp catastrophe may occur. This
is intuitively because once the global nodes begin to be
activated, those activated nodes further activates the local nodes that are otherwise inactive, leading to a drastic
cascade. We call this type of drastic cascade the trenddriven cascade.
On the other hand, the global nodes may also inhibit
cascades, because they are never activated until the cascade size exceeds a certain threshold value. Thus, threephases may exist in the model: Phase I: no nodes areactivated (except for seed nodes); Phase II: only local
nodes may be activated; and Phase III: every node may
be activated. It is shown that the boundary between
Phase II and Phase III is well approximated by a root ofa fixed-point equation, while the extended cascade condition proposed by Gleeson and Cahalane [2] can still accurately detect the boundary between Phase I and Phases
II+III.
The analysis also reveals that the average size of cascades will be uniquely maximized near the boundary between Phase II and Phase III, where there are a medium
fraction of global nodes in the population. These results
suggest that the share of trend followers in the total population will be a key to understanding real-world collec-

2following recursion equations [2, 3]

tive behavior.

ρt+1 = (1 − µ)ρLt+1 + µρG
t+1 ,
II.

A GENERALIZED THRESHOLD MODELWITH TREND FOLLOWERSA.

F (m, k) ≡1 if mk > θL0 otherwise(1)

where m denotes the number of neighbors that are already active and θL ∈ (ρ0 , 1] is the threshold above which
local nodes are activated.
The response function for the global nodes (or trend
followers) is given by(2)

where ρ is the share of activated nodes in the population,and θG ∈ (ρ0 , 1] is the threshold value. The essential difference between the two types of response functions isthat F L (·) is a function of m/k, which is the share ofactivated nodes in a vanishingly small fraction of nodes(i.e., k/N approaches 0 as N goes to infinity), whereas
F G (·) is a function of the share of activated nodes in a
finite fraction of nodes. In this paper, we focus on a particular case in which the global nodes are activated if alarge enough fraction of the total population exceeds athreshold. Note that the value of ρ is global-scale information that is not identifiable from the states of local
neighbors. The accessibility to global-scale information
can be justified by assuming that each node has accessto media, such as web sites, TV news, newspapers, etc.
In numerical simulation, a global node is activated atstep t if the total share of activated nodes at step t −1 exceeds θG . The local and global nodes are selected
uniformly at random with probabilities 1 − µ and µ in
the baseline model.

B.

k
X

Treelike approximation for the average size ofcascadesA treelike approximation for the conditional size of cascades, denoted by ρ∞ , is given by a fixed point of thekBm(ρ̃t )F L (m, k),

(4)

m=0

(5)

k
where
the degree distribution and Bm(ρ̃t ) ≡ m pk denotes
k
k−m
L
G
ρ̃
(1
−
ρ̃
)
.
ρ
and
ρ
are
the
fractionof actt+1
t+1
m t
tive nodes at step t + 1 among local and global nodes,
respectively. Note that in Eq.(5), ρG
t+1 is determined independently of the degree distribution. This is because
global nodes are assumed to ignore local information
coming directly from their neighbors. ρ̃t is obtained as asolution to the following recursion equationsρ̃t = (1 − µ)ρ̃Lt + µρ̃Gt ,ρ̃Lt = ρ0 + (1 − ρ0 )(1 if ρ > θGF G (ρ) ≡0 otherwisepk

ρG
t+1 = ρ0 + (1 − ρ0 )F (ρt ),Two types of nodes

(

∞
X
k=0
G

We consider an undirected and unweighted networkthat consists of N number of nodes. The degree of eachnode is denoted by k. Each node is initially “inactive”,
except for the seed nodes that are originally “active” bydefinition. The seed nodes are selected uniformly at random with probability ρ0 . The response function for the
local nodes (or trendsetters) isLρLt+1 = ρ0 + (1 − ρ0 )

(3)

∞
X
k=1

(6)
k−1
X

kpk
B k−1 (ρ̃t−1 )F L (m, k),z m=0 m(7)Gρ̃Gt = ρt ,(8)

where z is the mean degree.
Thus, six variablesGLaredeterminedby six equaandρ̃ρt+1 , ρLt+1 , ρG
,
ρ̃
,
ρ̃
t
t
t
t+1
tions (3)-(8), taking ρ̃0 = ρL0 = ρG=ρasgiven. No00tice that ρ∞ may not be interpreted as the average sizeof cascades because the probability of a global cascade
occurring is not necessarily equal to 1. One should interpret ρ∞ as the size of the cascade, or equivalently as theprobability of a randomly selected node being activated,conditional on a cascade event.
As discussed by Gleeson [3] for the standard case ofµ = 0, ρ∞ becomes an accurate approximation for the average size of cascades if the initial seed fraction ρ0 is notvanishingly small, where the frequency of global cascades
will be sufficiently close to 1. If instead ρ0 is vanishingly
small, then we need to multiply ρ∞ by the probability
that a global cascade occurs. This is because there arises
a non-negligible possibility that all the seed nodes may
be located outside the extended vulnerable cluster [1, 3],
in which case the cascade probability will be less than
1. In the presence of global nodes, the size of the extended vulnerable cluster becomes smaller than that of
the conventional one since global nodes are “immune” tolocal infection. The frequency of global cascades can besignificantly lower than 1 even if ρ0 is not vanishingly
small.
The average size of the modified extended vulnerable
cluster S̃e is given as
S̃e =

∞
X

pk [1 − (1 − q̃∞ )k ],

(9)

k=0

q̃t = (1 − µ)

∞
X
kpk
k=1

z

[1 − (1 − q̃t−1 )k−1 ]F L (1, k). (10)3S ≈ ρ∞ [1 − (1 − S̃e )bρ0 N c ].

(a)

0

1

0.1

0.8

0.2
0.6

µ

Note that a global cascade occurs if and only if at least
one seed node belongs to the modified extended vulnerable cluster. The average size of cascades, denoted by S,
is approximated as

0.3
0.4

(11)

0.4
0.2

0.5

III.
A.

0.6

ANALYSIS

Cascade conditions

∞
X

kpk
ρ̃t = (1 − µ) ρ0 + (1 − ρ0 )
z
k=1

×

k−1
X


k−1
Bm
(ρ̃t−1 )F L (m, k) .

(12)

m=0

In fact, this recursion equation is the same as that obtained in a hypothetical model in which there were no
global agents and 100µ% of local nodes were randomly
removed. The cascade region that appears in the present
model also coincides with that of the hypothetical model,
which implies that it is only the local nodes that can initiate cascades. This irrelevancy of the global nodes stems
from the fact that the global nodes are totally unresponsive in the initial stage of contagion under the natural
assumption of limρt−1 ↓0 dρdt−1 F G (ρt−1 ) = 0. The cascadecondition in the presence of global nodes is the one thatindicates the parameter space within which a finite fraction of the local nodes can be activated.
Fig. 1 demonstrates that our analytical approximation matches reasonably well with simulations on ErdősRényi random networks. Fig. 1(a) compares the simulated value of S and the cascade conditions. It is known
that the first-order cascade condition (dashed line) is notvery accurate for a finite seed size [2, 3], but the extended
cascade condition (solid line) still correctly predicts theupper as well as the lower phase transition. If we set
ρ0 = µ = 0 in the first-order cascade condition, then it
predicts the cascade region shown in the original Watts
model [1].

1

2

3

4

5

6

7

8

mean degree
(b)

1

µ=0
µ = 0.2µ = 0.4µ = 0.5µ=0µ = 0.2µ = 0.4µ = 0.5

0.8
0.6
0.4
0.2
0

The parameter space within which a global cascade
may occur is called the cascade region, and the condition
that determines whether or not a global cascade may occur is called the cascade condition. The first-order cascade condition is a cascade condition with first-order accuracy while the extended cascade condition guarantees
second-order accuracy [2].
Appendix A shows the derivation of the first-order andextended cascade conditions. Note that although ourmodel is summarized as a system of two recursion equations, Eqs.(A1)-(A2), the only equation relevant to thecascade conditions is00ave. cascade size

The terms in the square brackets capture the (approximated) probability that at least one seed node belongs
to the modified extended vulnerable cluster.

0

1

2

3

4

5

6

7

8

mean degree
FIG. 1. (Color online) Percentage of global nodes in the population, µ, and average size of cascades on Erdős-Rényi networks. (a) Simulated average cascade size (color bar) andthe cascade conditions. Dashed and solid lines denote thefirst-order and extended cascade conditions, respectively. (b)Lines denote the theoretical average size of cascades, andmarkers plot simulated values. N = 105 , ρ0 = 10/N andθL = θG = .18, averaged over 103 random perturbations.

B.

Cascade region for trend-driven cascades

The commonality in the cascade regions between thepresent model and the hypothetical model with random
node removal is illustrated in Fig.2(a). The figure showsthat the conditional cascade size, ρ∞ , is identical in thetwo cases for ρ∞ < θG . For ρ∞ > θG , ρ∞ in thecurrent model becomes larger than that under the hypothetical model because the “removed” nodes will be
activated. Note that the size of ρ∞ in the presenceof global nodes increases discontinuously at ẑ, whereẑ ≡ inf{z : ρ∞ > θG }. This indicates that the parameter
space can be decomposed into three parts: Phases I, II
and III [Figs.2(b) and (c)]. Phase I is the region in which
no nodes are activated (except for the seed nodes). Phase
II is the cascade region within which only local nodes canbe activated, while every node may be activated in PhaseIII.
For Erdős-Rényi random graphs, an approximatedvalue of ẑ, denoted by z̃, is obtained as a solution to thefollowing root-finding problem obtained from Eq. (12)∞Xz̃ k−1 e−z̃
(1 − µ) ρ0 + (1 − ρ0 )(k − 1)!
k=1

×

k−1
X


k−1
Bm
(θG )F L (m, k) − θG = 0,

(13)

m=0

and subject to z̃ ∈ [z, z̄], where z and z̄ are the lower
and upper boundaries of the extended cascade region,
respectively. The upper boundary of Phase III is given

4
(a)

(a) 1

1

µ = 0.2µ = 0.4
20% random removal
40% random removal

ρ∞

0.6

0.8

0.6

C

ρ̃

0.4
0.4

0

0

cascade region
0

1

2

3

(b) 0.1

4

1

5

6

7

I

G

III

0.2

I

0.3

III

I

0.4

0.4

II

0.2

B 2

4

0

0

2

4

mean degree

6

0

2

1

0.8

0.8

0.6

0.6
0.4

µ = 0.4

0.2

0.5

6

µ = 0.6

(d) 1
0.8
0.6

ρ̃
0.4

0.4

0.2

0.2

0

0.4

4

z

8

0
0

2

4

6

0

2

4

6

z

z

II
0.5

0

6

ρ̃

0.6

θ

θG

I

0.3

0

(c) 1

µ = 0.4(c) 0.1

0.8

0.2

0.2

1 fixed pointzmean degreeµ = 0.2

0.4

0.2

θG

Phase III

0.2

0

0

2

4

6

mean degree

FIG. 2. (Color online) Trend-driven cascades. (a) Lines denote ρ∞ obtained from Eqs. (3)–(8), while markers plot thecorresponding value obtained in a model without global nodes
but 100µ% of nodes being removed at random. (b) and (c)Colors indicate the simulated S and red solid line denotes theextended cascade condition. Blue dash-dotted line denotes
an approximate lower boundary z̃ above which a trend-driven
cascade occurs. Roman numerals denote the phase of the region. N = 105 , ρ0 = 10/N , θL = .18, θG = .18 [in panel (a)],averaged over 103 random perturbations.

by z̄. Note that because ρ̃∞ and ρ∞ can generally differ, z̃
obtained by solving (13) is an approximated, rather thanthe correct, lower boundary of Phase III. Nevertheless,Figs.2(b) and (c) demonstrate that the so-defined z̃ nicely
matches the numerical lower edge.
C.

0.8

3 fixed points

0.6

µ

0.8

µ=0

(b) 1

1 fixed point

Bifurcation analysis and tricritical-point scaling

The presence of discontinuous transition can also be
confirmed by bifurcation diagram illustrated in Fig. 3. A
saddle-node bifurcation appears anywhere on the bifurcation curve depicted in the stability diagram [Fig. 3(a)].
Our particular interest is on cusp catastrophes that occur
when the parameter combination (z, µ) is on the bifurcation curve BC highlighted in pale red, which is called
the first-order line.
Given µ = 0.4, for example [Fig. 3(c)], the first phasetransition occurring at z ≈ 1.9 (from Phase I to PhaseII) is smooth, but the second transition (from Phase II
to Phase III) at z = 2.3(≈ z̃) is discontinuous. The
first-order line BC indicates the combination of (z, µ)
at which cusp catastrophes occur. Note that as long asµ > 0, the introduction of global nodes distinguishes thefirst smooth transition from the second discontinuous one
however small the value of µ is. Recently, Lee et al. [15]also show that a saddle-node bifurcation emerges in a
multiplex network when there is heterogeneity in the response functions.

FIG. 3. (Color online) Bifurcation diagram of the roots ρ̃∞ offixed-point equations (ρ̃∞ , ρ∞ ) − g(ρ̃∞ , ρ∞ ) = 0 [eqs. (A1)–(A2)]. (a) Stability diagram that distinguishes the parameter
space (z, µ) in terms of the number of fixed points. The firstorder line BC highlighted in pale red denotes a set of combination (z, µ) on which a trend-driven cascade (i.e., a cusp
catastrophe) occurs. Panels (b)–(d) Bifurcation diagram foralternative values of µ. Black solid and dashed lines denotestable and unstable fixed points, respectively. Red line is therealized stable root for cascades starting from the initial seedfraction ρ0 = 10−4 . θL = θG = .18.

Fig. 4 illustrates the boundary of the classical cascade
region, called the critical line, detected by finding the
local maxima of the number of iterations (NOI) in therecursion equations (A1)-(A2). It demonstrates that asz increases, the NOI decreases drastically when crossing
the critical line and the first-order line. Both lines passthrough the tricritical point T = (zt , µt ) = (3.14, 0.49)(subscript t stands for “tricritical”), where the NOI attains the global maximum [15]. The tricritical point T
and the cusp point C in Fig. 3(a) generally differ, but inthe present case they are very close.
The inset figure shows the scaling of the critical line in
the scaling fields (κz , κµ ) [15, 18–20], where κz is tangent
to the critical line at T and κµ is perpendicular to it. A
new coordinate system is given by the transformation


κz
κµ





cos θ̃ sin θ̃=− sin θ̃ cos θ̃z − zt,µ − µt(14)

where θ̃ = π + θ, and θ (< 0) is the angle of κz with thez-axis. In the new coordinate system, the critical line
near the origin is described bytκµ ∼ κ1/φ
,
z

(15)

where φt is called the crossover tricritical exponent. In
the baseline case we have 1/φt ≈ 2.0. The log-log plot
demonstrates that at a point slightly deviated from T,
the scaling does not follow Eq. (15).

50.6log(NOI)κ

0.5

first-order line
continuous
discontinuous

T

z

9
8
7

0.4

IV. EFFECT OF TREND-FOLLOWINGBEHAVIOR ON THE AVERAGE SIZE OFCASCADESA.

Two opposite roles of trend followers

κµ

µ

6

0.3

5
10-2

4

κµ

0.2
10-4

0.1

2.0
10-6
10-2

0

z = 3.11
z = 3.13
z = 3.14
z = 3.15
z = 3.16
10-1

B
1

3
2

100

κz
2

3

1

4

5

6

7

z
FIG. 4. (Color online) Scaling at the tricritical point T. NOI
denotes the number of iterations needed to ensure that thesuccessive iterates in the recursion equations (A1)-(A2) differ
by less than 10−10 . The critical line (or the cascade region)
is identified by the local maxima of the NOI. The critical line
and the first-order line (BT, pale red) pass through the tricritical point T = (3.14, 0.49), where the global maximum of
the NOI is attained. (Inset) Scaling of the critical line in a newcoordinate system (κz , κµ ) centered at a point on the criticalline. The log-log plot demonstrates that the critical line in
the new coordinate system centered at T (black squares) fits astraight line with slope 2.0 near the origin. To obtain the newcoordinate system, the numerical critical line is smoothed bya 7th-order polynomial function. θL = θG = .18.

Fig. 5 illustrates an example path of the cumulative
fraction of activated nodes. When z ∈ (ẑ, z̄), the number of activated nodes in the steady state can be larger
than that under µ = 0. The figure also shows that the
speed of convergence is decelerated by the introductionof global nodes that are never activated in the early stageof contagion.
It follows from the above results that the effect of introducing global nodes is twofold. First, cascades are
inhibited by the presence of global nodes. The cascade
region tends to shrink as the share of global nodes µ
increases, and the speed of contagion decelerates accordingly. Global nodes play a role as “immunized patients”
that prevent infectious diseases from spreading widely.
Fig.9 in Appendix A illustrates how the cascade region
shrinks with µ.
Second, the previous figures also demonstrate thatthe size of cascades may increase with µ, provided thatz ∈ (ẑ, z̄). An intuition is that once the total fraction ofactivated nodes exceeds θG , all the global nodes are activated regardless of their degree, meaning that a certain
proportion of nodes outside the largest connected component (LCC) can be activated. Recall that the size of
global cascades is usually constrained by the size of the
LCC when µ = 0 [1, 3].
In total, whether or not the introduction of global
nodes increases the cascade size depends on the relative
strength between the negative and positive effects.

1

frac. of active nodesµ = 0, θG = 0.18
µ = 0.3, θG = 0.08

0.8

µ = 0.3, θG = 0.18
random removal

0.6

B.

Optimal value of µ

0.4

1.
0.2

Maximizing the average cascade size

0.18
0.08

0

5

10

15

20

25

30

35

40

45

steps

FIG. 5. (Color online) Cumulative fraction of activated nodes
in a contagion simulation. A trend-driven cascade occurs
when the cumulative fraction exceeds θG . The path denoted“random removal” (red crosses) corresponds to the case inwhich µ = 0 but 30% of the local nodes are randomly removed. z = 2, N = 105 , ρ0 = 10/N and θL = .18.

Figure 6(a) illustrates how the average size of cascades S varies with µ, taking z as given. It shows that
S initially increases due to the positive effect describedabove, but after passing a critical value, the negative effect comes to dominate the positive one and S falls drastically. Thus, there exists a unique maximizer of S, which
we call the “optimal” value of µ, denoted by µ∗ . The caseof µ∗ > 0 would be of interest because that is the case inwhich the presence of trend followers facilitates cascades.
A similar discussion on the maximization of informationcascades is given by Nematzadeh et al. [5].
Although an analytical expression for µ∗ is difficult toobtain, we know that µ∗ is within the parameter spacethat attains Phase III. From Eq.(12), an approximated

6
(a)

0.6
0.4
0.2
0

0.1

0.2

0.3

0.4

0.5

∆ρ∞, |∆Ψ|z = 1.2
z = 1.5z = 2.5z = 1.2
z = 1.5z = 2.5

0.8

0

0.6

∆ρ∞: µ = 0.2

0.2|∆Ψ| : µ = 0.2∆ρ : µ = 0.4∞|∆Ψ| : µ = 0.4

0.1

0
0.2

µ

(b) 0.6

0.4

0.8

(b)

ρ0=10-4
ρ0=10

1.4

1.6

1.8

2
×10-4

µ* < .2µ* < .4

0.1

ρ0=5·10-5
ρ0 =10 -5

0.3

1.2

0.2

-4

ρ0=5·10-5

0.4

1

ρ0

ρ0=10-30µ = 0.2µ = 0.4-0.1

ρ0=10-5

-0.2

0.2

-0.3
0.2

0.4

0.1
0

0.6

ρ0=10-3

0.5

optimal µ

0.3

1

∆S

ave. cascade size

(a)

0.6

0.8

1

1.2

1.4

1.6

ρ0
1

2

3

4

mean degree

56FIG. 6. (Color online) Optimal value of µ. (a) Effect ofvarying µ on the average size of cascades. Vertical dottedlines denote µ̄ calculated by (16). Other lines and markers
show the theoretical and simulated values of S, respectively.
The maximum of S is pointed by arrow. (b) Optimal valueof µ under alternative seed sizes. Lines and markers denotetheoretical and numerical results, respectively. N = 105 , θL =
θG = .18 and ρ0 = 10−4 [for panel (a)], averaged over 103
random perturbations.

1.8

2
×10-4

FIG. 7. (Color online) Decomposition of ∆S. (a) Changes inρ∞ and Ψ caused by an increase in µ. Arrows indicate thepoints above which a rise in ρ∞ dominates the reduction inΨ, leading ∆S to be positive. (b) Change in the average sizeof cascades. θL = θG = .18, z = 2.5.

2.

Effect of varying the seed size

upper bound of µ∗ , denoted as µ̄, is given asµ̄ = max {0, µ̂},
∞
X

kpk
where µ̂ = 1 − θG ρ0 + (1 − ρ0 )
z
k=1

×

k−1
X

−1
k−1
Bm
(θG )F L (m, k) ,

(16)

m=0

taking the parameters other than µ as given. The dotted vertical lines in Fig.6(a) plot µ̄. Another interpretation of µ̄ is that it indicates the minimum fraction of
global nodes that is required to eliminate the possibilityof trend-driven cascades. A further increase of µ from µ̄will prevent any global cascades.
Figure 6(b) compares the theoretical and simulated
values of µ∗ . The theoretical value of µ∗ is computedby a greedy search. It shows that the accuracy of theoretical µ∗ gets worse as z increases. This is because thelarger the mean degree, the lesser the benefit of increasing µ, which would undermine the accuracy of the greedy
search in the presence of a finite-size problem. The average size of cascades is almost unchanged for z > 3 sincemost of the nodes belong to the LCC.

Fig.6(b) also states that ρ0 and µ∗ have a positive relationship. To understand this, recall that the incrementof S can be decomposed into two factors from the relation S = ρ∞ Ψ, where Ψ ≡ [1 − (1 − S̃e )bρ0 N c ]. A risein S stems from an increase either in ρ∞ or in Ψ or in
both. However, for a given µ, the size of ρ∞ is determined solely by the size of the LCC independently ofρ0 if ρ0  1. The only factor that the initial seed size
can affect is therefore Ψ, the (approximated) frequency
of cascades.

Fig. 7 illustrates the decomposition of an increment ofS, defined as ∆S ≡ S|µ=c −S|µ=0 for c ∈ [0, 1]. In the figure, we see that ∆ρ∞ ≡ ρ∞ |µ=c − ρ∞ |µ=0 is independentof ρ0 , while ∆Ψ ≡ Ψ|µ=c − Ψ|µ=0 (< 0) increases with ρ0
because the larger the initial seed fraction, the higher the
probability of a global cascade occurring. Suppose thatµ has increased from 0.2 to 0.4. This largely lowers Ψby shrinking the size of the extended vulnerable clusterS̃e , while increasing ρ∞ by activating more nodes locatedoutside the LCC. The former effect dominates the latterfor a small ρ0 , but if ρ0 is large enough, then the increasein ρ∞ would compensate for the reduction in Ψ, which
could make µ = 0.4 optimal.

7
TREND-DRIVEN CASCADES ONSCALE-FREE NETWORKS(a)degree

0

1
0.8

0.2

0.4

0.6
0.8

0.4

0.6

0.2

0

0

(c)

0

2

4

6

mean degree
random

0

1
0.8
0.6

0.4

0.4

0.6

0.2

2

4

6

mean degree

High-centrality global nodes will suppress
cascades

2

4

6

8

mean degree

0.2

0

0

8

0

Fig. 8(a) shows the simulated values of S and µ∗ when
global nodes are selected in ascending order with respect
to nodal degree. This means that the global nodes havefewer edges than the local nodes and hubs are categorized as local nodes. It turns out that a rise in µ largely
increases S, provided that the mean degree is moderate. This can be understood by noticing that a certain
fraction of the global nodes do not belong to the LCC,
meaning that they are “unreachable” if they are local
nodes.
Fig. 8(b) shows the case in which global nodes are selected in ascending order in terms of eigenvector centrality. The result is qualitatively similar to that shown in
Fig. 8(a), but µ∗ is slightly lower than that under the
degree-based strategy for a wide range of z. This may
be surprising given the fact that eigenvector centrality
is an effective measure in detecting the keystone nodes
in the LCC [24]. The main difference between the two
strategies is that some relatively high-degree nodes may
be selected as global nodes and thereby “immunized” inthe eigenvector-based strategy. Recall that contagion initially propagates among vulnerable nodes that have degrees lower than b1/θL c (= 5 in this experiment) and thenspread to higher-degree nodes within the LCC. The numerical results suggest that vulnerable local nodes withrelatively high degrees could play an important role inpromoting cascades to a level that would activate global
nodes.
On the other hand, the value of S monotonically decreases when global nodes are chosen uniformly at random [Fig. 8(c)]. This result is not obvious because theaverage degrees are almost identical between local andglobal nodes, which is the same situation considered in
the previous sections for Erdős-Rényi networks. Fig. 8(c)implies that the degree distribution itself is also an important factor in evaluating whether global nodes will
inhibit or facilitate cascades.
To summarize, when the network has a fat-tailed de-

0.6

0.4

0.8

0.8

B.

0.8

0.2

µ

Thus far, we have employed Erdős-Rényi random networks and assumed that the global nodes are selected
uniformly at random from all nodes. In this section we
consider scale-free networks and examine situations inwhich a fraction µ of nodes are selected as global nodes
in ascending order with respect to a centrality measure.
We employ random scale-free networks generated by thestatic model [21–23], where pk ∼ k −γ . To avoid degree correlation,√ the maximum degree is restricted to besmaller than N [22, 23].

0.4

1

0.2

0.6

µ

The static modelµA.

eigenvector

(b) 0

8

(d) 1
ave. cascade sizeV.

degreeeigenvector
random

0.8
0.6
0.4
0.2
0

0

0.5

1

µ

FIG. 8. (Color online) Optimal value of µ on scale-free networks generated by the static model. Panels (a), (b) and (c)show the simulated values of S (color bar) and µ∗ (markers).
Global nodes are selected in ascending order with respect todegree centrality [panel (a)] or eigenvector centrality [panel(b)]. In panel (c), global nodes are selected uniformly at random. Panel (d) plots the average size of cascades against µ.
N = 104 , θL = θG = .18, γ = 2.5, ρ0 = 10/N , z = 3 [in panel(d)], averaged over 104 random perturbations.

gree distribution, global nodes may still increase the average size of cascades if a large enough fraction of the global
nodes are low-centrality ones (in terms of degree centrality or eigenvector centrality). However, global nodes may
inhibit cascades if their centrality values are more diverse.

VI.

CONCLUSION AND DISCUSSION

In this work, I investigated an interplay between localand global-scale contagion by generalizing the standard
threshold model. In real-world social and economic networks, it is quite common that nodes respond to certain
information in diverse ways. For example, a retail firm
may raise prices if some of its wholesalers (i.e., neighbors)increase their prices while others may set prices with reference to the rate of inflation (i.e., a global-scale trend).
There is thus response heterogeneity among individuals,
a topic also discussed in Lee et al. [15]. Interestingly, although Lee et al. introduced response heterogeneity ina multiplex version of the threshold model, they show aproperty similar to one suggested in the present work; aglobal cascade may appear abruptly yet slowly.
Global cascade is not a phenomenon that appears inevery social and economic network on a regular basis,suggesting that many real-world networks are stable. According to the simple model presented here, the observed
stability of actual networks may be attributed to the

8
The first-order cascade condition is that the Jacobian matrix of function g(·), defined as (ρ̃t , ρt ) = g(ρ̃t−1 , ρt−1 ),has the largest eigenvalue larger than 1 at (0, 0) [2]. However, since limρt−1 ↓0 dρdt−1 F G (ρt−1 ) = 0, the Jacobian
has rank one, meaning that the trace is the only nonzero
eigenvalue. Therefore, the first term in Eq.(A1) is the
only relevant equation for the cascade condition.

0.3
0.28

µ=0
0.26
0.24

µ=0.2

θL

0.22

The first-order cascade condition is given as

0.2
0.18

µ=0.4

b1/θL c(1 − µ)(1 − ρ0 )

0.16

X kpk
(k − 1) > 1,
z

(A3)

k=1

0.14

µ=0.6

0.12
0.1

0

1

2

3

4

5

6

7

8

mean degree
FIG. 9. (Color online) Extended cascade conditions under alternative values of µ. Cascade region in the absence of global
nodes (µ = 0) is painted in red. The dark-red solid (µ = .2),
green dash-dotted (µ = .4) and blue dotted (µ = .6) lines respectively indicate the outer boundary of the corresponding
cascade region. θG = .18, ρ0 = 10−4 .

presence of trend followers who are activated only whena large enough fraction of the total population are activated. The present model explains why cascades are
not very frequent in real-world networks, as well as whylarge cascades may appear abruptly. I hope this work
will contribute to a better understanding of the interplay
between local and global phenomena that could play a
crucial role in the mechanism of collective behavior.

The irrelevancy of F G (·) near the origin also allows us
to borrow the extended cascade condition proposed byGleeson and Cahalane [2]. The extended cascade condition is given as b2 − 4ac < 0, where a, b and c are thecoefficients in the second-order approximation of Eq.(A1)which is of the form aq̃ 2 + bq̃ + c = 0. In the presence ofparameter µ > 0, the extended cascade condition leadsto (to first order in ρ0 )[(1 − 2ρ0 )C12 − 4C2 (ρ0 + C0 − 2C0 ρ0 )](1 − µ)2− 2C1 (1 − ρ0 )(1 − µ) + 1 < 0,
(A4)

or Eq. (A3), where

k−1
∞
X
kpk X
k=1

z

k−1
Bm
(ρ̃)F L (m, k)

m=0= C0 + C1 ρ̃ + C2 ρ̃2 ,ACKNOWLEDGEMENTS

Financial supports from the Japan Society for the Promotion of Science KAKENHI 25780203, 15H01948 and
15H05729 are gratefully acknowledged.

and

Cl =

Appendix A: Cascade condition

(A5)

 
∞
l 
X
X
k −1
l
k=l+1 m=0lm(−1)l+m

kpk L
F (m, k).
z
(A6)

To obtain the cascade condition, we reorganize Eqs.(3)- (8) as the following two recursion equations that involve
two variables, ρ̃t and ρt :
∞
X

k−1
X

kpk
B k−1 (ρ̃t−1 )z m=0 mk=1
L× F (m, k) + µ ρ0 + (1 − ρ0 )F G (ρt−1 ) ,(A1)ρ̃t = (1 − µ) ρ0 + (1 − ρ0 )

∞
k
X
X

k
ρt = (1 − µ) ρ0 + (1 − ρ0 )pkBm
(ρ̃t−1 )k=0

REFERENCES

m=0




× F L (m, k) + µ ρ0 + (1 − ρ0 )F G (ρt−1 ) ,Fig.9 illustrates the cascade region indicated by the extended cascade condition.

(A2)

9

[1] Duncan J. Watts. A simple model of global cascades on
random networks. Proceedings of the National Academyof Sciences, 99(9):5766–5771, 2002. URL: http://www.
pnas.org/content/99/9/5766.abstract, doi:10.1073/
pnas.082090499.
[2] JP Gleeson and DJ Cahalane. Seed size strongly affects cascades on random networks. Physical Review E,
75(5):56103, 2007. doi:10.1103/PhysRevE.75.056103.
[3] James P. Gleeson. Cascades on correlated and modular
random networks. Physical Review E, 77(4):46117, 2008.
doi:10.1103/PhysRevE.77.046117.
[4] Sergey Melnik, Jonathan A Ward, James P Gleeson, andMason A Porter. Multi-stage complex contagions. Chaos,23(1):013124, 2013. doi:10.1063/1.4790836.
[5] Azadeh Nematzadeh, Emilio Ferrara, Alessandro Flammini, and Yong-Yeol Ahn. Optimal network modularity for information diffusion. Physical Review Letters,
113:088701, Aug 2014. URL: http://link.aps.org/
doi/10.1103/PhysRevLett.113.088701, doi:10.1103/
PhysRevLett.113.088701.
[6] R R Liu, W X Wang, Y C Lai, and B H Wang. Cascading dynamics on random networks: Crossover in phasetransition. Physical Review E, (85):026110, 2012. doi:
10.1103/PhysRevE.85.026110.
[7] Joshua Payne, Peter Dodds, and Margaret Eppstein.
Information cascades on degree-correlated random networks. Physical Review E, 80(2), August 2009. doi:
10.1103/PhysRevE.80.026125.
[8] Joshua Payne, Kameron Harris, and Peter Dodds. Exact
solutions for social and biological contagion models on
mixed directed and undirected, degree-correlated random
networks. Physical Review E, 84(1), July 2011. doi:
10.1103/PhysRevE.84.016110.
[9] D Centola, V Eguı́luz, and M W Macy. Cascade dynamics of complex propagation. Physica A, 374(1):449–456,
January 2007. doi:doi:10.1016/j.physa.2006.06.018.
[10] Duncan J Watts and Peter Sheridan Dodds. Influentials, networks, and public opinion formation. Journal of Consumer Research, 34(4):441–458, 2007. doi:
10.1086/518527.
[11] P Gai and S Kapadia. Contagion in financial networks.
Proceedings of the Royal Society A, 466:2401–2423, June
2010. doi:10.1098/rspa.2009.0410.
[12] P Gai, A Haldane, and S Kapadia. Complexity, concentration and contagion. Journal of Monetary Economics,
58:453–470, July 2011. doi:10.1016/j.jmoneco.2011.
05.005.
[13] Teruyoshi. Kobayashi. A model of financial contagion
with variable asset returns may be replaced with a simple
threshold model of cascades. Economics Letters, 124:113–
116, 2014. doi:10.1016/j.econlet.2014.05.003.

[14] Charles D. Brummitt and Teruyoshi Kobayashi. Cascades in multiplex financial networks with debts ofdifferent seniority.
Physical Review E, 91:062813,
Jun 2015.
URL: http://link.aps.org/doi/10.
1103/PhysRevE.91.062813, doi:10.1103/PhysRevE.91.
062813.
[15] Kyu-Min Lee, Charles D Brummitt, and K-I Goh.
Threshold cascades with response heterogeneity in multiplex networks. Physical Review E, 90(6), December 2014.
doi:10.1103/PhysRevE.90.062816.
[16] Osman Yağan and Virgil Gligor. Analysis of complex
contagions in random multiplex networks. Physical Review E, 86(3):036103, September 2012. doi:10.1103/
PhysRevE.86.036103.
[17] Charles D Brummitt, Kyu-Min Lee, and K-I Goh.
Multiplexity-facilitated cascades in networks. Physical Review E, 85:045102(R), April 2012. doi:10.1103/
PhysRevE.85.045102.
[18] Eberhard K. Riedel and Franz J. Wegner. Tricritical exponents and scaling fields. Physical Review Letters, 29:349–352, Aug 1972. URL: http://link.aps.
org/doi/10.1103/PhysRevLett.29.349, doi:10.1103/
PhysRevLett.29.349.
[19] Nuno A. M. Araújo, José S. Andrade, Robert M. Ziff,and Hans J. Herrmann. Tricritical point in explosive percolation. Physical Review Letters, 106:095703,
Mar 2011. URL: http://link.aps.org/doi/10.1103/
PhysRevLett.106.095703, doi:10.1103/PhysRevLett.
106.095703.
[20] Davide Cellai, Aonghus Lawlor, Kenneth A. Dawson, andJames P. Gleeson. Tricritical point in heterogeneous kcore percolation. Physical Review Letters, 107:175703,
Oct 2011. URL: http://link.aps.org/doi/10.1103/
PhysRevLett.107.175703, doi:10.1103/PhysRevLett.
107.175703.
[21] K-I Goh, B Kahng, and D Kim. Universal Behaviorof Load Distribution in Scale-Free Networks. PhysicalReview Letters, 87(27):278701, December 2001. doi:
10.1103/PhysRevLett.87.278701.
[22] M Catanzaro and R Pastor-Satorras. Analytic solution of a static scale-free network model. The European Physical Journal B, 44(2):241–248, April 2005.
doi:10.1140/epjb/e2005-00120-9.
[23] Michele Catanzaro, Marián Boguñá, and Romualdo
Pastor-Satorras. Generation of uncorrelated random
scale-free networks. Physical Review E, 71(2):027103,
February 2005. doi:10.1103/PhysRevE.71.027103.
[24] Juan G. Restrepo, Edward Ott, and Brian R. Hunt.
Weighted percolation on directed networks. Physical Review Letters, 100:058701, Feb 2008. URL: http://link.
aps.org/doi/10.1103/PhysRevLett.100.058701, doi:
10.1103/PhysRevLett.100.058701.