0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.2 0.4 0.6 0.8 1 p$_{k}$ −theory P ( k,k’ )−theory Numerical simulation  on original network (a) Facebook Oklahoma (b) AS Internet (c) PGP Network (d) Power Grid µ ρ 4 edge [23] has smaller absolute values for the networks shown in panels (a) and (d) (0.074, with the mean 0.063 over 100 Facebook networks, and 0.0035, respectively) than it does for the networks in (b) and (c) ( − 0 . 2 and 0.24, respectively). (We use K to denote this maximal value of k .) For Fig. 2(a) and (b), we obtain K$_{P}$$_{(}$$_{k,k}$ ′ $_{)}$/K$_{num}$ ≈ 0 . 916 and K$_{P}$$_{(}$$_{k,k}$ ′ $_{)}$/K$_{num}$ ≈ 0 . 826, respectively. The corresponding values for Fig. 2(c) and (d) are K$_{P}$$_{(}$$_{k,k}$ ′ $_{)}$/K$_{num}$ ≈ 0 . 516 and K$_{P}$$_{(}$$_{k,k}$ ′ $_{)}$/K$_{num}$ ≈ 0 . 368. Watts [36] introduced a simple model for the spread of cultural fads. It allows one to examine how a small initial fraction of early adopters can lead to a global cas- cade of adoption via a social network. The p$_{k}$ -theory and P ( k, k $^{′}$)-theory for the average cascade size are given, re- spectively, in Ref. [37] and Ref. [35]. In Fig. 3, we com- pare these theories with numerical simulations on popu- lations with Gaussian threshold distributions of mean µ and variance σ 2 = 0 . 04. The cascade size shows a sharp transition as µ is increased. As with the other processes that we discussed above, the position of this transition is accurately captured by the theory for the Facebook and AS Internet networks but not for the other examples. Figures 2, 3, and 4 show similar comparisons of analyt- ical results versus numerical simulations for other well- studied processes on networks. In Fig. 2, we plot the k -core sizes of the networks. The k -core is the largest subgraph whose nodes all have degree at least k . The p$_{k}$ -theory for k -core sizes is given in Ref. [34] and the P ( k, k $^{′}$)-theory is given by Eq. (32) of Ref. [35]. As shown in Fig. 2(a,b), we again find very good agree- ment of P ( k, k $^{′}$)-theory with numerical calculations on the AS Internet and Facebook networks and less accu- rate results for the other example networks. This can be quantified by comparing the actual (numerical) result for the highest value of k for which the k -core size is nonzero to the value that is predicted by P ( k, k $^{′}$)-theory. FIG. 3: (Color online) Watts’ threshold model, with threshold mean µ and variance σ 2 = 0 . 04 for the networks from Fig. 1. We use the seed fraction ρ$_{0}$ = 0 because the nodes with negative thresholds immediately turn on and act as initial seeds. In other words, the effective seed fraction is given by the cumulative distribution of thresholds at zero: [ 1 + erf ($_{−}$ µ/ ( $_{σ}$√$_{2}$ ))] / 2. B. k -Cores C. Watts’ Threshold Model