{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T00:35:42Z","timestamp":1772930142717,"version":"3.50.1"},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>We study a dynamically evolving random graph which adds vertices and edges using preferential attachment and is \u2018attacked by an adversary\u2019. At time <jats:italic>t<\/jats:italic>, we add a new vertex <jats:italic>x<jats:sub>t<\/jats:sub><\/jats:italic> and <jats:italic>m<\/jats:italic> random edges incident with <jats:italic>x<jats:sub>t<\/jats:sub><\/jats:italic>, where <jats:italic>m<\/jats:italic> is constant. The neighbours of <jats:italic>x<jats:sub>t<\/jats:sub><\/jats:italic> are chosen with probability proportional to degree. After adding the edges, the adversary is allowed to delete vertices. The only constraint on the adversarial deletions is that the total number of vertices deleted by time <jats:italic>n<\/jats:italic> must be no larger than \u03b4<jats:italic>n<\/jats:italic>, where \u03b4 is a constant. We show that if \u03b4 is sufficiently small and <jats:italic>m<\/jats:italic> is sufficiently large then with high probability at time <jats:italic>n<\/jats:italic> the generated graph has a component of size at least <jats:italic>n<\/jats:italic>\/30.<\/jats:p>","DOI":"10.1017\/s0963548306007681","type":"journal-article","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T11:59:26Z","timestamp":1155643166000},"page":"261-270","source":"Crossref","is-referenced-by-count":16,"title":["Adversarial Deletion in a Scale-Free Random Graph Process"],"prefix":"10.1017","volume":"16","author":[{"given":"ABRAHAM D.","family":"FLAXMAN","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALAN M.","family":"FRIEZE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUAN","family":"VERA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,3,1]]},"reference":[{"key":"S0963548306007681_manual_ref-7","volume-title":"Handbook of Graphs and Networks","author":"Bollob\u00e1s","year":"2002"},{"key":"S0963548306007681_manual_ref-5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_57"},{"key":"S0963548306007681_manual_ref-8","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129080"},{"key":"S0963548306007681_manual_ref-10","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129084"},{"key":"S0963548306007681_manual_ref-3","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"S0963548306007681_manual_ref-13","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129094"},{"key":"S0963548306007681_manual_ref-29","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/42.3-4.425"},{"key":"S0963548306007681_manual_ref-6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006930"},{"key":"S0963548306007681_manual_ref-28","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"S0963548306007681_manual_ref-22","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48686-0_1"},{"key":"S0963548306007681_manual_ref-25","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_20"},{"key":"S0963548306007681_manual_ref-24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548306007681_manual_ref-19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_11"},{"key":"S0963548306007681_manual_ref-17","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129095"},{"key":"S0963548306007681_manual_ref-21","doi-asserted-by":"publisher","DOI":"10.1511\/2000.19.104"},{"key":"S0963548306007681_manual_ref-30","doi-asserted-by":"publisher","DOI":"10.1515\/9780691188331"},{"key":"S0963548306007681_manual_ref-9","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"S0963548306007681_manual_ref-14","doi-asserted-by":"publisher","DOI":"10.1007\/s000260300002"},{"key":"S0963548306007681_manual_ref-11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1009"},{"key":"S0963548306007681_manual_ref-2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959927"},{"key":"S0963548306007681_manual_ref-12","doi-asserted-by":"crossref","unstructured":"[12] Broder, A. , Kumar, R. , Maghoul, F. , Raghavan, P. , Rajagopalan, S. , Stata, R. , Tomkins, A. and Wiener, J. (2002) Graph structure in the web. In Proc. 9th Intl. World Wide Web Conference, pp. 309\u2013320.","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"S0963548306007681_manual_ref-27","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"S0963548306007681_manual_ref-18","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"S0963548306007681_manual_ref-20","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"S0963548306007681_manual_ref-23","doi-asserted-by":"crossref","unstructured":"[23] Kumar, R. , Raghavan, P. , Rajagopalan, S. , Sivakumar, D. , Tomkins, A. and Upfal, E. (2000) Stochastic models for the web graph, In Proc. IEEE Symposium on Foundations of Computer Science, pp. 57\u201365.","DOI":"10.1109\/SFCS.2000.892065"},{"key":"S0963548306007681_manual_ref-31","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1098\/rstb.1925.0002","article-title":"A mathematical theory of evolution based on the conclusions of Dr. J. C. Willis","volume":"213","author":"Yule","year":"1925","journal-title":"Philos. Trans. Royal Soc. London, Ser. B"},{"key":"S0963548306007681_manual_ref-15","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0937490100"},{"key":"S0963548306007681_manual_ref-1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"key":"S0963548306007681_manual_ref-16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10084"},{"key":"S0963548306007681_manual_ref-26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.009"},{"key":"S0963548306007681_manual_ref-4","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548306007681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T01:34:20Z","timestamp":1750469660000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548306007681\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0963548306007681"],"URL":"https:\/\/doi.org\/10.1017\/s0963548306007681","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3]]}}}