0 20 40 60 80 100 0.2 0.4 0.6 0.8 1 0 5 10 15 20 0 5 10 15 20 25 30 0.2 0.4 0.6 0.8 1 0 5 10 15 20 p$_{k}$ −theory P ( k,k’ )−theory Numerical result for original network (a) Facebook Oklahoma (b) AS Internet (c) PGP Network (d) Power Grid k k -core s i ze 3 FIG. 2: (Color online) Plots of k -core sizes versus k for the real-world networks from Fig. 1. The highest nonzero k -cores are (a) K p$_{k}$ = 91, K$_{P}$$_{(}$$_{k,k}$ ′ ) = 98, K$_{num}$ = 107; (b) K p$_{k}$ = 132, K$_{P}$$_{(}$$_{k,k}$ ′ ) = 19, K$_{num}$ = 23; (c) K p$_{k}$ = 7, K$_{P}$$_{(}$$_{k,k}$ ′ ) = 16, K$_{num}$ = 31; and (d) K p$_{k}$ = 6, K$_{P}$$_{(}$$_{k,k}$ ′ ) = 7, K$_{num}$ = 19. using the algorithm in Ref. [33] and plotted the results as black disks in Fig. 1. It is apparent from Fig. 1(a,b) that P ( k, k $^{′}$)-theory matches numerical simulations very accu- rately for the AS Internet and Oklahoma Facebook net- works, and we found similar accuracy for all 100 single- university Facebook data sets available to us. However, as shown in Fig. 1(c,d), the match between theory and numerics is much poorer on the PGP and Power Grid networks. The usual explanation for this lack of accu- racy is that it is caused by clustering in the real-world network that is not captured by P ( k, k $^{′}$)-theory. Note, however, that the Oklahoma Facebook network has one of the highest clustering coefficients of the four cases in Fig. 1 even though it is accurately described by its P ( k, k $^{′}$)-theory. Indeed, the global clustering coefficients (defined as the mean of the local clustering coefficient over all nodes [29]) for the Oklahoma Facebook, AS Internet, PGP, and Power Grid networks are 0.23, 0.21, 0.27, and 0.08, re- spectively. (See Table I for basic summary statistics for these networks.) The clustering coefficients for all 100 Facebook networks range from 0.19 to 0.41, and the mean value of these coefficients is 0.24. These observations sug- gest that one ought to consider other explanatory mecha- nisms for the discrepancy between theory and simulations in Fig. 1(c,d). In considering other explanations, note that the dis- crepancy between theory and numerics in Fig. 1(c,d) does not arise from finite-size effects. To demonstrate this, we rewired the networks using an algorithm that preserves the P ( k, k $^{′}$) distribution but otherwise randomizes con- nections between the N nodes [52]. Because this scheme preserves the degree correlation matrix P ( k, k $^{′}$), we call this the P -rewiring algorithm. Note that the ensemble of fully P -rewired networks is in fact the ensemble of random networks defined by the P ( k, k $^{′}$) matrix of the original (unrewired) network. We show numerical calculations of the GCC sizes for these rewired networks with blue squares in Fig. 1(c,d) and observe that they agree very well with the curves pro- duced from P ( k, k $^{′}$)-theory. We conclude that the struc- tural characteristics of the original networks—rather than simply their sizes—must underlie the observed dif- ferences between simulations and analytics. Also note that the agreement between P ( k, k $^{′}$)- and p$_{k}$ -theories in Fig. 1 is better in panels (a) and (d) than in panels (b) and (c). This is because the Pearson corre- lation coefficient r of the end-vertex degrees of a random