Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-17T16:04:52.347Z Has data issue: false hasContentIssue false
  • English
  • Français

THE ASYMPTOTIC DEGREE DISTRIBUTIONS OF RANDOM FAST GROWTH MODELS FOR TREELIKE NETWORKS

Published online by Cambridge University Press:  03 January 2017

Qunqiang Feng  and
Zhishui Hu
Qunqiang Feng
Affiliation:
Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China E-mail: [email protected]; [email protected]
Zhishui Hu
Affiliation:
Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei 230026, China E-mail: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We propose two random network models for complex networks, which are treelike and always grow very fast. One is the uniform model and the other is the preferential attachment model, and both of them depends on a parameter 0<p<1. We first briefly discuss the network sizes, each of which can be corresponding to a supercritical branching process. And then we mainly study the degree distributions of both models. The asymptotic degree distribution of the first one with any parameter 0<p<1 is a geometric distribution with parameter 1/2, whereas that of the second one, which depends on p, can be uniquely determined by a functional equation of its probability generating function.

Keywords

complex networksdegree distributionfast growthpreferential attachmentrandom trees
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 31 , Issue 2 , April 2017 , pp. 180 - 195
Copyright
Copyright © Cambridge University Press 2017 

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. Agliari, E. & Burioni, R. (2009). Random walks on deterministic scale-free networks: Exact results. Physical Review E 80: 031125.Google Scholar
2. Athreya, K.B. & Ney, P.E. (1972). Branching processes. Berlin: Springer-Verlag.Google Scholar
3. Barabási, A.-L. & Albert, R. (1999). Emergence of scaling in random networks. Science 286: 509–512.Google Scholar
4. Barabási, A.-L., Ravasz, E., & Vicsek, T. (2001). Deterministic scale-free networks. Physica A: Statistical Mechanics and its Applications 229: 559–564.Google Scholar
5. Comellas, F. & Miralles, A. (2010). Mean first-passage time for random walks on generalized deterministic recursive trees. Physical Review E 81: 061103.Google Scholar
6. Cooper, C. & Prałat, P. (2011). Scale-free graphs of increasing degree. Random Structures and Algorithms 38: 396–421.Google Scholar
7. Dorogovtsev, S.N., Goltsev, A.V., & Mendes, J.F.F. (2002). Pseudofractal scale-free web. Physical Review E 65: 066122.Google Scholar
8. Dorogovtsev, S.N. & Mendes, J.F.F. (2002). Accelerated growth of networks. In Bornholdt, S. & Schuster, H.G. (eds.). Handbook of graphs and networks: from the genome to the internet, Berlin: Wiley-VCH, pp. 318–341.CrossRefGoogle Scholar
9. Drmota, M. (2009). Random trees. Springer-Verlag, Wien.Google Scholar
10. Durrett, R. (2007). Random graphs dynamics (Cambridge series in statistical and probabilistic mathematics). New York: Cambridge University Press.Google Scholar
11. Harris, T.E. (1948). Branching Processes. The Annals of Mathematical Statistics 19: 474–494.CrossRefGoogle Scholar
12. Harris, T.E. (1963). The theory of branching processes. Berlin: Springer-Verlag.CrossRefGoogle Scholar
13. van der Hofstad, R. (2014). Random Graphs and Complex Networks. Unpublished manuscript. Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf Google Scholar
14. Janson, S. (2005). Asymptotic degree distribution in random recursive trees. Random Structures and Algorithms 26: 69–83.Google Scholar
15. Janson, S. (2012). Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Probability Surveys 9: 103–252.CrossRefGoogle Scholar
16. Janson, S., Łuczak, T., & Ruciński, A. (2000). Random graphs. New York: Wiley-Interscience.Google Scholar
17. Jung, S., Kim, S., & Kahng, B. (2002). Geometric fractal growth model for scale-free networks. Physical Review E 65: 056101.Google Scholar
18. Lu, Z., Su, Y., & Guo, S. (2013). Deterministic scale-free small-world networks of arbitrary order. Physica A: Statistical Mechanics and its Applications 392: 3555–3562.Google Scholar
19. Móri, T.F. (2002). On random trees. Studia Scientiarum Mathematicarum Hungarica 39: 143–155.Google Scholar
20. Rudas, A., Tóth, B., & Valkó, B. (2007). Random trees and general branching processes. Random Structures and Algorithms 31: 186–202.Google Scholar
21. Smith, D.M.D., Onnela, J.-P., & Jones, N.S. (2009). Master-equation analysis of accelerating networks. Physical Review E 79: 056101.Google Scholar
22. 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.CrossRefGoogle ScholarPubMed