With the couplings J$_{0}$ = − 0 . 9, J = 1 and a smaller av- erage connectivity, c = 4 . 5 the theory predicts that only a P-SG transition is present. We studied by simulation this spin-glass critical behavior and we found the critical temperature very close to the theoretical prediction. We also introduced a model not previously studied, the two dimensional Edwards-Anderson model with added long-range shortcuts, where we confirmed that even an infinitesimal inclusion of shortcuts makes the spin-glass phase transition to occur at a finite non-zero tempera- ture. In other words, as the theory predicts, we find that the two dimensional Edwards-Anderson model is not thermodynamically stable under graph-noise. The class of disordered models for which the theory is applicable is very wide and its application just relies on the availability of numerical or analytical results for the susceptibility of non disordered models in arbitrary This work was supported by the projects SOCIAL- NETS and FCT (Portugal) PTDC/FIS/71551/2006. We thank M. Barroso for the administration of the compu- tational facilities where the simulations were done. d$_{0}$ dimensions. When there is strong frustration, sim- ulations are difficult to perform requiring large simula- tion times and averages over many samples. Our results clearly confirm the usefulness of the effective field the- ory proposed in [12] by giving accurate predictions for the models phase diagram. The possibility to improve the theory out of the P region opens a new interesting challenge. Acknowledgments 12 [1] M. M´ ezard, G. Parisi, M.A. Virasoro, 1987 Spin Glass Theory and Beyond (Singapore: World Scientific). [2] M. M´ ezard, G. Parisi, Eur. Phys. J. B 20 , 217-233 (2001). [3] S. Franz, M. Leone, F. Ricci-Tersenghi, and R. Zecchina, Phys. Rev. Lett. 87 , 127209 (2001). [4] M. Ostilli, J. Stat. Mech. P09010 (2007). [5] D. Sherrington, S. Kirkpatrick, Phys. Rev. Lett. 35 , 1792 (1975). [6] L. Viana, A. J. Bray, J. Phys. C: Solid State Phys. 18 , 3037 (1985). [7] D. J. Watts, S. H. Strogatz, Nature, 393 , 440 (1998). [8] A. Barrat and M. Weigt, Eur. Phys. J B, 13 , 547 (2000). [9] T. Nikoletopoulos, A. C. C. Coolen, I. Prez Castillo, N. S. Skantzos, J. P. L. Hatchett and B. Wemmenhove, J. Phys. A: Math. Gen. 37 6455-6475 (2004). Note that in the model considered in [9] the long range coupling J is divided by c (see Eq. (1) of [9]). [10] B. Wemmenhove, T. Nikoletopoulos, and J. P. L. Hatch- ett J. Stat. Mech. P11007 (2005). [11] D. Boll´ e, R. Heylen and N.S. Skantzos, Phys. Rev. E 74 , 056111 (2006). [12] M. Ostilli and J. F. F. Mendes, Phys. Rev. E 78, 031102 (2008). [13] M. Ostilli, J. Stat. Mech. P10004 (2006). [14] M. Ostilli, J. Stat. Mech. P10005 (2006). [15] Essentially, the presence of a finite probability of rewiring p affects only the value of the effective short-range cou- pling βJ (F) 0 whose value in turn cannot change the critical behavior of the model. M. Ostilli and J. F. F. Mendes, in preparation. [16] M. Gitterman, J. Phys. A 33 , 8373 (2000). [17] A. Pekalski, Phys. Rev. E 64 , 057104 (2001). [34] An exception is the spherical model which can be treated analytically for any d$_{0}$ ; see [12]. [33] Katzgraber, H. G., Lee, L. W. and Campbell, I. A., Phys. Rev. B 75 , 014412 (2007). [32] A. K. Hartmann and A. P. Young, Phys. Rev. B 64, 180404(R) (2001). [31] E Luijten, K Binder, H W J Bl¨ ote, Eur. J. Phys. B, 9 , 289-97 (1999). [30] K. Vollmayr, J. D. Reger, M. Schencher and K. Binder, Z. Phys. B: Condens. Matter 9l , 113-125 (1993). [29] G. Parisi and Juan J. Ruiz-Lorenzo, Phys. Rev. B, 54 , R3698-01, (1996). [28] E Luijten and H W J Bl¨ ote, Int. J. Mod. Phys. C, 6 , 359-70 (1995). [27] G. Kamieniarz and H. W. J. Bl¨ ote, J. Phys. A: Math. Gen. 26 , 201 (1993). [26] H. W. J. Bl¨ ote, E. Luijten, and J. R. Heringa, J. Phys. A 28 , 6289, (1995). [25] K. Binder, Z. Phys B - Condensed Matter 43 , 119-140 (1981). [24] Metropolis N, Rosenbluth A, Rosenbluth M., Teller A.; Teller E. Journal of Chemical Physics 21 , 1087 (1953). [23] S. F. Edwards and P. W. Anderson, J. Phys. F: Met. Phys. 5 , 965 (1975) [22] N. S. Skantzos, A. C. C. Coolen, J. Phys. A: Math. Gen. 33 5785-5807 (2000). [21] C. P. Herrero, Phys. Rev. E, 77 , 041102, (2008). [20] M. B. Hastings, Phys. Rev. Lett. 96 , 148701 (2006). [19] C. P. Herrero, Phys. Rev. E 65 , 066110 (2002). [18] J. Viana Lopes, Y. G. Pogorelov, J. M. B. Lopes dos Santos, and R. Toral, Phys. Rev. E 70 , 026112, (2004).