^{1,2,3}, Jonathan A. Ward

^{4}, James P. Gleeson

^{2}and Mason A. Porter

^{1,3}

### Abstract

The spread of ideas across a social network can be studied using complex contagion models, in which agents are activated by contact with multiple activated neighbors. The investigation of complex contagions can provide crucial insights into social influence and behavior-adoption cascades on networks. In this paper, we introduce a model of a multi-stage complex contagion on networks. Agents at different stages—which could, for example, represent differing levels of support for a social movement or differing levels of commitment to a certain product or idea—exert different amounts of influence on their neighbors. We demonstrate that the presence of even one additional stage introduces novel dynamical behavior, including interplay between multiple cascades, which cannot occur in single-stage contagion models. We find that cascades—and hence collective action—can be driven not only by high-stage influencers but also by low-stage influencers.

Studying models of cascades allows one to gain insights into a variety of processes ranging from the spread of fads and ideas in social networks to the appearance of cascading failures in infrastructure networks. To date, researchers have mostly considered single-stage cascade models wherein the propagation of a cascade is characterized by a single subpopulation of active agents,

^{1–5}though some multi-stage models have been examined recently.

^{6,7}In the usual approach, it is assumed that all active agents exhibit the same amount of influence on their peers. In reality, however, supporters of a cause can vary significantly in their desire and ability to recruit new members. In this paper, we introduce a model of multi-stage cascading dynamics in which agents can exert different amounts of influence on their peers depending on the stage of their adoption (i.e., on the level of their commitment to a certain idea or product). We investigate the dynamics of our multi-stage cascade model on various networks and observe an interplay between cascades—e.g., one cascade driving the other one or vice versa—that cannot be observed in single-stage cascade models. We also provide an analytical method for solving the model that gives a good prediction for the cascade sizes on configuration-model networks.

