{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:54:26Z","timestamp":1787320466194,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2020\/39\/D\/ST6\/00419"],"award-info":[{"award-number":["2020\/39\/D\/ST6\/00419"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/B\/ST6\/01294"],"award-info":[{"award-number":["2018\/31\/B\/ST6\/01294"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0939370"],"award-info":[{"award-number":["CCF-0939370"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS1661063"],"award-info":[{"award-number":["DMS1661063"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2006440"],"award-info":[{"award-number":["CCF-2006440"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We present a rigorous and precise analysis of the maximum degree and the average degree in a dynamic duplication-divergence graph model introduced by Sol\u00e9 et\u00a0al.\u00a0[ Adv.\u00a0Complex Syst., 5 (2002), pp. 43\u201354] in which the graph grows according to a duplication-divergence mechanism, i.e., by iteratively creating a copy of some node and then randomly alternating the neighborhood of a new node with probability [Formula: see text]. This model captures the growth of some real-world processes, e.g., biological or social networks. In this paper, we prove that for some [Formula: see text], the maximum degree and the average degree of a duplication-divergence graph on [Formula: see text] vertices are asymptotically concentrated with high probability around [Formula: see text] and [Formula: see text], respectively, i.e., they are within at most a polylogarithmic factor from these values with probability at least [Formula: see text] for any constant [Formula: see text].<\/jats:p>","DOI":"10.1137\/23m1592766","type":"journal-article","created":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T04:01:50Z","timestamp":1709784110000},"page":"988-1006","source":"Crossref","is-referenced-by-count":0,"title":["On the Concentration of the Maximum Degree in the Duplication-Divergence Models"],"prefix":"10.1137","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8481-5615","authenticated-orcid":true,"given":"Alan M.","family":"Frieze","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3871-1038","authenticated-orcid":true,"given":"Krzysztof","family":"Turowski","sequence":"additional","affiliation":[{"name":"Theoretical Computer Science Department, Jagiellonian University, Krak\u00f3w 30-348, Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[{"name":"Center for Science of Information, Department of Computer Science, Purdue University, West Lafayette, IN 47907 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,3,7]]},"reference":[{"key":"ref1","volume-title":"Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables","author":"Abramowitz M.","year":"1972"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/120879828"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/107"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1089\/106652703322539024"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"R. Colak , \nF. Hormozdiari , \nF. Moser , \nA. Sch\u00f6nhuth , \nJ. Holman , \nM. Ester , and \nS. C. Sahinalp  , Dense graphlet statistics of protein interaction and random networks, in Proceedings of Biocomputing 2009, World Scientific Publishing, 2009, pp. 178\u2013189.","DOI":"10.1142\/9789812836939_0018"},{"key":"ref7","volume-title":"Graph Theory","author":"Diestel R.","year":"2005"},{"key":"ref8","first-page":"290","volume":"6","author":"Erd\u0151s P.","year":"1959","journal-title":"Publ. Math."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"ref10","volume-title":"Introduction to Random Graphs","author":"Frieze A.","year":"2016"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60440-0_18"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"A. Frieze , \nK. Turowski , and \nW. Szpankowski  , The concentration of the maximum degree in the duplication-divergence models, in Proceedings of the 27th International Conference on Computing and Combinatorics, COCOON 2021, Tainan, Taiwan, October 24\u201326, 2021, Proceedings, \nC.Y. Chen  et al., eds. Lecture Notes in Comput. Sci. 13025, Springer, 2021, pp. 413\u2013424.","DOI":"10.1007\/978-3-030-89543-3_35"},{"key":"ref13","volume-title":"Concrete Mathematics: A Foundation for Computer Science","author":"Graham R.","year":"1994","edition":"2"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.30757\/ALEA.v13-27"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030118"},{"key":"ref16","unstructured":"P. Jacquet , \nK. Turowski , and \nW. Szpankowski  , Power-law degree distribution in the connected component of a duplication graph, in Proceedings of the 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020),  \nM. Drmota  and \nC. Heuberger , eds. LIPIcs. Leibniz Int. Proc. Inform. 159, Schloss Dagstuhl. Leibniz-Zentrum f\u00fcr Informatik, 2020, 16."},{"key":"ref17","volume-title":"Random Graphs","author":"Janson S.","year":"2011"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.30757\/ALEA.v15-53"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1201\/9781003218869"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1017\/9781316216002"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.12.045"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.14"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"T. \u0141uczak , \nA. Magner , and \nW. Szpankowski  , Compression of preferential attachment graphs, in Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), IEEE, 2019, pp. 1697\u20131701.","DOI":"10.1109\/ISIT.2019.8849739"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-86659-3"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-5193(03)00028-6"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbt014"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1142\/S021952590200047X"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2020.2980260"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.37236\/9251"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1017\/9781316779422"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-5347(03)00033-8"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1592766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:57:44Z","timestamp":1787317064000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1592766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,7]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/23M1592766"],"URL":"https:\/\/doi.org\/10.1137\/23m1592766","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,7]]}}}