Degree correlations amplify the growth of cascades in networks

Networks facilitate the spread of cascades, allowing a local perturbation to percolate via interactions between nodes and their neighbors. We investigate how network structure affects the dynamics of a spreading cascade. By accounting for the joint degree distribution of a network within a generating function framework, we can quantify how degree correlations affect both the onset of global cascades and the propensity of nodes of specific degree class to trigger large cascades. However, not all degree correlations are equally important in a spreading process. We introduce a new measure of degree assortativity that accounts for correlations among nodes relevant to a spreading cascade. We show that the critical point defining the onset of global cascades has a monotone relationship to this new assortativity measure. In addition, we show that the choice of nodes to seed the largest cascades is strongly affected by degree correlations. Contrary to traditional wisdom, when degree assortativity is positive, low degree nodes are more likely to generate largest cascades. Our work suggests that it may be possible to tailor spreading processes by manipulating the higher-order structure of networks.

Figure 1

Critical threshold ${\varphi }^{*}$ as a function of network's degree assortativity. Global cascades exist in the parameter region $\varphi <{\varphi }^{*}$, and only local cascades exist in the region $\varphi >{\varphi }^{*}$.

Figure 2

Expected outbreak size $S\left(k\right)$ on network with log-normal distribution network joint degree distribution $e_{k,k^{\prime }}$. The distribution is with parameters $\mu =1.5$ and $\sigma =1.5$, and the assortativity parameter $c$ is tunable between range $-1$ and 1. The vertical dashed line indicates the threshold chosen $\varphi =\frac{1}{6}$.

Figure 3

The block probability weight on different threshold chosen in $e_{k,k^{\prime }}$ with $\mu =1.5,2.5$ and $\sigma =1.5,2.5$, which sums over the element values in range of $2\le k\le {\varphi }_0^{-1}$, $2\le k^{\prime }\le {\varphi }_0^{-1}$, where ${\varphi }_0^{-1}$ solves the equation of Eq. (8).

Figure 4

Critical threshold ${\varphi }^{*}$ as a function of the network's vulnerable node degree correlation defined by Eq. (16). Global cascades exist in the parameter region $\varphi <{\varphi }^{*}$, and only local cascades exist in the region $\varphi >{\varphi }^{*}$.

Figure 5

Theoretical calculation (lines) and observations (points) of giant vulnerable component of synthetic power-law networks with exponent $\alpha =2.4$ and number of nodes $n=10000$.

Figure 6

Theoretical calculation and observations of single seed cascading problems on synthetic power-law networks with $\alpha =2.1$ and 2.4, comparing the observed expected outbreak by the seed degree (blue dots) and the predictions of the generating function formulation (red line).

Figure 7

Theoretical calculation (lines) and observations (points) of giant vulnerable component of selected real-world networks.

Figure 8

Theoretical calculation and observations of single seed cascading problems on real-world networks, comparing the observed expected outbreak by the seed degree (blue dots), predictions of the generating function formulation (red line) and the observation on the reconstructed graph (green crosses).