Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-08T19:30:46.917Z Has data issue: false hasContentIssue false
  • English
  • Français

ON SEVERAL PROPERTIES OF A CLASS OF PREFERENTIAL ATTACHMENT TREES—PLANE-ORIENTED RECURSIVE TREES

Published online by Cambridge University Press:  15 May 2020

Panpan Zhang Open the ORCID record for Panpan Zhang [Opens in a new window]
Panpan Zhang*
Affiliation:
Department of Biostatistics, Epidemiology and Informatics, Perelman School of Medicine, University of Pennsylvania, Philadelphia, PA19104, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, several properties of a class of trees presenting preferential attachment phenomenon—plane-oriented recursive trees (PORTs) are uncovered. Specifically, we investigate the degree profile of a PORT by determining the exact probability mass function of the degree of a node with a fixed label. We compute the expectation and the variance of degree variable via a Pólya urn approach. In addition, we study a topological index, Zagreb index, of this class of trees. We calculate the exact first two moments of the Zagreb index (of PORTs) by using recurrence methods. Lastly, we determine the limiting degree distribution in PORTs that grow in continuous time, where the embedding is done in a Poissonization framework. We show that it is exponential after proper scaling.

Keywords

degree distributionplane-oriented recursive treesPoissonizationPólya urnpreferential attachmentZagreb index
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 35 , Issue 4 , October 2021 , pp. 839 - 857
Copyright
Copyright © The Author(s), 2020. 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.)

References