This work was funded in part by the Irish Research Council co-funded by Marie Curie Actions under FP7 (INSPIRE fellowship, S.M.), the Engineering and Physical Sciences Research Council (MOLTEN, EP/I016058/1, J.A.W.), Science Foundation Ireland (11/PI/1026, J.P.G.), the James S. McDonnell Foundation (Award #220020177, M.A.P.), and the European Commission FET-Proactive project PLEXMATH (FP7-ICT-2011-8, Grant No. 317614, M.A.P. and J.P.G.). Work by S.M. and M.A.P. was carried out in part at the Statistical and Applied Mathematical Sciences Institute in the Research Triangle Park, North Carolina. We thank Adam D'Angelo and Facebook for providing the Facebook data used in this study. We thank James Moody, Jukka-Pekka Onnela, Noah E. Friedkin, Mariano Beguerisse Díaz, and Sandra González-Bailón for reading and commenting on a draft of the paper. We also thank Peter Grindrod and Ben Williamson for useful comments and a referee for suggesting Fig. 8.

I. INTRODUCTION

II. MULTI-STAGE MODEL

III. THRESHOLD MODELS

A. Cascades driven by high influencers

B. Cascades driven by low influencers

IV. SYNTHETIC NETWORKS

V. ANALYSIS

VI. FINAL STATE AND TEMPORAL EVOLUTION OF CASCADES

VII. CASCADE CONDITION AND BIFURCATION ANALYSIS

VIII. CONCLUSIONS

### Key Topics

- Agent based models
- 12.0
- Social networks
- 7.0
- Bifurcations
- 6.0
- Numerical modeling
- 5.0
- Data analysis
- 2.0

## Figures

(a) Schematic of a single-stage complex contagion. All nodes can be either inactive (*S* _{0}) or active (*S* _{1}). Nodes that are barely above the *S* _{1}-threshold have the same level of influence as nodes that are strongly above that threshold. (b) Multi-stage complex contagion. A subset of active nodes (called “*S* _{1}-active”) can become *hyper-active* (called “*S* _{2}-active”) and have additional influence. Note that *S* _{2}-active nodes are necessarily also *S* _{1}-active.

(a) Schematic of a single-stage complex contagion. All nodes can be either inactive (*S* _{0}) or active (*S* _{1}). Nodes that are barely above the *S* _{1}-threshold have the same level of influence as nodes that are strongly above that threshold. (b) Multi-stage complex contagion. A subset of active nodes (called “*S* _{1}-active”) can become *hyper-active* (called “*S* _{2}-active”) and have additional influence. Note that *S* _{2}-active nodes are necessarily also *S* _{1}-active.

Comparison of single-stage [panel (a)] and multi-stage [panel (b)] cascade dynamics on the Oklahoma Facebook network. ^{ 56 } Time *t* is on the horizontal axis, and we indicate the fractions of nodes in each state on the vertical axis. Light blue, blue (and purple), and red regions represent *S* _{0}-, *S* _{1}-, and *S* _{2}-active nodes, respectively. In panel (a), ; and in panel (b), . The threshold parameter values are and . We use 348 *S* _{1}-active seed nodes (corresponding to ) and zero *S* _{2}-active seeds ( ). There is no cascade in panel (a), but some of the nodes (colored in purple) are well above the *S* _{1}-threshold. The bonus influence of *S* _{2}-active nodes drives a cascade in panel (b).

Comparison of single-stage [panel (a)] and multi-stage [panel (b)] cascade dynamics on the Oklahoma Facebook network. ^{ 56 } Time *t* is on the horizontal axis, and we indicate the fractions of nodes in each state on the vertical axis. Light blue, blue (and purple), and red regions represent *S* _{0}-, *S* _{1}-, and *S* _{2}-active nodes, respectively. In panel (a), ; and in panel (b), . The threshold parameter values are and . We use 348 *S* _{1}-active seed nodes (corresponding to ) and zero *S* _{2}-active seeds ( ). There is no cascade in panel (a), but some of the nodes (colored in purple) are well above the *S* _{1}-threshold. The bonus influence of *S* _{2}-active nodes drives a cascade in panel (b).

Comparison of single-stage [panel (a)] and multi-stage [panel (b)] cascade dynamics on the Oklahoma Facebook network. ^{ 56 } As in Fig. 2 , the time *t* is on the horizontal axis, and we indicate the fractions of nodes in each state on the vertical axis. Light blue, blue, and red regions represent *S* _{0}-, *S* _{1}-, and *S* _{2}-active nodes, respectively. We use 348 *S* _{2}-active seed nodes (corresponding to ) and . In panel (a), , so the *S* _{1} dynamics are slaved to the *S* _{2} dynamics. A small change in the threshold parameter ( ) in panel (b) yields a small number of additional *S* _{1}-active nodes, which are nevertheless enough to trigger a cascade.

Comparison of single-stage [panel (a)] and multi-stage [panel (b)] cascade dynamics on the Oklahoma Facebook network. ^{ 56 } As in Fig. 2 , the time *t* is on the horizontal axis, and we indicate the fractions of nodes in each state on the vertical axis. Light blue, blue, and red regions represent *S* _{0}-, *S* _{1}-, and *S* _{2}-active nodes, respectively. We use 348 *S* _{2}-active seed nodes (corresponding to ) and . In panel (a), , so the *S* _{1} dynamics are slaved to the *S* _{2} dynamics. A small change in the threshold parameter ( ) in panel (b) yields a small number of additional *S* _{1}-active nodes, which are nevertheless enough to trigger a cascade.

Demonstration of dynamics when an *S* _{2}-cascade drives an *S* _{1}-cascade. Panels (a) and (b) show the aggregate fractions of *S* _{1}- and *S* _{2}-active nodes, panels (c) and (d) show these fractions for each degree class separately, and panel (e) shows the fractions of nodes in each degree class that are *S* _{1}-active but not *S* _{2}-active. We show the numerical results (averaged over 100 realizations) using symbols and the analytical results given by Eqs. (2) and (3) using curves. The timescales are independent of network size *N*, which we take to be . The values of the other parameters are , and . (We choose seed nodes uniformly at random.) We use an upper threshold of to model the single-stage case.

Demonstration of dynamics when an *S* _{2}-cascade drives an *S* _{1}-cascade. Panels (a) and (b) show the aggregate fractions of *S* _{1}- and *S* _{2}-active nodes, panels (c) and (d) show these fractions for each degree class separately, and panel (e) shows the fractions of nodes in each degree class that are *S* _{1}-active but not *S* _{2}-active. We show the numerical results (averaged over 100 realizations) using symbols and the analytical results given by Eqs. (2) and (3) using curves. The timescales are independent of network size *N*, which we take to be . The values of the other parameters are , and . (We choose seed nodes uniformly at random.) We use an upper threshold of to model the single-stage case.

Demonstration of dynamics when an *S* _{1}-cascade drives an *S* _{2}-cascade. Panels (a) and (b) show the aggregate fractions of *S* _{1}- and *S* _{2}-active nodes, panels (c) and (d) show these fractions for each degree class separately, and panel (e) shows the fractions of nodes in each degree class that are *S* _{1}-active but not *S* _{2}-active. We show the numerical results (averaged over 100 realizations) using symbols and the analytical results given by Eqs. (2) and (3) using curves. The timescales are independent of network size *N*, which we take to be . We use the values for the single-stage case [panels (a) and (c)] and the values and for the multi-stage case [panels (b), (d), and (e)]. The values of the other parameters are and (where we choose the seed nodes uniformly at random).

Demonstration of dynamics when an *S* _{1}-cascade drives an *S* _{2}-cascade. Panels (a) and (b) show the aggregate fractions of *S* _{1}- and *S* _{2}-active nodes, panels (c) and (d) show these fractions for each degree class separately, and panel (e) shows the fractions of nodes in each degree class that are *S* _{1}-active but not *S* _{2}-active. We show the numerical results (averaged over 100 realizations) using symbols and the analytical results given by Eqs. (2) and (3) using curves. The timescales are independent of network size *N*, which we take to be . We use the values for the single-stage case [panels (a) and (c)] and the values and for the multi-stage case [panels (b), (d), and (e)]. The values of the other parameters are and (where we choose the seed nodes uniformly at random).

Comparison of numerical computations (symbols) with analytical predictions of Eqs. (2) and (3) (curves) for (a) the final fractions of *S* _{2}-active nodes as functions of the bonus influence β for ensembles of (4,5)-uncorrelated random networks (blue dashed-dotted curve) and Erdős-Rényi random graphs with mean degree *z* = 5 (black dashed curve) and (b,c) the temporal evolution of active fraction of nodes in each degree class in (4,5)-uncorrelated random networks for . In panel (a), we use the response functions of Eq. (1) with and uniform thresholds and . For the ER graphs, we also use a solid red curve to show the case in which the *R* _{2} thresholds are Gaussian-distributed with mean and standard deviation . The total number of nodes in each network is . For the numerical simulations, we initially *S* _{1}-activate a fraction of nodes chosen uniformly at random, and we average over 100 realizations of networks and initial conditions.

Comparison of numerical computations (symbols) with analytical predictions of Eqs. (2) and (3) (curves) for (a) the final fractions of *S* _{2}-active nodes as functions of the bonus influence β for ensembles of (4,5)-uncorrelated random networks (blue dashed-dotted curve) and Erdős-Rényi random graphs with mean degree *z* = 5 (black dashed curve) and (b,c) the temporal evolution of active fraction of nodes in each degree class in (4,5)-uncorrelated random networks for . In panel (a), we use the response functions of Eq. (1) with and uniform thresholds and . For the ER graphs, we also use a solid red curve to show the case in which the *R* _{2} thresholds are Gaussian-distributed with mean and standard deviation . The total number of nodes in each network is . For the numerical simulations, we initially *S* _{1}-activate a fraction of nodes chosen uniformly at random, and we average over 100 realizations of networks and initial conditions.

Two-parameter bifurcation diagram for (whose value is indicated by color) calculated from Eqs. (2) and (3) for Erdős-Rényi random graphs. The mean degree *z* is on the horizontal axis, and the bonus influence β is on the vertical axis. The first threshold is , and the second threshold *R* _{2} is Gaussian-distributed with mean and standard deviation . The initial seed fractions are and . The dashed curve gives the boundary of the cascade condition, and the solid curve is a numerical continuation of the saddle-node bifurcation.

Two-parameter bifurcation diagram for (whose value is indicated by color) calculated from Eqs. (2) and (3) for Erdős-Rényi random graphs. The mean degree *z* is on the horizontal axis, and the bonus influence β is on the vertical axis. The first threshold is , and the second threshold *R* _{2} is Gaussian-distributed with mean and standard deviation . The initial seed fractions are and . The dashed curve gives the boundary of the cascade condition, and the solid curve is a numerical continuation of the saddle-node bifurcation.

Two-parameter bifurcation diagram for (whose value is indicated by color) calculated from Eqs. (2) and (3) for Erdős-Rényi random graphs with mean degree *z* = 4. We plot the uniform thresholds *R* _{1} and *R* _{2} on the horizontal and vertical axes, respectively. The bonus influence is , and the initial seed fractions are and . The dashed red line gives the boundary of the cascade condition. The labeled regions (which are separated by dashed white lines) indicate cascades that are driven by (a) low influencers, (b) low and high influencers, and (c) high influencers. See the description in the text.

Two-parameter bifurcation diagram for (whose value is indicated by color) calculated from Eqs. (2) and (3) for Erdős-Rényi random graphs with mean degree *z* = 4. We plot the uniform thresholds *R* _{1} and *R* _{2} on the horizontal and vertical axes, respectively. The bonus influence is , and the initial seed fractions are and . The dashed red line gives the boundary of the cascade condition. The labeled regions (which are separated by dashed white lines) indicate cascades that are driven by (a) low influencers, (b) low and high influencers, and (c) high influencers. See the description in the text.

Tree-like structure of a network near node *A*, which we treat as the root of the tree. For every two nodes connected by an edge (e.g., nodes *B* and *C*), the node that is closer to *A* is called the parent; thus, node *B* is the parent of node *C*, and node *C* is the child of node *B*. Only the influence from nodes within a distance *n* of node *A* can reach *A* in *n* time steps.

Tree-like structure of a network near node *A*, which we treat as the root of the tree. For every two nodes connected by an edge (e.g., nodes *B* and *C*), the node that is closer to *A* is called the parent; thus, node *B* is the parent of node *C*, and node *C* is the child of node *B*. Only the influence from nodes within a distance *n* of node *A* can reach *A* in *n* time steps.

This figure is analogous to Fig. 4 of the main text, but here we use a different value of the upper threshold *R* _{2} for the multi-stage case [panels (b), (d), and (e)]. In this example, we use the threshold value ; in Fig. 4 , we used . As discussed in the text, the state-segregation effect is more pronounced for , which implies that all of the neighbors of degree-4 nodes must be *S* _{1}-active for such a node to become *S* _{2}-active (whereas only three *S* _{1}-active neighbors are needed for such *S* _{2}-activation when ). Our analytical approximation does not properly account for state segregation, and the consequences of that can be seen by comparing panels (d) in the two figures. The match with the numerical simulations in this figure is clearly worse than that in Fig. 4 .

This figure is analogous to Fig. 4 of the main text, but here we use a different value of the upper threshold *R* _{2} for the multi-stage case [panels (b), (d), and (e)]. In this example, we use the threshold value ; in Fig. 4 , we used . As discussed in the text, the state-segregation effect is more pronounced for , which implies that all of the neighbors of degree-4 nodes must be *S* _{1}-active for such a node to become *S* _{2}-active (whereas only three *S* _{1}-active neighbors are needed for such *S* _{2}-activation when ). Our analytical approximation does not properly account for state segregation, and the consequences of that can be seen by comparing panels (d) in the two figures. The match with the numerical simulations in this figure is clearly worse than that in Fig. 4 .

Article metrics loading...

Full text loading...

Commenting has been disabled for this content