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 µ ρ 8 FIG. 7: (Color online) Watts’ threshold model, with threshold mean µ and variance σ 2 = 0 (i.e., with uniform thresholds) for the networks from Fig. 1. We use a seed fraction of ρ$_{0}$ = 10 − $^{2}$. (DMS-0645369). We thank Adam D’Angelo and Face- book for providing the Facebook data used in this study. We also thank Alex Arenas, Mark Newman, CAIDA, and Cx-Nets collaboratory for making publicly available other data sets used in this paper. accurate results for networks in which ℓ ≈ ℓ$_{1}$ even in the presence of significant clustering. Such graphs, which in- clude the AS Internet network and Facebook social net- works, are definitively not locally tree-like, so that the theory is working very well even in situations where the theory’s fundamental hypothesis is known to fail utterly. The fact that analytical results for several dynamical pro- cesses can be expected to apply on “sufficiently small” small-world networks increases the value of existing the- oretical work and highlights the types of process for which improved analytical modelling of clustering effects should most profitably be targeted. We hope that the results of the present paper will motivate further research on the underlying causes of this “unreasonable” effectiveness of tree-based theory for clustered networks. We consider the class of networks for which one can define a branching matrix [38]. A branching matrix de- scribes the connection probabilities in tree-like networks with non-trivial structure, e.g., modular networks [39]. In this appendix, we derive how the error measure E de- fined in Eq. (2) depends on ℓ − ℓ$_{1}$ for a network with a branching matrix when the network is close to fully P - rewired (i.e., when it is close to a random network with the same degree correlation). We give the final formula in Eq. (A6) below. Because clustering is negligible in these infinite networks, E cannot depend on the cluster- ing coefficient C . In Fig. 6, we illustrate both of these characteristics for real-world networks. The branching matrix characterizes the average inter- SM, AH, and JPG acknowledge funding provided by Science Foundation Ireland under programmes 06/IN.1/I366 and MACSI 06/MI/005. MAP acknowl- edges a research award (#220020177) from the James S. McDonnell Foundation. PJM was funded by the NSF Appendix A: Scaling of Prediction Error with Mean Intervertex Distance Acknowledgements