Threshold Cascade Dynamics in Coevolving Networks

Abstract

We study the coevolutionary dynamics of network topology and social complex contagion using a threshold cascade model. Our coevolving threshold model incorporates two mechanisms: the threshold mechanism for the spreading of a minority state such as a new opinion, idea, or innovation and the network plasticity, implemented as the rewiring of links to cut the connections between nodes in different states. Using numerical simulations and a mean-field theoretical analysis, we demonstrate that the coevolutionary dynamics can significantly affect the cascade dynamics. The domain of parameters, i.e., the threshold and mean degree, for which global cascades occur shrinks with an increasing network plasticity, indicating that the rewiring process suppresses the onset of global cascades. We also found that during evolution, non-adopting nodes form denser connections, resulting in a wider degree distribution and a non-monotonous dependence of cascades sizes on plasticity.

Keywords: coevolution; link rewiring; threshold cascades.

Figure 1

An example of the evolution rules of the coevolutionary dynamics of a threshold cascade model. A connected pair of an adopting (filled circles) and a non-adopting node (open circles) is removed with a probability p, and the non-adopting node establishes a connection to a new node that is not adopting, chosen randomly from the entire network. In addition, a non-adopting node becomes adopting if the fraction of adopting neighbors is larger than the threshold $\theta$. Once a node becomes adopting, the node is then permanently in this state.

Figure 2

(a) The final fraction R of adopting nodes and the size S of the largest non-adopting cluster as a function of the network plasticity p. (b) The number $n_c$ of clusters to network size N as a function of p. The dynamics starts with $\theta =0.18$ in ER networks with $N={10}^5$, $z=3$, and an initial fraction of seeds of $R_0=2\times {10}^{-4}$. The average values are obtained by ${10}^4$ independent runs with different network realizations for each run. Examples of network structures with $N=200$ at the steady state with (c) $p=0.2$ and (d) $p=0.8$. Red and blue nodes represent adopting and non-adopting states, respectively.

Figure 3

The final fraction R of adopting nodes in ER networks with $N={10}^5$ as a function of the average degree z and threshold $\theta$, with various rewiring probabilities, i.e., (a) $p=0.2$, (b) $p=0.4$, and (c) $p=0.6$, in a steady state. Th dashed lines represent the transition points between the global cascade and no cascade phases in static networks, that is $p=0$, obtained from Equation (3). The solid lines represent the transition points with network plasticity p by using mean-field approximations. The numerical results are obtained by ${10}^3$ independent runs with different network realizations for each run.

Figure 4

(a) The final size R of cascades as a function of network plasticity p and average degree z of the ER networks with threshold $\theta =0.18$ and seed fraction $R_0=2\times {10}^{-4}$. The dashed lines represent analytical predictions obtained by Equation (9). (b) The size R as a function of the average degree z in ER networks for $p=0,0.2,0.4$, and $0.6$ with $\theta =0.18$. The lines represent analytical predictions based on Equations (4) and (5). (c) Inset shows the size R with respect to the probability of link rewiring p for $z=2$ and $2.5$ and $\theta =0.1$. The numerical results were obtained with ${10}^3$ independent runs with different network realizations for each run.

Figure 5

Degree distribution $P\left(k\right)$ of the coevolving threshold model at the steady state in (a) linear and (b) log scales for $p=0,0.1,0.2,0.3$ (global cascade region) and (c) linear scale for $p=0.4,0.5,0.6,0.7$ (no cascades region). The results were obtained from ER networks with $z=4$ and $N={10}^5$ with ${10}^4$ independent runs. The solid lines in (a,c) represent the Poisson distribution with $z=4$.

Figure 6

The critical values $p_c$ of network plasticity estimated by the mean-field approximation (a) with respect to z with fixed $\theta =0.1,0.15,0.2$ and (b) with respect to $\theta$ with fixed $z=2,4,6,8$.