1.Aldous, D. (1989). Probability approximations via the Poisson clumping heuristic. Applied Mathematical Sciences No. 77. New York, NY: Springer-Verlag, xvi+269 pp.CrossRefGoogle Scholar
2.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: 1801–1817.CrossRefGoogle Scholar
3.Avrachenkov, K., & Lebedev, D. (2006). PageRank of scale-free growing networks. Internet Mathematics 3: 207–231.CrossRefGoogle Scholar
4.Balaji, H., & Mahmoud, H. (2017). The Gini index of random trees with an application to caterpillars. Journal of Applied Probability 54: 701–709.CrossRefGoogle Scholar
5.Barabási, A., & Albert, R. (1999). Emergence of scaling in random networks. Science 286: 509–512.CrossRefGoogle ScholarPubMed
6.Berge, C. (1973). Graphs and hypergraphs. Translated from the French by Minieka, Edward. North-Holland Mathematical Library, vol. 6. Amsterdam-London/New York: North-Holland Publishing Co./American Elsevier Publishing Co., Inc., xiv+528 pp.Google Scholar
7.Billingsley, P. (1995). Probability and measure, 3rd ed. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. New York, NY: John Wiley & Sons, Inc., xiv+593 pp.Google Scholar
8.Bollobás, B., Riordan, O., Spencer, J., & Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures & Algorithms 18: 279–290.CrossRefGoogle Scholar
9.Chen, C., & Mahmoud, H. (2018). The continuous-time triangular Pólya process. Annals of the Institute of Statistical Mathematics 70: 303–321.CrossRefGoogle Scholar
10.Chen, W.-C., & Ni, W.-C. (1994). Internal path length of the binary representation of heap-ordered trees. Information Processing Letters 51: 129–132.CrossRefGoogle Scholar
11.Drmota, M., Gittenberger, B., & Panholzer, A. (2008). The degree distribution of thickened trees (English summary). In Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., vol. AI. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 149–161.Google Scholar
12.Feller, W. (1971). An introduction to probability theory and its applications, 2nd ed., vol. II, New York-London-Sydney: John Wiley & Sons, Inc., xxiv+669 pp.Google Scholar
13.Feng, Q., & Hu, Z. (2011). On the Zagreb index of random recursive trees. Journal of Applied Probability 48: 1189–1196.CrossRefGoogle Scholar
14.Feng, Q., & Hu, Z. (2013). Phase changes in the topological indices of scale-free trees. Journal of Applied Probability 50: 516–532.CrossRefGoogle Scholar
15.Feng, Q., & Hu, Z. (2015). Asymptotic normality of the Zagreb index of random b-ary recursive trees. Dal'nevostochnyi Matematicheskii Zhurnal 15: 91–101.Google Scholar
16.Feng, Q., Mahmoud, H., & Panholzer, A. (2010). Limit laws for the Randić index of random binary trees. Annals of the Institute of Statistical Mathematics 60: 319–343.CrossRefGoogle Scholar
17.Fuchs, M., & Lee, C.-K. (2015). The Wiener index of random digital trees. SIAM Journal on Discrete Mathematics 29: 586–614.CrossRefGoogle Scholar
18.Gastwirth, J. (1977). A probability model of a pyramid scheme. The American Statistician 31: 79–82.Google Scholar
19.Gutman, I., & Trinajstić, N. (1972). Graph theory and molecular orbitals. Total ϕ-electron energy of alternant hydrocarbons. Chemical Physics Letters 17: 535–538.CrossRefGoogle Scholar
20.Holmgren, C., & Janson, S. (2017). Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees. Probability Surveys 14: 53–154.CrossRefGoogle Scholar
21.Hwang, H.-K. (2007). Profiles of random trees: plane-oriented recursive trees. Random Structures & Algorithms 30: 380–413.CrossRefGoogle Scholar
22.Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures & Algorithms 25: 69–83.CrossRefGoogle Scholar
23.Janson, S. (2019). Random recursive trees and preferential attachment trees are random split trees. Combinatorics, Probability and Computing 28: 81–99.CrossRefGoogle Scholar
24.Lu, J., & Feng, Q. (1998). Strong consistency of the number of vertices of given degrees in nonuniform random recursive trees. Yokohama Mathematical Journal 45: 61–69.Google Scholar
25.Mahmoud, H. (1992). Distances in random plane-oriented recursive trees. Journal of Computational and Applied Mathematics 41: 237–245.CrossRefGoogle Scholar
26.Mahmoud, H. (2009). Pólya urn models. Texts in Statistical Science Series. Boca Raton, FL: CRC Press, xii+290 pp.Google Scholar
27.Mahmoud, H., & Smythe, R. (1992). Asymptotic joint normality of outdegrees of nodes in random recursive trees. Random Structures & Algorithms 3: 255–266.CrossRefGoogle Scholar
28.Mahmoud, H., Smythe, R., & Szymański, J. (1993). On the structure of random plane-oriented recursive trees and their branches. Random Structures & Algorithms 4: 151–176.CrossRefGoogle Scholar
29.Moon, J. (1974). The distance between nodes in recursive trees. In Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973). London Math. Soc. Lecture Note Ser., vol. 13. London: Cambridge Univ. Press, pp. 125–132.Google Scholar
30.Najock, D., & Heyde, C.C. (1982). On the number of terminal vertices in certain random trees with an application to stemma construction in philology. Journal of Applied Probability 19: 675–680.CrossRefGoogle Scholar
31.Neininger, R. (2002). The Wiener index of random trees. Combinatorics, Probability and Computing 11: 587–597.CrossRefGoogle Scholar
32.Nikolić, S., Tolić, I., Trinajstić, N., & Baučić, I. (2000). On the Zagreb indices as complexity indices. Croatica Chemica Acta 73: 909–921.Google Scholar
33.Nikolić, S., Kovačević, G., Miličević, A., & Trinajstić, N. (2003). The Zagreb indices 30 years after. Croatica Chemica Acta 76: 113–124.Google Scholar
34.Ross, S. (1996). Stochastic processes, 2nd ed. Wiley Series in Probability and Statistics: Probability and Statistics. New York, NY: John Wiley & Sons, Inc., xvi+510 pp.Google Scholar
35.Szymański, J. (1987). On a nonuniform random recursive tree. In Random graphs '85 (Poznań, 1985). North-Holland Math. Stud., vol. 144. Amsterdam: North-Holland, pp. 297–306.Google Scholar
36.Todeschini, R., & Consonni, V. (2009). Molecular descriptors for chemoinformatics. Hoboken, NJ: Wiley, 1257 pp.CrossRefGoogle Scholar
37.Zhang, P. (2016). On properties of several random networks. (Ph.D. Thesis), The George Washington Univeristy, 131 pp.Google Scholar
38.Zhang, P. (2016). On terminal nodes and the degree profile of preferential dynamic attachment circuits. In Thirteenth workshop on analytic algorithmics and combinatorics. Arlington: SIAM, pp. 80–92.Google Scholar
39.Zhang, P. (2019). The Zagreb index of several random models. ArXiv:1901.04657.Google Scholar
40.Zhang, P., & Dey, D. (2019). The degree profile and Gini index of random caterpillar trees. Probability in the Engineering and Informational Sciences 33: 511–527.CrossRefGoogle Scholar
41.Zhang, P., & Mahmoud, H. (2016). The degree profile and weight in Apollonian networks and k-trees. Advances in Applied Probability 48: 163–175.CrossRefGoogle Scholar
42.Zhang, P., Chen, C., & Mahmoud, H. (2015). Explicit characterization of moments of balanced triangular Pólya urns by an elementary approach. Statistics & Probability Letters 96: 149–154.CrossRefGoogle Scholar