{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:48:00Z","timestamp":1753876080400,"version":"3.41.2"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2023,11,7]],"date-time":"2023-11-07T00:00:00Z","timestamp":1699315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,11,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Real-world networks evolve over time via the addition or removal of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently introduced degree-preserving network growth (DPG) family of models preserves vertex degree, resulting in structures significantly different from and more diverse than previous models ([Nature Physics 2021, DOI:10.1038\/s41567-021-01417-7]). Despite its degree preserving property, the DPG model is able to replicate the output of several well-known real-world network growth models. Simulations showed that many real-world networks can also be constructed from small seed graphs via the DPG process. Here, we start the development of a rigorous mathematical theory underlying the DPG family of network growth models. We prove that the degree sequence of the output of some of the well-known, real-world network growth models can be reconstructed via the DPG process, using proper parametrization. We also show that the general problem of deciding whether a simple graph can be obtained via the DPG process from a small seed (DPG feasibility) is, however, NP-complete. It is an intriguing open problem to uncover whether there is a structural reason behind the DPG-constructability of real-world networks. Keywords: network growth models; degree-preserving growth (DPG); matching theory; synthetic networks; power-law degree distribution.<\/jats:p>","DOI":"10.1093\/comnet\/cnad046","type":"journal-article","created":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T06:26:51Z","timestamp":1702448811000},"source":"Crossref","is-referenced-by-count":0,"title":["Degree-preserving graph dynamics: a versatile process to construct random networks"],"prefix":"10.1093","volume":"11","author":[{"given":"P\u00e9ter L","family":"Erd\u0151s","sequence":"first","affiliation":[{"name":"Department of Combinatorics and Applications, Alfr\u00e9d R\u00e9nyi Inst. of Math. (HUN-REN) , Re\u00e1ltanoda utca 13\u201315, H-1053 Budapest, Hungary"}]},{"given":"Shubha R","family":"Kharel","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy , 225 Nieuwland Science Hall , , IN 46556, USA"},{"name":"Notre Dame , 225 Nieuwland Science Hall , , IN 46556, USA"}]},{"given":"Tam\u00e1s R","family":"Mezei","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Applications, Alfr\u00e9d R\u00e9nyi Inst. of Math. (HUN-REN) , Re\u00e1ltanoda utca 13\u201315, H-1053 Budapest, Hungary"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6602-2849","authenticated-orcid":false,"given":"Zoltan","family":"Toroczkai","sequence":"additional","affiliation":[{"name":"Department of Physics and Astronomy , 225 Nieuwland Science Hall , , IN 46556, USA"},{"name":"Notre Dame , 225 Nieuwland Science Hall , , IN 46556, USA"}]}],"member":"286","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"2023121306264367400_cnad046-B1","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","article-title":"A probabilistic proof of an asymptotic formula for the number of labelled regular graphs","volume":"1","author":"Bollob\u00e1s","year":"1980","journal-title":"Eur. J. Combin"},{"key":"2023121306264367400_cnad046-B2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/rsa.3240060204","article-title":"A critical point for random graphs with a given degree sequence","volume":"6","author":"Molloy","year":"1995","journal-title":"Random Struct. Algorithms"},{"key":"2023121306264367400_cnad046-B3","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"first-page":"171","year":"2000","author":"Aiello","key":"2023121306264367400_cnad046-B4"},{"key":"2023121306264367400_cnad046-B5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/rsa.21004","article-title":"Fast uniform generation of random graphs with given degree sequences","volume":"59","author":"Arman","year":"2021","journal-title":"Random Struct. & Algorithms"},{"key":"2023121306264367400_cnad046-B6","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":"Barabasi","year":"1999","journal-title":"Science"},{"key":"2023121306264367400_cnad046-B7","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1038\/s41567-021-01417-7","article-title":"Degree-preserving network growth","volume":"18","author":"Kharel","year":"2022","journal-title":"Nat. Phys"},{"year":"2003","author":"Bourassa","key":"2023121306264367400_cnad046-B8"},{"key":"2023121306264367400_cnad046-B9","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Canad. J. Math"},{"key":"2023121306264367400_cnad046-B10","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Diskret. Analiz"},{"key":"2023121306264367400_cnad046-B11","first-page":"225","article-title":"A theorem concerning Hamilton lines","volume":"7","author":"P\u00f3sa","year":"1962","journal-title":"Magyar Tud. Akad. Mat. Kutat Int. Kzl"},{"key":"2023121306264367400_cnad046-B12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0012-365X(76)90078-9","article-title":"A method in graph theory","volume":"15","author":"Bondy","year":"1976","journal-title":"Discrete Math"},{"key":"2023121306264367400_cnad046-B13","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum","year":"1989","journal-title":"SIAM J. Comput."},{"key":"2023121306264367400_cnad046-B14","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","article-title":"A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries","volume":"51","author":"Jerrum","year":"2004","journal-title":"J. ACM"},{"key":"2023121306264367400_cnad046-B15","first-page":"873","article-title":"On counting perfect matchings in general graphs","volume":"10807","author":"\u0160tefankovi\u010d","year":"2018","journal-title":"LATIN 2018: Theor. Informatics, LNCS"},{"key":"2023121306264367400_cnad046-B16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejc.2021.103421","article-title":"The mixing time of switch Markov chains: a unified approach","volume":"99","author":"Erd\u0151s","year":"2022","journal-title":"Eur. J. Combin"},{"key":"2023121306264367400_cnad046-B17","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.aim.2015.09.002","article-title":"Enumeration of graphs with a heavy-tailed degree sequence","volume":"287","author":"Gao","year":"2016","journal-title":"Adv. Math"},{"key":"2023121306264367400_cnad046-B18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.dam.2020.12.004","article-title":"Mixing time of the switch Markov chain and stable degree sequences","volume":"291","author":"Gao","year":"2021","journal-title":"Discrete Appl. Math"},{"first-page":"1741","year":"2018","author":"Gao","key":"2023121306264367400_cnad046-B19"},{"key":"2023121306264367400_cnad046-B20","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1017\/9781316779422","volume-title":"Random Graphs and Complex Networks","author":"van der Hofstad","year":"2016"},{"key":"2023121306264367400_cnad046-B21","doi-asserted-by":"crossref","first-page":"15879","DOI":"10.1073\/pnas.252631999","article-title":"The average distances in random graphs with given expected degrees","volume":"99","author":"Chung","year":"2002","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023121306264367400_cnad046-B22","first-page":"799","volume-title":"Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks","author":"Holt","year":"2005"},{"key":"2023121306264367400_cnad046-B23","doi-asserted-by":"crossref","first-page":"15263","DOI":"10.1103\/PhysRevB.49.15263","article-title":"Correlations in two-dimensional vortex liquids","volume":"49","author":"Hu","year":"1994","journal-title":"Phys. Rev. B"},{"key":"2023121306264367400_cnad046-B24","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1017\/S0963548306007978","article-title":"Sampling regular graphs and a peer-to-peer network","volume":"16","author":"Cooper","year":"2007","journal-title":"Combin. Probab. Comput"},{"year":"2009","author":"Gao","key":"2023121306264367400_cnad046-B25"},{"key":"2023121306264367400_cnad046-B26","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1002\/rsa.20253","article-title":"Short cycle distribution in random regular graphs recursively generated by pegging","volume":"34","author":"Gao","year":"2008","journal-title":"Random Struct. Algorithms"},{"key":"2023121306264367400_cnad046-B27","doi-asserted-by":"crossref","first-page":"#R44. 19","DOI":"10.37236\/133","article-title":"Rate of convergence of the short cycle distribution in random regular graphs generated by pegging","volume":"16","author":"Gao","year":"2009","journal-title":"Elec. J. Combin"},{"key":"2023121306264367400_cnad046-B28","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/jgt.20472","article-title":"Connectivity of random regular graphs generated by the Pegging algorithm","volume":"65","author":"Gao","year":"2011","journal-title":"J. Graph Theory"},{"key":"2023121306264367400_cnad046-B29","doi-asserted-by":"crossref","DOI":"10.1007\/s00208-023-02574-1","article-title":"The sequence of prime gaps is graphic","author":"Erd\u0151s","year":"2023","journal-title":"Mathematische Annalen, pp. 21"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/6\/cnad046\/54358360\/cnad046.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comnet\/article-pdf\/11\/6\/cnad046\/54358360\/cnad046.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T06:27:00Z","timestamp":1702448820000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnad046\/7471460"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,7]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11,7]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnad046","relation":{},"ISSN":["2051-1329"],"issn-type":[{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2023,12,1]]},"published":{"date-parts":[[2023,11,7]]},"article-number":"cnad046"}}