{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:37Z","timestamp":1750308217325,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other networks that give rise to power-law distributions. These models are based on the notion of preferential attachment, leading to the \u201crich get richer\u201d phenomenon. We present a generalization of the basic model by allowing deletion of individual links and show that it also gives rise to a power-law distribution. We derive the mean-field equations for this stochastic model and show that, by examining a snapshot of the distribution at the steady state of the model, we are able to determine the extent to which link deletion has taken place and estimate the probability of deleting a link. Applying our model to actual Web graph data provides evidence of the extent to which link deletion has occurred. We also discuss a problem that frequently arises in estimating the power-law exponent from empirical data and a few possible methods for dealing with this, indicating our preferred approach. Using this approach our analysis of the data suggests a power-law exponent of approximately 2.15 for the distribution of inlinks in the Web graph, rather than the widely published value of 2.1.<\/jats:p>","DOI":"10.1145\/1149121.1149122","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"117-130","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A stochastic model for the evolution of the Web allowing link deletion"],"prefix":"10.1145","volume":"6","author":[{"given":"Trevor","family":"Fenner","sequence":"first","affiliation":[{"name":"University of London, London, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Levene","sequence":"additional","affiliation":[{"name":"University of London, London, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Loizou","sequence":"additional","affiliation":[{"name":"University of London, London, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/383694.383707"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert R.","year":"2002","unstructured":"Albert , R. and Barab\u00e1si , A.-L. 2002 . Statistical mechanics of complex networks . Rev. Mod. Phys. 74 , 47 -- 97 . Albert, R. and Barab\u00e1si, A.-L. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47--97.","journal-title":"Rev. Mod. Phys."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si A.-L.","year":"1999","unstructured":"Barab\u00e1si , A.-L. and Albert , R. 1999 . Emergence of scaling in random networks . Science 286 , 509 -- 512 . Barab\u00e1si, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.","journal-title":"Science"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.64.035104","article-title":"World Wide Web scaling exponent from Simon's 1955 model","volume":"64","author":"Bornholdt S.","year":"2001","unstructured":"Bornholdt , S. and Ebel , H. 2001 . World Wide Web scaling exponent from Simon's 1955 model . Phys. Rev. E 64 , 035104-1--035104-4. Bornholdt, S. and Ebel, H. 2001. World Wide Web scaling exponent from Simon's 1955 model. Phys. Rev. E 64, 035104-1--035104-4.","journal-title":"Phys. Rev. E"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10084"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/572326.572328"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"056125","DOI":"10.1103\/PhysRevE.63.056125","article-title":"Scaling properties of scale-free evolving networks: Continuous approach","volume":"35","author":"Dorogovtsev S.","year":"2001","unstructured":"Dorogovtsev , S. and Mendes , J. 2001 . Scaling properties of scale-free evolving networks: Continuous approach . Phys. Rev. E 35 , 056125 . Dorogovtsev, S. and Mendes, J. 2001. Scaling properties of scale-free evolving networks: Continuous approach. Phys. Rev. E 35, 056125.","journal-title":"Phys. Rev. E"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1080\/00018730110112519","article-title":"Evolution of networks","volume":"51","author":"Dorogovtsev S.","year":"2002","unstructured":"Dorogovtsev , S. and Mendes , J. 2002 . Evolution of networks . Adv. Phys. 51 , 1079 -- 1187 . Dorogovtsev, S. and Mendes, J. 2002. Evolution of networks. Adv. Phys. 51, 1079--1187.","journal-title":"Adv. Phys."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1214\/aos\/1016120372","article-title":"How to make a Hill plot","volume":"28","author":"Drees H.","year":"2000","unstructured":"Drees , H. , de Haan , L. , and Resnick , S. 2000 . How to make a Hill plot . Ann. Stat. 28 , 254 -- 274 . Drees, H., de Haan, L., and Resnick, S. 2000. How to make a Hill plot. Ann. Stat. 28, 254--274.","journal-title":"Ann. Stat."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1016\/j.physa.2005.01.007","article-title":"A stochastic evolutionary model exhibiting power-law behaviour with an exponential cutoff","volume":"335","author":"Fenner T.","year":"2005","unstructured":"Fenner , T. , Levene , M. , and Loizou , G. 2005 . A stochastic evolutionary model exhibiting power-law behaviour with an exponential cutoff . Physica A 335 , 641 -- 656 . Fenner, T., Levene, M., and Loizou, G. 2005. A stochastic evolutionary model exhibiting power-law behaviour with an exponential cutoff. Physica A 335, 641--656.","journal-title":"Physica A"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S1389-1286(02)00212-8","article-title":"A statistical physics perspective on Web growth","volume":"39","author":"Krapivsky P.","year":"2002","unstructured":"Krapivsky , P. and Redner , S. 2002 . A statistical physics perspective on Web growth . Comput. Netw. 39 , 261 -- 276 . Krapivsky, P. and Redner, S. 2002. A statistical physics perspective on Web growth. Comput. Netw. 39, 261--276.","journal-title":"Comput. Netw."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S1389-1286(02)00209-8","article-title":"A stochastic model for the evolution of the","volume":"39","author":"Levene M.","year":"2002","unstructured":"Levene , M. , Fenner , T. , Loizou , G. , and Wheeldon , R. 2002 . A stochastic model for the evolution of the Web. Comput. Netw. 39 , 277 -- 287 . Levene, M., Fenner, T., Loizou, G., and Wheeldon, R. 2002. A stochastic model for the evolution of the Web. Comput. Netw. 39, 277--287.","journal-title":"Web. Comput. Netw."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman M.","year":"2003","unstructured":"Newman , M. 2003 . The structure and function of complex networks . SIAM Rev. 45 , 167 -- 256 . Newman, M. 2003. The structure and function of complex networks. SIAM Rev. 45, 167--256.","journal-title":"SIAM Rev."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/(SICI)1097-4571(198911)40:6<379::AID-ASI1>3.0.CO;2-Q","article-title":"Bibliometric modeling processes and the empirical validity of Lotka's law","volume":"40","author":"Nicholls P.","year":"1989","unstructured":"Nicholls , P. 1989 . Bibliometric modeling processes and the empirical validity of Lotka's law . J. Amer. Soc. Inform. Sci. 40 , 379 -- 385 . Nicholls, P. 1989. Bibliometric modeling processes and the empirical validity of Lotka's law. J. Amer. Soc. Inform. Sci. 40, 379--385.","journal-title":"J. Amer. Soc. Inform. Sci."},{"key":"e_1_2_1_16_1","first-page":"59","article-title":"The wayback machine: The Web's archive","volume":"26","author":"Notess G.","year":"2002","unstructured":"Notess , G. 2002 . The wayback machine: The Web's archive . Online 26 , 59 -- 61 . Notess, G. 2002. The wayback machine: The Web's archive. Online 26, 59--61.","journal-title":"Online"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"5207","DOI":"10.1073\/pnas.032085699","article-title":"Winners don't take all: Characterizing the competition for links on the web","volume":"99","author":"Pennock D.","year":"2002","unstructured":"Pennock , D. , Flake , G. , Lawrence , S. , Glover , E. , and Giles , C. 2002 . Winners don't take all: Characterizing the competition for links on the web . Proc. Nat. Acad. Sci. U.S.A. 99 , 5207 -- 5211 . Pennock, D., Flake, G., Lawrence, S., Glover, E., and Giles, C. 2002. Winners don't take all: Characterizing the competition for links on the web. Proc. Nat. Acad. Sci. U.S.A. 99, 5207--5211.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"volume-title":"Introduction to Stochastic Dynamic Programming","author":"Ross S.","key":"e_1_2_1_18_1","unstructured":"Ross , S. 1983. Introduction to Stochastic Dynamic Programming . Academic Press , New York, NY . Ross, S. 1983. Introduction to Stochastic Dynamic Programming. Academic Press, New York, NY."},{"volume-title":"Chaos","author":"Schroeder M.","key":"e_1_2_1_19_1","unstructured":"Schroeder , M. 1991. Fractals , Chaos , Power Laws : Minutes from an Infinite Paradise. W. H. Freeman , New York, NY. Schroeder, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W. H. Freeman, New York, NY."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1093\/biomet\/42.3-4.425","article-title":"On a class of skew distribution functions","volume":"42","author":"Simon H.","year":"1955","unstructured":"Simon , H. 1955 . On a class of skew distribution functions . Biometrika 42 , 425 -- 440 . Simon, H. 1955. On a class of skew distribution functions. Biometrika 42, 425--440.","journal-title":"Biometrika"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149121.1149122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1149121.1149122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:13Z","timestamp":1750264273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1149121.1149122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1149121.1149122"],"URL":"https:\/\/doi.org\/10.1145\/1149121.1149122","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}