{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:04:23Z","timestamp":1725516263575},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540788072"},{"type":"electronic","value":"9783540788089"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78808-9_3","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"24-35","source":"Crossref","is-referenced-by-count":0,"title":["Expansion and Lack Thereof in Randomly Perturbed Graphs"],"prefix":"10.1007","author":[{"given":"Abraham D.","family":"Flaxman","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/978-3-540-27821-4_31","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A.D. Flaxman","year":"2004","unstructured":"Flaxman, A.D., Frieze, A.M.: The diameter of randomly perturbed digraphs and some applications. In: Jansen, K., et al. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol.\u00a03122, pp. 345\u2013356. Springer, Heidelberg (2004)"},{"issue":"3","key":"3_CR2","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0401033","volume":"1","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B., Chung, F.R.K.: The diameter of a cycle plus a random matching. SIAM J. Discrete Math.\u00a01(3), 328\u2013333 (1988)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/rsa.10070","volume":"22","author":"T. Bohman","year":"2003","unstructured":"Bohman, T., Frieze, A., Martin, R.: How many random edges make a dense graph Hamiltonian? Random Structures Algorithms\u00a022(1), 33\u201342 (2003)","journal-title":"Random Structures Algorithms"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1002\/rsa.10112","volume":"24","author":"T. Bohman","year":"2004","unstructured":"Bohman, T., Frieze, A., Krivelevich, M., Martin, R.: Adding random edges to dense graphs. Random Structures Algorithms\u00a024(2), 105\u2013117 (2004)","journal-title":"Random Structures Algorithms"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1002\/rsa.20097","volume":"29","author":"M. Krivelevich","year":"2006","unstructured":"Krivelevich, M., Sudakov, B., Tetali, P.: On smoothed analysis in dense graphs and formulas. Random Structures Algorithms\u00a029(2), 180\u2013193 (2006)","journal-title":"Random Structures Algorithms"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/380752.380813","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing","author":"D. Spielman","year":"2001","unstructured":"Spielman, D., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, New York, pp. 296\u2013305. ACM Press, New York (2001)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-540-30216-2_2","volume-title":"Algorithms and Models for the Web-Graph","author":"R. Andersen","year":"2004","unstructured":"Andersen, R., Chung, F., Lu, L.: Analyzing the small world phenomenon using a hybrid model with local network flow. In: Leonardi, S. (ed.) WAW 2004. LNCS, vol.\u00a03243, pp. 19\u201330. Springer, Heidelberg (2004)"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/335305.335325","volume-title":"Proceedings of the Thiry-Second Annual ACM Symposium on Theory of Computing","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithm perspective. In: Proceedings of the Thiry-Second Annual ACM Symposium on Theory of Computing, New York, pp. 163\u2013170. ACM Press, New York (2000)"},{"issue":"2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1002\/rsa.1022","volume":"19","author":"I. Benjamini","year":"2001","unstructured":"Benjamini, I., Berger, N.: The diameter of long-range percolation clusters on finite cycles. Random Structures Algorithms\u00a019(2), 102\u2013111 (2001)","journal-title":"Random Structures Algorithms"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.10042","volume":"21","author":"D. Coppersmith","year":"2002","unstructured":"Coppersmith, D., Gamarnik, D., Sviridenko, M.: The diameter of a long-range percolation graph. Random Structures Algorithms\u00a021(1), 1\u201313 (2002)","journal-title":"Random Structures Algorithms"},{"issue":"4","key":"3_CR11","doi-asserted-by":"publisher","first-page":"2938","DOI":"10.1214\/009117904000000577","volume":"32","author":"M. Biskup","year":"2004","unstructured":"Biskup, M.: On the scaling of the chemical distance in long-range percolation models. Ann. Probab.\u00a032(4), 2938\u20132977 (2004)","journal-title":"Ann. Probab."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"292","author":"D.J. Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of \u201csmall-world\u201d networks. Nature\u00a0292, 440\u2013442 (1998)","journal-title":"Nature"},{"key":"3_CR13","first-page":"195","volume-title":"Problems in analysis (Papers dedicated to Salomon Bochner, 1969)","author":"J. Cheeger","year":"1970","unstructured":"Cheeger, J.: A lower bound for the smallest eigenvalue of the Laplacian. In: Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pp. 195\u2013199. Princeton Univ. Press, Princeton (1970)"},{"issue":"1","key":"3_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N. Alon","year":"1985","unstructured":"Alon, N., Milman, V.D.: \n                  \n                    \n                  \n                  $\\lambda\\sb 1,$\n                 isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B\u00a038(1), 73\u201388 (1985)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica\u00a06(2), 83\u201396 (1986) (Theory of computing (Singer Island, Fla., 1984))","journal-title":"Combinatorica"},{"issue":"1","key":"3_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A. Sinclair","year":"1989","unstructured":"Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput.\u00a082(1), 93\u2013133 (1989)","journal-title":"Inform. and Comput."},{"issue":"2","key":"3_CR17","doi-asserted-by":"publisher","first-page":"557","DOI":"10.2307\/2000925","volume":"309","author":"G.F. Lawler","year":"1988","unstructured":"Lawler, G.F., Sokal, A.D.: Bounds on the \n                  \n                    \n                  \n                  $L\\sp 2$\n                 spectrum for Markov chains and Markov processes: A generalization of Cheeger\u2019s inequality. Trans. Amer. Math. Soc.\u00a0309(2), 557\u2013580 (1988)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"3","key":"3_CR18","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF02579329","volume":"1","author":"Z. F\u00fcredi","year":"1981","unstructured":"F\u00fcredi, Z., Koml\u00f3s, J.: The eigenvalues of random symmetric matrices. Combinatorica\u00a01(3), 233\u2013241 (1981)","journal-title":"Combinatorica"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1145\/73007.73063","volume-title":"Proceedings of the Twenth-First Annual ACM Symposium on Theory of Computing","author":"J. Friedman","year":"1989","unstructured":"Friedman, J., Kahn, J., Szemer\u00e9di, E.: On the second eigenvalue of random regular graphs. In: Proceedings of the Twenth-First Annual ACM Symposium on Theory of Computing, pp. 587\u2013598. ACM Press, New York (1989)"},{"issue":"6","key":"3_CR20","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM J. Comput.\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM J. Comput."},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/780542.780646","volume-title":"Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing","author":"J. Friedman","year":"2003","unstructured":"Friedman, J.: A proof of Alon\u2019s second eigenvalue conjecture. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 720\u2013724. ACM Press, New York (2003)"},{"issue":"2","key":"3_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U. Feige","year":"2005","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Random Structures and Algorithms\u00a027(2), 251\u2013275 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/316188.316229","volume-title":"SIGCOMM \u201999: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication","author":"M. Faloutsos","year":"1999","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM \u201999: Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pp. 251\u2013262. ACM Press, New York (1999)"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s100510051038","volume":"12","author":"R. Monasson","year":"1999","unstructured":"Monasson, R.: Diffusion, localization and dispersion relations on \u201csmall-world\u201d lattices. The European Physical Journal B\u00a012, 555\u2013567 (1999)","journal-title":"The European Physical Journal B"},{"issue":"1","key":"3_CR25","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s000260300002","volume":"7","author":"F. Chung","year":"2003","unstructured":"Chung, F., Lu, L., Vu, V.: Eigenvalues of random power law graphs. Ann. Comb.\u00a07(1), 21\u201333 (2003)","journal-title":"Ann. Comb."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/SFCS.2003.1238178","volume-title":"FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science","author":"M. Mihail","year":"2003","unstructured":"Mihail, M., Papadimitriou, C., Saberi, A.: On certain connectivity properties of the internet topology. In: FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, p. 28. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"1","key":"3_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/15427951.2005.10129097","volume":"2","author":"A. Flaxman","year":"2005","unstructured":"Flaxman, A., Frieze, A., Fenner, T.: High degree vertices and eigenvalues in the preferential attachment graph. Internet Math.\u00a02(1), 1\u201319 (2005)","journal-title":"Internet Math."},{"key":"3_CR28","first-page":"679","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003)","author":"D.K. Blandford","year":"2003","unstructured":"Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), pp. 679\u2013688. ACM Press, New York (2003)"},{"issue":"4","key":"3_CR29","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1209\/epl\/i2005-10441-3","volume":"73","author":"E. Estrada","year":"2006","unstructured":"Estrada, E.: Spectral scaling and good expansion properties in complex networks. Europhysics Letters\u00a073(4), 649\u2013655 (2006)","journal-title":"Europhysics Letters"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-30216-2_4","volume-title":"Algorithms and Models for the Web-Graph","author":"A. Flaxman","year":"2004","unstructured":"Flaxman, A., Frieze, A.M., Vera, J.: A geometric preferential attachment model of networks. In: Leonardi, S. (ed.) WAW 2004. LNCS, vol.\u00a03243, pp. 44\u201355. Springer, Heidelberg (2004)"},{"key":"3_CR31","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization, p. 301. Wiley-Interscience [John Wiley & Sons], New York (2000) With an appendix on the life and work of Paul Erd\u0151s"},{"key":"3_CR32","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Rucinski, A.: Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web-Graph"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78808-9_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:22:56Z","timestamp":1619522576000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78808-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540788072","9783540788089"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78808-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}