Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T10:29:04.078Z Has data issue: false hasContentIssue false
  • English
  • Français

DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS

Published online by Cambridge University Press:  13 September 2016

Yarong Feng ,
Hosam Mahmoud  and
Ludger Rüschendorf
Yarong Feng
Affiliation:
Department of Statistics, The George Washington University, Washington, DC 20052, USA E-mails: [email protected]; [email protected]
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, DC 20052, USA E-mails: [email protected]; [email protected]
Ludger Rüschendorf
Affiliation:
Department of Mathematical Stochastics, University of Freiburg, Eckerstraße 1, D-79104 Freiburg, Germany E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the degree profile of random hierarchical lattice networks. At every step, each edge is either serialized (with probability p) or parallelized (with probability 1−p). We establish an asymptotic Gaussian law for the number of nodes of outdegree 1, and show how to extend the derivations to encompass asymptotic limit laws for higher outdegrees. The asymptotic joint distribution of the number of nodes of outdegrees 1 and 2 is shown to be bivariate normal. No phase transition with p is detected in these asymptotic laws.

For the limit laws, we use ideas from the contraction method. The recursive equations which we get involve coefficients and toll terms depending on the recursion variable and thus are not in the standard form of the contraction method. Yet, an adaptation of the contraction method goes through, showing that the method has promise for a wider range of random structures and algorithms.

Keywords

applied probabilitygraphsprobabilistic networksstochastic modelling
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 31 , Issue 1 , January 2017 , pp. 60 - 82
Copyright
Copyright © Cambridge University Press 2016 

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. Bernasconi, N., Panagiotou, K., & Steger, A. (2008). On the degree sequences of random outerplanar and series-parallel graphs. Lecture Notes in Computer Science 5171: 303–316.Google Scholar
2. Bickel, P. & Freedman, D. (1981). Some asymptotic theory for the bootstrap. The Annals of Statistics 9: 1196–1217.Google Scholar
3. Cramer, M. & Rüschendorf, L. (1996). Convergence of a branching type recursion. Annales de l'Iinstitut Henri Poincaré, Probabilités et Statistiques 32: 725–741.Google Scholar
4. Drmota, M., Giménez, O., & Noy, M. (2010). Vertices of given degree in series-parallel graphs. Random Structures & Algorithms 36: 273–314.Google Scholar
5. Eppstein, D. (1992). Parallel recognition of series-parallel graphs. Information and Computation 98: 41–55.Google Scholar
6. Farmakis, I. & Moskowitz, M. (2013). Fixed point theorems and their applications. New Jersey: World Scientific.Google Scholar
7. Feng, Q. (2014). Random fast growth models for treelike networks. Private Communication.Google Scholar
8. Hambly, B. & Jordan, J. (2004). A random hierarchical lattice: the series-parallel graph and its properties. Advances in Applied Probability 36: 824–838.Google Scholar
9. Karr, A. (1993). Probability. New York: Springer.Google Scholar
10. Mahmoud, H. (2013). Some node degree properties of series-parallel graphs evolving under a stochastic growth model. Probability in the Engineering and Informational Sciences 27: 297–307.Google Scholar
11. Mahmoud, H. (2014). Some properties of binary series-parallel graphs. Probability in the Engineering and Informational Sciences 28: 565–572.Google Scholar
12. Neininger, R. & Rüschendorf, L. (2004). A general limit theorem for recursive algorithms and combinatorial structures. The Annals of Applied Probability 14: 378–418.Google Scholar
13. Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures and Algorithms 19: 498–524.Google Scholar
14. Rachev, S. & Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Advances in Applied Probability 27: 770–799.CrossRefGoogle Scholar
15. Rösler, U. (1991). A limit theorem for “Quicksort.” RAIRO Inform. Théor. Appl. 25: 85–100.Google Scholar
16. Rösler, U. & Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29: 3–33.Google Scholar
17. Vervaat, W. (1979). On a stochastic difference equation and a representation of non-negative infinitely divisible random variables. Advances in Applied Probability 11: 750–783.Google Scholar
18. Zhang, Z., Qi, Y., Zhou, S., Gao, S., & Guan, J. (2010). Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees. Physical Review, E 81: 016114.Google Scholar