{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T09:58:52Z","timestamp":1747216732736,"version":"3.40.5"},"reference-count":29,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Compositionality"],"abstract":"<jats:p>The theme in this paper is a composition of random graphs and P\u00f3lya urns. The random graphs are generated through a small structure called the seed. Via P\u00f3lya urns, we study the asymptotic degree structure in a random <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math>-ary hooking network and identify strong laws. We further upgrade the result to second-order asymptotics in the form of multivariate Gaussian limit laws. We give a few concrete examples and explore some properties with a full representation of the Gaussian limit in each case. The asymptotic covariance matrix associated with the P\u00f3lya urn is obtained by a new method that originated in this paper and is reported in \\cite{Mahmoud2022}.<\/jats:p>","DOI":"10.32408\/compositionality-5-6","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T16:47:11Z","timestamp":1691599631000},"page":"6","source":"Crossref","is-referenced-by-count":0,"title":["Degrees in random <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>m<\/mml:mi><\/mml:math>-ary hooking networks"],"prefix":"10.46298","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4823-0887","authenticated-orcid":false,"given":"Kiran R.","family":"Bhutani","sequence":"first","affiliation":[{"name":"Department of Mathematics, The Catholic University of America, Washington, D.C. 20064, U.S.A."}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5874-2427","authenticated-orcid":false,"given":"Ravi","family":"Kalpathy","sequence":"additional","affiliation":[{"name":"Department of Mathematics, The Catholic University of America, Washington, D.C. 20064, U.S.A."}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0962-9406","authenticated-orcid":false,"given":"Hosam","family":"Mahmoud","sequence":"additional","affiliation":[{"name":"Department of Statistics, The George Washington University, Washington, D.C. 20052, U.S.A."}]}],"member":"25203","published-online":{"date-parts":[[2023,8,9]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Athreya, K. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. The Annals of Mathematical Statistics 39, 1801-1817. https:\/\/doi.org\/10.1214\/aoms\/1177698013.","DOI":"10.1214\/aoms\/1177698013"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Bagchi, A. and Pal, A. (1985). Asymptotic normality in the generalized P\u00f3lya-Eggenberger urn model with applications to computer data structures. SIAM Journal on Algebraic and Discrete Methods 6, 394-405. https:\/\/doi.org\/10.1137\/0606041.","DOI":"10.1137\/0606041"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Bahrani, M. and Lumbroso, J. (2019). Split-decomposition trees with prime nodes: Enumeration and random generation of cactus graphs. 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 143-157. https:\/\/doi.org\/10.1137\/1.9781611975062.13.","DOI":"10.1137\/1.9781611975062.13"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Bhutani, K., Kalpathy, R. and Mahmoud, H. (2021). Average measures in polymer graphs. International Journal of Computer Mathematics: Computer Systems Theory 6:1, 37-53. https:\/\/doi.org\/10.1080\/23799927.2020.1860134.","DOI":"10.1080\/23799927.2020.1860134"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Bhutani, K., Kalpathy, R. and Mahmoud, H. (2022). Random networks grown by fusing edges via urns. Network Science, 1-14. https:\/\/doi.org\/10.1017\/nws.2022.30.","DOI":"10.1017\/nws.2022.30"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Bhutani, K., Kalpathy, R. and Mahmoud, H. (2023). Random multi-hooking networks. Probability in the Engineering and Informational Sciences, 1-15. https:\/\/doi.org\/10.1017\/s0269964822000523.","DOI":"10.1017\/s0269964822000523"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Bhutani, K., Kalpathy, R., Mahmoud, H. and Ofonedu, A. (2023+). Some empirical and theoretical attributes of random multi-hooking networks (under review).","DOI":"10.1017\/S0269964822000523"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Brown, G. and Shubert, B. (1984). On random binary trees. Mathematics of Operations Research 9, 43-65. https:\/\/doi.org\/10.1287\/moor.9.1.43.","DOI":"10.1287\/moor.9.1.43"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Chen, C. and Mahmoud, H. (2016). Degrees in random self-similar bipolar networks. Journal of Applied Probability 53, 434-447. https:\/\/doi.org\/10.1017\/jpr.2016.11.","DOI":"10.1017\/jpr.2016.11"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Desmarais, C. and Holmgren, C. (2019). Degree distributions of generalized hooking networks. 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 103-110. https:\/\/doi.org\/10.1137\/1.9781611975505.11.","DOI":"10.1137\/1.9781611975505.11"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Desmarais, C. and Holmgren, C. (2020). Normal limit laws for vertex degrees in randomly grown hooking networks and bipolar networks. The Electronic Journal of Combinatorics 27(2), P2.45. https:\/\/doi.org\/10.37236\/9139.","DOI":"10.37236\/9139"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Desmarais, C. and Mahmoud, H. (2021). Depths in hooking networks. Probability in the Engineering and Informational Sciences, 1-9. https:\/\/doi.org\/10.1017\/s0269964821000164.","DOI":"10.1017\/s0269964821000164"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Drmota, M., Gittenberger, B. and Panholzer, A. (2008). The degree distribution of thickened trees. DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science AI, 149-162. https:\/\/doi.org\/10.46298\/dmtcs.3561.","DOI":"10.46298\/dmtcs.3561"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Freedman, D. (1965). Bernard Friedman's urn. The Annals of Mathematical Statistics 36, 956-970. https:\/\/doi.org\/10.1214\/aoms\/1177700068.","DOI":"10.1214\/aoms\/1177700068"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Gopaladesikan, M., Mahmoud, H. and Ward, M. (2014). Building random trees from blocks. Probability in the Engineering and Informational Sciences 28, 67-81. https:\/\/doi.org\/10.1017\/s0269964813000338.","DOI":"10.1017\/s0269964813000338"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Holmgren, C., Janson, S. and Sileikis, M. (2017). Multivariate normal limit laws for the numbers of fringe subtrees in $m$-ary search trees and preferential attachment trees. The Electronic Journal of Combinatorics 24, p2.51. https:\/\/doi.org\/10.37236\/6374.","DOI":"10.37236\/6374"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Horn, R. and Johnson, C. (1985). Matrix Analysis. Cambridge University Press, Cambridge, UK.","DOI":"10.1017\/CBO9780511810817"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized P\u00f3lya urns. Stochastic Processes and Their Applications 110, 177-245. https:\/\/doi.org\/10.1016\/j.spa.2003.12.002.","DOI":"10.1016\/j.spa.2003.12.002"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Janson, S. (2020). Mean and variance of balanced P\u00f3lya urns. Advances in Applied Probability 52 , 1224-1248. https:\/\/doi.org\/10.1017\/apr.2020.38.","DOI":"10.1017\/apr.2020.38"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Kalpathy, R. and Mahmoud, H. (2016). Degree profile of $m$-ary search trees: A vehicle for data structure compression. Probability in the Engineering and Informational Sciences 30, 133-123. https:\/\/doi.org\/10.1017\/s0269964815000303.","DOI":"10.1017\/s0269964815000303"},{"key":"20","unstructured":"Knuth, D. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd Ed. Addison-Wesley, Boston, Massachusetts."},{"key":"21","doi-asserted-by":"crossref","unstructured":"Mahmoud, H. (2008). P\u00f3lya Urn Models. Chapman-Hall, Orlando, Florida.","DOI":"10.1201\/9781420059847"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Mahmoud, H. (2019). Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment. Advances in Applied Mathematics 111, 101930. https:\/\/doi.org\/10.1016\/j.aam.2019.07.006.","DOI":"10.1016\/j.aam.2019.07.006"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Mahmoud, H. (2019). A spectrum of series-parallel graphs with multiple edge evolution. Probability in the Engineering and Informational Sciences 33, 487-499. https:\/\/doi.org\/10.1017\/s0269964818000505.","DOI":"10.1017\/s0269964818000505"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Mahmoud, H. (2021). Covariances in P\u00f3lya urn schemes. Probability in the Engineering and Informational Sciences 37, 60-71. https:\/\/doi.org\/10.1017\/s0269964821000450.","DOI":"10.1017\/s0269964821000450"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Pouyanne, N. (2008). An algebraic approach to P\u00f3lya processes. Annales de l'Institut Henri Poincar\u00e9, Probabilit\u00e9s et Statistiques 44, 293-323. https:\/\/doi.org\/10.1214\/07-aihp130.","DOI":"10.1214\/07-aihp130"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Resnick, S. and Samorodnitsky, G. (2016). Asymptotic normality of degree counts in a preferential attachment model. Advances in Applied Probability 48, 283-299. https:\/\/doi.org\/10.1017\/apr.2016.56.","DOI":"10.1017\/apr.2016.56"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Smythe, R. (1996). Central limit theorems for urn models. Stochastic Processes and Their Applications 65, 115-137. https:\/\/doi.org\/10.1016\/s0304-4149(96)00094-4.","DOI":"10.1016\/s0304-4149(96)00094-4"},{"key":"28","doi-asserted-by":"crossref","unstructured":"van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1. Cambridge University Press, Cambridge, UK.","DOI":"10.1017\/9781316779422"}],"container-title":["Compositionality"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/compositionality-journal.org\/papers\/compositionality-5-6\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T20:22:46Z","timestamp":1717446166000},"score":1,"resource":{"primary":{"URL":"https:\/\/compositionality.episciences.org\/13525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":29,"URL":"https:\/\/doi.org\/10.32408\/compositionality-5-6","relation":{},"ISSN":["2631-4444"],"issn-type":[{"type":"electronic","value":"2631-4444"}],"subject":[],"published":{"date-parts":[[2023,8,9]]},"article-number":"6"}}