Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T10:50:27.006Z Has data issue: false hasContentIssue false
  • English
  • Français

Random networks grown by fusing edges via urns

Published online by Cambridge University Press:  03 November 2022

Kiran R. Bhutani ,
Ravi Kalpathy Open the ORCID record for Ravi Kalpathy [Opens in a new window]  and
Hosam Mahmoud
Kiran R. Bhutani
Affiliation:
Department of Mathematics, The Catholic University of America, Washington, DC, USA
Ravi Kalpathy*
Affiliation:
Department of Mathematics, The Catholic University of America, Washington, DC, USA
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, DC, USA
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Many classic networks grow by hooking small components via vertices. We introduce a class of networks that grows by fusing the edges of a small graph to an edge chosen uniformly at random from the network. For this random edge-hooking network, we study the local degree profile, that is, the evolution of the average degree of a vertex over time. For a special subclass, we further determine the exact distribution and an asymptotic gamma-type distribution. We also study the “core,” which consists of the well-anchored edges that experience fusing. A central limit theorem emerges for the size of the core.

At the end, we look at an alternative model of randomness attained by preferential hooking, favoring edges that experience more fusing. Under preferential hooking, the core still follows a Gaussian law but with different parameters. Throughout, Pólya urns are systematically used as a method of proof.

Keywords

networkrandom graphdegree profilePólya urnlimit lawpreferential attachmentphase transitionStirling numberasymptotic analysispolyacenes
Type
Research Article
Information
Network Science , Volume 10 , Issue 4 , December 2022 , pp. 347 - 360
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Action Editor: Ulrik Brandes

References

Abramowitz, M., & Stegun, I. (1972). Handbook of mathematical functions with formulas, graphs, and mathematical tables. Washington, DC: U.S. Department of Commerce, National Bureau of Standards.Google Scholar
Aguech, R. (2009). Limit theorems for random triangular urn schemes. Journal of Applied Probability, 46(3), 827–843.CrossRefGoogle Scholar
Akter, S., Yamamoto, Y., Zope, R., & Baruah, T. (2021). Static dipole polarizabilities of polyacenes using self-interaction-corrected density functional approximations. Journal of Chemical Physics, 154(11), 114305. doi: 10.1063/5.0041265.CrossRefGoogle ScholarPubMed
Anthony, J. (2008). The larger acenes: Versatile organic semiconductors. Angewandte Chemie International Edition, 47(3), 452–483. doi: 10.1002/anie.200604045.CrossRefGoogle ScholarPubMed
Athreya, K., & Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. The Annals of Mathematical Statistics, 39(6), 1801–1817.CrossRefGoogle Scholar
Bagchi, A., & Pal, A. (1985). Asymptotic normality in the generalized Pólya-Eggenberger urn model with applications to computer data structures. SIAM Journal on Algebraic and Discrete Methods, 6(3), 394–405.CrossRefGoogle Scholar
Bhamidi, S., Fan, R., Fraiman, N., & Nobel, A. (2021). Community modulated recursive trees and population dependent branching processes. Random Structures & Algorithms, 1-32(2), 201–232. doi: 10.1002/rsa.21027.Google Scholar
Bhutani, K., & Khan, B. (2003). A metric on the set of connected simple graphs of given order. Aequationes Mathematicae, 66(3), 232–240.CrossRefGoogle Scholar
Bhutani, K., Kalpathy, R., & Mahmoud, H. (2021). Average measures in polymer graphs. International Journal of Computer Mathematics: Computer Systems Theory, 6(1), 37–53. doi: 10.1080/23799927.2020.1860134.Google Scholar
Chen, C., & Mahmoud, H. (2016). Degree profile of self-similar bipolar networks. Journal of Applied Probability, 53(2), 434–447.CrossRefGoogle Scholar
David, F., & Barton, E. (1962). Combinatorial chance. London: Charles Griffin.CrossRefGoogle Scholar
Desmarais, C., & Holmgren, C. (2018). Degree distributions of generalized hooking networks. In 2019 Proceedings of the sixteenth workshop on analytic algorithmics and combinatorics (ANALCO) .Google Scholar
Desmarais, C., & Mahmoud, H. (2021). Depths in hooking networks. In Probability in the Engineering and Informational Sciences (pp. 1–9). doi: 10.1017/S0269964821000164.Google Scholar
Drmota, M., Gittenberger, B., & Panholzer, A. (2008). The degree distribution of thickened trees. Discrete Mathematics and Theoretical Computer Science. In Proceedings of the fifth colloquium on mathematics and computer science. Proceedings AI, (pp. 149–162).CrossRefGoogle Scholar
Flajolet, P., Dumas, P., & Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In Discrete Mathematics and Theoretical Compute Science AG (pp. 59–118).Google Scholar
Gopaladesikan, M., Mahmoud, H., & Ward, M. (2014). Building random trees from blocks. Probability in the Engineering and Informational Sciences, 28(1), 67–81.CrossRefGoogle Scholar
Graham, R., Knuth, D., & Patashnik, O. (1994). Concrete mathematics. Reading, Massachusetts: Addison-Wesley.Google Scholar
Janson, S. (2006). Limit theorems for triangular urn schemes. Probability Theory and Related Fields, 134(3), 417–452.CrossRefGoogle Scholar
Janson, S. (2010). Moments of Gamma type and the Brownian supremum process area. Probability Surveys, 7(none), 1–52.Google Scholar
Mahmoud, H. (2008). Pólya Urn models. Orlando, Florida: Chapman-Hall.CrossRefGoogle Scholar
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.CrossRefGoogle Scholar
Tönshoff, C., & Bettinger, H. (2021). Pushing the limits of acene chemistry: The recent surge of large acenes. Chemistry–A European Journal, 27(10), 3193–3212. doi: 10.1002/chem.202003112.CrossRefGoogle ScholarPubMed
Trapman, P. (2007). On analytical approaches to epidemics on networks. Theoretical Population Biology, 7(2), 160–173.CrossRefGoogle Scholar
van der Hofstad, R., van Leeuwaarden, J., & Stegehuis, C. (2018). Mesoscopic scales in hierarchical configuration models. Stochastic Processes and their Applications, 128(12), 4246–4276.CrossRefGoogle Scholar
Zamoshchik, N., Zade, S., & Bendikov, M. (2013). Formation of acene-based polymers: Mechanistic computational study. The Journal of Organic Chemistry, 78(20), 10058–10068. doi: 10.1021/jo4006415.CrossRefGoogle ScholarPubMed
Zhang, P., Chen, C., & Mahmoud, H. (2015). Characterization of the moments of balanced triangular urn schemes via an elementary approach. Statistics and Probability Letters, 96, 149–153.CrossRefGoogle Scholar