Network N z ℓ ℓ$_{1}$ ℓ B 1 C ˜ C r Ref(s). Real world Power Grid 4941 2.67 18.99 8.61 7.85 0.08 0.10 0.0035 [29, 30] PGP Network 10680 4.55 7.49 5.40 2.66 0.27 0.38 0.23 [26–28] AS Internet 28311 4.00 3.88 3.67 2.56 0.21 0.0071 -0.20 [25] RL Internet 190914 6.34 6.98 5.25 3.17 0.16 0.061 0.025 [40] Coauthorships 39577 8.88 5.50 4.45 2.93 0.65 0.25 0.19 [41, 42] Airports500 500 11.92 2.99 2.76 1.62 0.62 0.35 -0.278 [43, 44] Interacting Proteins 4713 6.30 4.22 4.05 2.96 0.09 0.062 -0.136 [45–47] C. Elegans Metabolic 453 8.94 2.66 2.55 1.93 0.65 0.12 -0.226 [48, 49] C. Elegans Neural 297 14.46 2.46 2.33 1.84 0.29 0.18 -0.163 [29, 50] Facebook Caltech 762 43.70 2.34 2.26 1.55 0.41 0.29 -0.066 [24] Facebook Georgetown 9388 90.67 2.76 2.55 1.79 0.22 0.15 0.075 [24] Facebook Oklahoma 17420 102.47 2.77 2.66 1.79 0.23 0.16 0.074 [24] Facebook UNC 18158 84.46 2.80 2.68 1.87 0.20 0.12 $^{7}$×10 − 5 [24] Synthetic γ -theory [ γ (3 , 3) = 1] 1002 3 13.15 8.06 9.97 1/3 1/3 N/A [13] γ -theory [ γ (3 , 3) = 1] 10002 3 19.81 11.37 13.29 1/3 1/3 N/A [13] Watts-Strogatz (WS) 1000 10 50.45 3.29 3.14 2/3 2/3 N/A [29] Watts-Strogatz (WS) 10000 10 500.45 4.34 4.19 2/3 2/3 N/A [29] 10 TABLE I: Basic summary statistics for the networks that we used in this paper. We have treated all real-world data sets as undirected, unweighted networks and have computed the following properties: total number of nodes N ; mean degree z ; mean intervertex distance ℓ in original network; mean intervertex distance ℓ$_{1}$ in the corresponding fully P -rewired version of the network (i.e., in a random network with the original degree correlation); the mean intervertex distance ℓ B 1 predicted by Eq. (A2) using the branching matrix corresponding to a random network with the original degree correlation; clustering coefficients C and ˜ C (whose respective definitions are given by Eqs. (3.6) and (3.4) of [23]); and the Pearson degree correlation coefficient r . The last column in the table gives the citation number(s) for the data in the bibliography. [29] D. J. Watts and S. H. Strogatz, Nature (London) 393 , 440 (1998). [28] Giant component of the network of users of the Pretty-Good-Privacy algorithm for secure information interchange , URL http://deim.urv.cat/ ~ aarenas/data/xarxes/PGP.zip . [27] M. Bogu˜ n´ a, R. Pastor-Satorras, A. Diaz-Guilera, and A. Arenas, Phys. Rev. E 70 , 056122 (2004). [26] X. Guardiola, R. Guimera, A. Arenas, A. Diaz-Guilera, D. Streib, and L. A. N. Amaral, arXiv (2002), 0206240. [25] The CAIDA Autonomous System Re- lationships Dataset, 30-Jun-2008 , URL [24] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, arXiv (2008), 0809.0690. [23] M. E. J. Newman, SIAM Rev. 45 , 167 (2003). [22] T. Britton, M. Deijfen, A. N. Lager˙as, and M. Lindholm, J. Appl. Probab. 45 , 743 (2008). [21] J. C. Miller, Phys. Rev. E 80 , 020901 (2009). [20] J. C. Miller, J. Roy. Soc. Interface 6 , 1121 (2009). [19] P. Trapman, Theor. Pop. Biol. 71 , 160 (2007). [18] M. ´ A. Serrano and M. Bogu˜ n´ a, Phys. Rev. Lett. 97 , 088701 (2006). [17] M. A. Serrano and M. Bogu˜ n´ a, Phys. Rev. E 74 , 056115 (2006). [16] M. ´ A. Serrano and M. Bogu˜ n´ a, Phys. Rev. E 74 , 056114 (2006). ´ [15] M. Ostilli and J. F. F. Mendes, Phys. Rev. E 80 , 011142 (2009). [14] J. P. Gleeson and S. Melnik, Phys. Rev. E 80 , 046121 (2009). [13] J. P. Gleeson, Phys. Rev. E 80 , 036107 (2009). [12] M. E. J. Newman, Phys. Rev. Lett. 103 , 058701 (2009). [11] M. A. Porter, J.-P. Onnela, and P. J. Mucha, Not. Amer. Math. Soc 9 , 1082 (2009). [10] M. E. J. Newman, Phys. Rev. E 68 , 026121 (2003). [9] A. Arenas, A. Diaz-Guilera, J. Kurths, Y. Moreno, and C. Zhou, Phys. Rep. 469 , 93 (2008). [8] M. Garavello and B. Piccoli, Traffic Flow on Networks (American Institute of Mathematical Sciences, Spring- field, MO, 2006). [7] K. T. D. Eames, Theor. Pop. Biol. 73 , 104 (2008). [6] M. Barth´ elemy, A. Barrat, R. Pastor-Satorras, and A. Vespignani, J. Theor. Biol. 235 , 275 (2005). [5] R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86 , 3200 (2001). [4] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Rev. Mod. Phys. 80 , 1275 (2008). [3] A. Barrat, A. Vespignani, and M. Barthelemy, Dynamical Processes on Complex Networks (Cambridge University Press, Cambridge, UK, 2008). [2] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Phys. Rep. 424 , 175 (2006). [1] S. H. Strogatz, Nature (London) 410 , 268 (2001).