vertex distance ℓ in a network, and it also determines the bond percolation behavior. The largest eigenvalue of the branching matrix, which we denote by λ , determines the percolation threshold Additionally, an estimate of the mean intervertex dis- tance can be written in terms of λ as [38] where we recall that N denotes the number of nodes in the network. We suppose now that the network is almost fully P - rewired, and we consider how values of λ that differ from the fully P -rewired value (which we denote by λ$_{1}$ ) affect the values of ℓ and p$_{th}$ . Note that it is easy to calculate λ$_{1}$ , as the branching matrix of a fully P -rewired network is given in terms of the degree correlation matrix P ( k, k $^{′}$) by [38] and λ$_{1}$ is the largest eigenvalue of B$_{1}$ . Moreover, for uncorrelated networks produced using the configuration model, λ$_{1}$ is simply ∑ k k ( k − 1) p$_{k}$/z . This implies in particular that λ$_{1}$ = z − 1 for graphs in which all nodes have the same degree (such as P -rewired Watts-Strogatz networks and the special cases of γ -theory networks used in Sec. III). Considering only small deviations from fully P -rewired values, we write λ = λ$_{1}$ +Δ λ , and ℓ = ℓ$_{1}$ +Δ ℓ . Expanding to linear terms, we find from (A2) that the excess length is Similarly, we find from (A1) that the change in percola- tion threshold is If we now make the further assumption that Δ p$_{th}$ is ap- proximately equal to the error E for the bond percolation process [this approximation is exact if the effect of the perturbation is to shift the entire bond percolation curve S ( p ) to S ( p + Δ p$_{th}$ )], we obtain the relation The scatter plots show data points for real-world net- works, and for synthetic Watts-Strogatz small-world net- works and γ -theory networks, which are described in Sec. III B. The dependence of E on ℓ − ℓ$_{1}$ is clearly strong (see the top row of scatter plots, which all have R 2 > 0 . 9), whereas the dependence on clustering is weak (see the bottom row of scatter plots, which all have R 2 < 0 . 3). Given the relatively small number of available data sets, we cannot definitively select the best scaling function F ( z, ℓ, . . . ) for the relation E ≈ F ( z, ℓ, . . . )( ℓ − ℓ$_{1}$ ), but the simple choice F = 1 /z used in Fig. 6(b) and the scal- ing function F = ln 2 λ$_{1}$/ ( λ$_{1}$ ln N ) indicated by Eq. (A6) both give satisfactory fits. In this appendix, we show scatter plots of log$_{10}$ E ver- sus a variety of possible predictors. Recall that E , which we defined in Eq. (2), gives an error measure for bond percolation. We test for the dependence of E on vari- ous combinations of the mean degree z , mean intervertex distance ℓ , and clustering coefficients [55]. Recall again that ℓ$_{1}$ denotes the value taken by ℓ in a fully P -rewired version of a network (i.e., in a random network with the same degree correlation and size). p$_{th}$ = 1 λ . (A1) ℓ ≈ ln N ln λ , (A2) B$_{1}$ ( k, k $^{′}$) ≡ ( k ′ − 1) P ( k, k $^{′}$) ∑ j P ( k, j ) = ( k ′ − 1) P ( k, k $^{′}$) kp$_{k}$/z , (A3) Δ ℓ = − Δ λ ln N λ$_{1}$ (ln λ$_{1}$ ) 2 . (A4) Δ p$_{th}$ = − Δ λ λ 2 1 . (A5) E ≈ (ln λ$_{1}$ ) 2 λ$_{1}$ ln N ( ℓ − ℓ$_{1}$ ) . (A6) Although the scope of our analysis is obviously lim- ited by our assumptions, Eq. (A6) nevertheless supports −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 0 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 log$_{10}$[ (ln λ$_{1}$ ) 2 λ$_{1}$ ln N ( ℓ − ℓ$_{1}$ )] log 10 E our main claim that E depends primarily on the excess length ℓ − ℓ$_{1}$ . Note C = 0 for branching-matrix net- works, so E is (trivially) independent of C ; compare this to the results for the real-world networks that are shown in Fig. 6(a). Moreover, the scatter plot of log$_{10}$ E versus log$_{10}$[(ln λ$_{1}$ ) $^{2}$( ℓ − ℓ$_{1}$ ) / ( λ$_{1}$ ln N )] in Fig. 8 indicates that Eq. (A6) gives a good fit ( R 2 ≈ 0 . 87) even for real-world networks. FIG. 8: (Color online) Log-log scatter plot of actual (numer- ical) values of E for real-world networks versus the values predicted by Eq. (A6), for which we numerically calculate ℓ and ℓ$_{1}$ . We find that R 2 ≈ 0 . 87; the slope of the fitted line is 1.09. 9 Appendix B: Scatter Plots