Aging in binary-state models: The Threshold model for complex contagion

We study the non-Markovian effects associated with aging for binary-state dynamics in complex networks. Aging is considered as the property of the agents to be less prone to change their state the longer they have been in the current state, which gives rise to heterogeneous activity patterns. In particular, we analyze aging in the Threshold model, which has been proposed to explain the process of adoption of new technologies. Our analytical approximations give a good description of extensive Monte Carlo simulations in Erdős-Rényi, random-regular and Barabási-Albert networks. While aging does not modify the cascade condition, it slows down the cascade dynamics towards the full-adoption state: the exponential increase of adopters in time from the original model is replaced by a stretched exponential or power law, depending on the aging mechanism. Under several approximations, we give analytical expressions for the cascade condition and for the exponents of the adopters' density growth laws. Beyond random networks, we also describe by Monte Carlo simulations the effects of aging for the Threshold model in a two-dimensional lattice.

Figure 1

Average density $\rho$ of adopters for an Erdős-Rényi graph of mean degree $z$ using a model with threshold $T$. Color-coded values of $\rho$ are from Monte Carlo simulations of the model without aging in a graph with $N=10000$ agents. Black dashed and white dotted lines correspond to the $T_c$ value obtained numerically for the model with exogenous and endogenous aging, respectively. Monte Carlo simulations are averaged over $M=5\times {10}^4$ realizations. The red solid line is the analytical approximation of the cascade boundary, from Eq. (17), which is the same with and without aging.

Figure 2

Cascade spreading for (a) the original Threshold model, and the versions with (b) endogenous and (c) exogenous aging. Yellow nodes are adopters and purple nodes are nonadopters. Time increases from left to right. Monte Carlo simulations are performed in an Erdős-Rényi network with mean degree $z=3$ and $T=0.22$. System size is $N=8000$.

Figure 3

Cascade dynamics and fall to the full-adopt state ($\rho \sim 1$) of the Threshold model (a) without aging, and the versions with (b) endogenous and (c) exogenous aging effects. At (b) and (c), the evolution is plotted as a function of the logarithm of time, $ln\left(t\right)$, in Monte Carlo steps, as in the insets. The underlying network is a 3-regular random graph and the threshold is $T=0.2$. The exponent values are $\alpha \simeq 1.0, \beta \simeq 1.14, \gamma \simeq 0.38$, and $\delta \simeq 1.0$. Numerically integrated solutions of Eq. (4) (solid lines) accurately describe the numerical results. Monte Carlo simulations are averaged over $M=5\times {10}^4$ realizations in a network of $N=1.6\times {10}^5$ nodes.

Figure 4

Average time to reach the steady state ($\rho >0.9$) $\tau$ as a function of the system size $N$ for the original Threshold model and the versions with endogenous and exogenous aging. The underlying network is a 5-regular random graph and the threshold is $T=0.12$. Monte Carlo simulations are averaged over $M=5\times {10}^4$ realizations. Solid lines are the system size-dependent timescale: For the original model, ${\tau }_{\mathrm{NO}\mathrm{AG}}=(1/\alpha )ln\left(N\right)$, and for the endogenous $({\tau }_{\mathrm{ENDO}}=2N^{1/\delta }-2)$ and exogenous (${\tau }_{\mathrm{EXO}}=2{[ln\left(N\right)/\beta ]}^{1/\gamma }-2$) aging, which follows from the dynamics from Eqs. (1, 2, 3). The exponents $\alpha , \beta , \gamma$, and $\delta$ are fitted exponents.

Figure 5

