7 −2 −1.5 −1 −0.5 0 0.5 1 −4 −3.5 −3 −2.5 −2 −1.5 −1 −0.5 Power Grid PGP Network AS Internet RL Internet Coauthorships Airports500 Interacting Proteins C. Elegans Metabolic C. Elegans Neural Facebook Caltech Facebook Georgetown Facebook Oklahoma Facebook UNC WS:  z =10,  N =1000 WS:  z =10,  N =10000 (3,3)=1,  N =1002 (3,3)=1,  N =10002 (a) log$_{10}$ C log 10 E −3.5 −3 −2.5 −2 −1.5 −1 −0.5 0 0.5 1 −4 −3.5 −3 −2.5 −2 −1.5 −1 −0.5 (b) log$_{10}$[( ℓ − ℓ$_{1}$ ) /z ] log 10 E FIG. 6: (Color online) Scatter plots of log$_{10}$ E versus (a) log$_{10}$ C (with R 2 ≈ 0 . 087) and (b) log$_{10}$ [( ℓ − ℓ$_{1}$ ) /z ] (with R 2 ≈ 0 . 94). work, we calculate the coefficient of determination R 2 using a linear regression. For the data in Fig. 6(a), we calculate R 2 ≈ 0 . 087 (using the points only and ignor- ing the connecting curves which help identify families of points). This relatively small value indicates that C is not a good predictor of the theory error across the set of networks that we tested (see Table I). After examin- ing a wide range of possibilities (see the scatter plots in Appendix B), we found that the network measure that best correlates with the error E (on logarithmic scales) is ( ℓ − ℓ$_{1}$ ) /z (which gives R 2 ≈ 0 . 94), where z is the mean degree and ℓ$_{1}$ is the mean intervertex distance in the version of the network that has been fully rewired while preserving the joint degree distribution P ( k, k $^{′}$) [see Fig. 6(b)]. Recall that one can think of such fully P - rewired versions of a network as random networks with the same degree correlation P ( k, k $^{′}$) and size as the orig- inal network. restricted in its applicability, it lends weight to our claim that E depends primarily on ℓ − ℓ$_{1}$ rather than on the clustering C . At the beginning of this paper, we posed the following question: “How small must small-world networks be in order for P ( k, k $^{′}$)-theory to give accurate results?” Our heuristic answer is that they must have a value for the mean intervertex distance ℓ that differs from the mean intervertex distance in a random network with the same P ( k, k $^{′}$) and number of nodes by no more than about 10% of the mean degree z . Surprisingly, the level of clus- tering has much less of an impact on the accuracy of P ( k, k $^{′}$)-theory, which is why we found excellent matches between theory and numerical simulations even in highly clustered graphs such as Facebook social networks and the AS Internet network. We can summarize our observations as follows. Given a network, we compare its mean intervertex distance ℓ with the value ℓ$_{1}$ in a random network of equal size and degree correlation P ( k, k $^{′}$). If the difference ℓ − ℓ$_{1}$ is suffi- ciently small—e.g., if it is less than z/ 10, as was the case in Fig. 1(a,b)—then the P ( k, k $^{′}$)-theory can be expected to accurately give the GCC size, k -core sizes, and results for several dynamical processes (see Figs. 1–4). For ex- ample, the AS Internet graph has ( ℓ − ℓ$_{1}$ ) /z ≈ 3 . 3 × 10 − 2 and all 100 Facebook networks have values much smaller than this. However, the theory is not accurate for larger values of ℓ − ℓ$_{1}$ . (For example, the PGP and Power Grid networks have ( ℓ − ℓ$_{1}$ ) /z values of approximately 0 . 45 and 3 . 9, respectively.) Although our presentation used bond percolation as our primary example, we demonstrated in Figs. 1–4 that if P ( k, k $^{′}$)-theory is accurate for percolation, then it also works well for other processes. However, an absolute measure of accuracy must, of course, depend on the pro- cess under scrutiny. For example, Fig. 7 shows a com- parison between theory and simulation results for Watts’ threshold model in which σ = 0, which implies that all nodes have identical thresholds equal to µ (in contrast to Fig. 3). This example now exhibits different results for theory and numerics even in the Facebook networks. This suggests that the σ = 0 case of Watts’ model is particularly sensitive to deviations of the network from randomness and suggests that this case provides a suit- able testing ground for new analytically solvable models of networks that include clustering [12, 13]. Because the tree-based theory systematically gives ac- curate results for dynamical processes on networks that are not locally tree-like when the intervertex distance is small, it seems that there must be a deeper argument than is currently known for the validity of such theories. We show in Appendix A that the error measure E de- pends linearly on ℓ − ℓ$_{1}$ in a certain class of networks with zero clustering. Although this theoretical result is In summary, we have shown that for a variety of processes—including bond percolation and k -core size calculations—tree-based analytical theory yields highly IV. CONCLUSIONS