Cascade dynamics of the Threshold model with (a)–(c) endogenous and (d)–(f) exogenous aging. From the left column to the right: (a), (d) a random regular graph with degree $z=5$, (b), (e) an Erdős-Rényi graph with average degree $z=5$, and (c), (f) a Barabási-Albert graph with average degree $z=8$. Different colors indicate different values of $T$ and markers correspond to different system sizes: $N=2500$ (plus), $10000$ (circles), $40000$ (triangles), $160000$ (crosses), and $640000$ (squares). Time is scaled according to the system size for each model: ${\tau }_{\mathrm{EXO}}=2{[ln\left(N\right)/\beta ]}^{1/\gamma }-2, {\tau }_{\mathrm{ENDO}}=2N^{1/\delta }-2$, where $\beta ,\gamma$, and $\delta$ are the fitted exponents from the behavior according to Eqs. (2) and (3). Solid lines are obtained from the solutions of Eq. (13). Monte Carlo simulations are averaged over $M=5\times {10}^4$ realizations.

Figure 6

Exponent $\alpha$ for the original Threshold model (empty markers) and $\delta$ for the version with endogenous aging (filled markers) for different values of the average degree $z$ (and $T=0.1$) (left) and as a function of $T$ for fixed $z$ (right). Different markers indicate results from Monte Carlo simulations with different topologies: red triangles indicate an Erdős-Rényi (ER) graph, blue circles indicate a random-regular (RR) graph, and green squares indicate a Barabási-Albert (BA) graph. In the right panel, the average degree is fixed $z=5$ for ER and RR, and $z=8$ for the BA. Predicted values by Eq. (22) (solid lines) fit the results for each topology. System size is fixed at $N=4\times {10}^6$ for the original model and $N=3.2\times {10}^5$ for the version with aging.

Figure 7

Exponent $\gamma$ for the Threshold model with exogenous aging for different values of the average degree $z$ ($T=0.1$) (left) and as a function of $T$ for fixed $z$ (right). Different markers indicate results from Monte Carlo simulations with different topology: red triangles indicate an Erdős-Rényi (ER) graph, blue circles indicate a random-regular (RR) graph, and green squares indicate a Barabási-Albert (BA) graph. In the right panel, the average degree is fixed $z=5$ for ER and RR, and $z=8$ for the BA. Predicted values by numerical integration of Eqs. (13) (solid lines) fit approximately the results for each topology. System size is fixed at $N=3.2\times {10}^5$.

Figure 8

Cascade spreading of (a) the original Threshold model and the versions with (b) exogenous and (c) endogenous aging on a Moore neighborhood lattice with size $N=L\times L, L=405$. Yellow and purple nodes are adopters and nonadopters, respectively. Time increases from left to right. Initial seeds are selected favoring cascades: one agent and all his or her neighbors are set as adopters at the center of the system.

Figure 9

Cascade dynamics of the Threshold model with (a) exogenous and (b) endogenous aging on a Moore neighborhood lattice. Different colors indicate different values of the threshold $T$. Different markers indicate the results of Monte Carlo simulations with different system size $N=L\times L$: $L=50$ (crosses), 100 (triangles), 200 (circles), and 400 (squares). In (a), time is scaled according to size $\tau =L^{2/\zeta }$. Discontinuous solid lines indicate a power-law behavior with exponent $\zeta =4/3$ (blue), 1 (red), and $2/3$ (green). In (b), the system sizes are not scaled due to the slow dynamics. Discontinuous solid lines indicate a power-logarithmic behavior, $\rho \left(t\right)N\sim ln{\left(t\right)}^{\nu }$, with exponent $\nu =7/3$ (blue), 2 (red), and $5/3$ (green).

Figure 10

Average density $\rho$ of adopters for an Erdős-Rényi graph of mean degree $z$ using the symmetrical Threshold model with endogenous aging with threshold $T$. The activation probability is exponential, $p_A\left(j\right)=exp[-0.5*(j+1\left)\right]$. Color-coded values of $\rho$ are from Monte Carlo simulations of the model without aging in a graph with $N=10000$ agents. Monte Carlo simulations are averaged over $M=5\times {10}^4$ realizations.

Figure 11

Schematic representation of the transitions to or from the set $s_{k,m,j}$ ($j>0)$. We show the central node with some neighbors for different values $m$ and $j$. Purple nodes are susceptible, nonadopters, or spin down, and yellow are infected, adopters, or spin up.